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!

I don't get all these votes to close, there is nothing wrong with this question. There are things wrong with the code but that makes it a valid question. — CashCow, Oct 19 '12 at 06:39
@CashCow - I agree completely. StackOverflow's nearly fatal flaw, in my opinion, is the activity of overzealous close-voters. As the SO usership grows, the number of close votes required does *not* grow, and close voters are more active by an order or orders of magnitude than re-open voters, causing this problem. — Dan Nissenbaum, Mar 24 '14 at 12:12
If the problem is that he's having compiler errors, he should tell us what they are. If we see the errors, we can probably immediately post an answer. Without the errors we have to go through the additional work of compiling it ourselves, which makes us not want to answer, which makes this a bad question. — Mooing Duck, Mar 24 '14 at 16:35
Worse, when I try to compile this, the first error I get is `vector does not name a type`. So the obvious answer to his question is "include the `` header." Or maybe he already did that. I can't tell, because the code is incomplete and the errors aren't listed. Also, did he or did he not use `using namespace std;`? No way to tell if that's part of the answer or not. — Mooing Duck, Mar 24 '14 at 16:37
The title of the question shows what he wants to know how to do, i.e. use lower_bound where it says "How to use lower bound here". In any case, this question is 17 months old, was answered same day (by me) with the answer accepted. It's tricky to solve because you need to do different compares. Not even sure it can be done with a lambda yet. — CashCow, Mar 26 '14 at 17:23

CashCow · Accepted Answer · 2014-08-27T12:24:13.293

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

score 2 · Answer 2 · answered Oct 19 '12 at 06:29

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;
    }

score 2 · Answer 3 · answered Oct 19 '12 at 06:31

2

Class keyword must start from lower c - class.
struct Value has wrong type qualtiy instead of quality
I dont see using namespace std to use STL types without it.
vector<value> - wrong type value instead of Value
Etc.

You have to check it first before posting here with such simple errors i think. And main problem here that comparison function cant be member of class. Use it as free function:

bool compareValue(const Value lhs, const int time) { 
    return lhs.time < time ; 
}

answered Oct 19 '12 at 06:31

Denis Ermolin

5,530
6
27
44

I fixed a couple of the typos, assumed he had done using namespace std; and included relevant headers. (Of course better to qualify rather than using namespace). – CashCow Oct 19 '12 at 07:10

score 0 · Answer 4 · answered Oct 19 '12 at 06:27

0

class is the keyword and not "Class":

class MyClass {

And its body should be followed by semicolon ;.
There can be other errors, but you may have to paste them in the question for further help.

answered Oct 19 '12 at 06:27

iammilind

68,093
33
169
336

score 0 · Answer 5 · answered Oct 19 '12 at 06:30

You just want to make compareValue() a normal function. The way you have implemented it right now, you need an object of type MyClass around. The way std::lower_bound() will try to call it, it will just pass in two argument, no extra object. If you really want it the function to be a member, you can make it a static member.

That said, there is a performance penalty for using functions directly. You might want to have comparator type with an inline function call operator:

struct MyClassComparator {
    bool operator()(MyClass const& m0, MyClass const& m1) const {
        return m0.time < m1.time;
    }
};

... and use MyClassComparator() as comparator.

compare function in lower bound

5 Answers5

Linked