Finding index in list in C++

Question

I need to find correct index in a array by comparing ranges. Here is my first try:

int TunerDriver::TunerLookUpTable(double Freq) {
  Freq /= 1e6;
  if (Freq >= 60 and Freq < 140)
    return 1;
  else if (Freq >= 180 and Freq < 280)
    return 2;
  else if (Freq >= 280 and Freq < 460)
    return 3;
  else if (Freq >= 140 and Freq < 180)
    return 4;
  else if (Freq >= 2720 and Freq < 4020)
    return 5;
  else if (Freq >= 4020 and Freq <= 6000)
    return 6;
  else if (Freq >= 2000 and Freq < 2720)
    return 7;
  else if (Freq >= 830 and Freq < 1420)
    return 8;
  else if (Freq >= 1420 and Freq < 2000)
    return 9;
  else if (Freq >= 460 and Freq < 830)
    return 10;
  else {
    //TODO: throw exception
  }
}

I believe I can use std::pair and for to increase readability. Can you assist me in this case?

Answer 1

It's a short bit of code, but enough to work with, I think. Here are some suggestions to help you improve your code.

Minimize the number of comparisons

There is not really a need to check both upper and lower bounds for each possibility if the comparisons are done in order. That is, we could compare the incoming Freq to 60, then 140, then 180, etc. That might look like this:

int FreqLookup(double Freq) {
    if (Freq < 60e6 || Freq > 6000e6) {
        return 0;  // or throw an error
    }
    if (Freq < 140e6) return 1;
    if (Freq < 180e6) return 4;
    if (Freq < 280e6) return 2;
    if (Freq < 460e6) return 3;
    if (Freq < 830e6) return 10;
    if (Freq < 1420e6) return 8;
    if (Freq < 2000e6) return 9;
    if (Freq < 2720e6) return 7;
    if (Freq < 4020e6) return 5;
    return 6;
}

Put constants in a structure

Having the constants in a structure allows the code to be more data driven. Here's what I'd suggest:

struct FreqTableEntry {
    double freq;
    int divisor;
    operator double() const { return freq; }
}; 
static constexpr std::array<FreqTableEntry, 11> lookup {{
    { 60e6, 0 }, // error if below 60e6
    { 140e6, 1 },
    { 180e6, 4 },
    { 280e6, 2 },
    { 460e6, 3 },
    { 830e6, 10 },
    { 1420e6, 8 },
    { 2000e6, 9 },
    { 2720e6, 7 },
    { 4020e6, 5 },
    { 6000e6, 6 },
}};

Now we have a nice, neat, compile-time lookup table. Note also that we can avoid division by simply using the full value in the table.

Use a standard algorithm

The std::upper_bound algorithm returns an iterator to the first entry that is greater than the given value. We can use it:

auto it{std::upper_bound(lookup.cbegin(), lookup.cend(), Freq)};

It would be nice to simply return it->divisor but we have to handle a few special cases. First, if the frequency is exactly 6000e6, we need to return 6. Next, if the frequency is < 60e6 or > 6000e6, we need to indicate an error. I've chosen to return 0 as an indication of error, but one could also throw if that's more appropriate. Putting it all together we have this:

#include <array>
#include <algorithm>

int alt(double Freq) {
    struct FreqTableEntry {
        double freq;
        int divisor;
        operator double() const { return freq; }
    }; 
    static constexpr std::array<FreqTableEntry, 11> lookup {{
        { 60e6, 0 }, // error if below 60e6
        { 140e6, 1 },
        { 180e6, 4 },
        { 280e6, 2 },
        { 460e6, 3 },
        { 830e6, 10 },
        { 1420e6, 8 },
        { 2000e6, 9 },
        { 2720e6, 7 },
        { 4020e6, 5 },
        { 6000e6, 6 },
    }};
    // special case the last entry
    if (Freq == lookup.back().freq) {
        return lookup.back().divisor;
    }
    auto it{std::upper_bound(lookup.cbegin(), lookup.cend(), Freq)};
    if (it == lookup.cend() || it->divisor == 0) { 
        return 0;  // could throw here as alternative
    }
    return it->divisor;
}

Provide a test program

It's often helpful to write a test program and to provide it to reviewers to make it clear what the program is expected to do and how it will be called. I modified your routine slightly to return 0 as an error indication and made it a standalone function. The test program in this case, was just to compare the original routine to the alternative (named alt) shown above:

#include <iostream>

int main() {
    for (double f{30e6}; f <= 6020e6; f += 10e6) {
        if (TunerLookUpTable(f) != alt(f)) {
            std::cout << "ERROR: TunerLookUpTable(" << f/1e6 << " MHz) = " 
                << TunerLookUpTable(f) << ", but alt(f) = " << alt(f) << '\n';
        }
    }
}