compare function in lower bound

Question

I have following structure

    enum quality { good = 0, bad, uncertain };

    struct Value {
       int time;
       int value;
       quality qual;
    };

    class MyClass {

public:
    MyClass() {
        InsertValues();
    }

       void InsertValues();

       int GetLocationForTime(int time);

private:

    vector<Value> valueContainer;
};

void MyClass::InsertValues() {
    for(int num = 0; num < 5; num++) {
        Value temp;
        temp.time = num;
        temp.value = num+1;
        temp.qual = num % 2;
        valueContainer.push_back(temp);
    }
}


int MyClass::GetLocationForTime(int time)
{

   // How to use lower bound here.
   return 0;
}

In above code I have been thrown with lot of compile errors. I think I am doing wrong here I am new to STL programming and can you please correct me where is the error? Is there better to do this?

Thanks!

Answer 1

The predicate needs to take two parameters and return bool.

As your function is a member function it has the wrong signature.

In addition, you may need to be able to compare Value to int, Value to Value, int to Value and int to int using your functor.

struct CompareValueAndTime
{
   bool operator()( const Value& v, int time ) const 
   {
       return v.time < time;
   }

   bool operator()( const Value& v1, const Value& v2 ) const 
   {
       return v1.time < v2.time;
   }

   bool operator()( int time1, int time2 ) const
   {
       return time1 < time2;
   }

   bool operator()( int time, const Value& v ) const
   {
      return time < v.time;
   }
};

That is rather cumbersome, so let's reduce it:

struct CompareValueAndTime
{
   int asTime( const Value& v ) const // or static
   {
      return v.time;
   }

   int asTime( int t ) const // or static
   {
      return t;
   }

   template< typename T1, typename T2 >
   bool operator()( T1 const& t1, T2 const& t2 ) const
   {
       return asTime(t1) < asTime(t2);
   }
};

then:

std::lower_bound(valueContainer.begin(), valueContainer.end(), time,
   CompareValueAndTime() );

There are a couple of other errors too, e.g. no semicolon at the end of the class declaration, plus the fact that members of a class are private by default which makes your whole class private in this case. Did you miss a public: before the constructor?

Your function GetLocationForTime doesn't return a value. You need to take the result of lower_bound and subtract begin() from it. The function should also be const.

If the intention of this call is to insert here, then consider the fact that inserting in the middle of a vector is an O(N) operation and therefore vector may be the wrong collection type here.

Note that the lower_bound algorithm only works on pre-sorted collections. If you want to be able to look up on different members without continually resorting, you will want to create indexes on these fields, possibly using boost's multi_index

Answer 2

One error is that the fourth argument to lower_bound (compareValue in your code) cannot be a member function. It can be a functor or a free function. Making it a free function which is a friend of MyClass seems to be the simplest in your case. Also you are missing the return keyword.

class MyClass {
    MyClass() { InsertValues(); }
    void InsertValues();
    int GetLocationForTime(int time);
    friend bool compareValue(const Value& lhs, const Value& rhs)
    {
        return lhs.time < rhs.time;
    }