CODEWITHSUNDEEP
c++sortingc++11binary-searchc++03
Robin Hsu
Robin Hsu

Reputation: 4484

C++ std::lower_bound() function to find insertion point for an index-sorted vector

Suppose I have vector<Foo>, and its index is externally sorted in a vector<int> by a key field .bar in class Foo. e.g.

class Foo {
public:
     int bar;
     int other;
     float f;
     Foo(int _b, int _o, float _f): bar(_b), other(_o), f(_f) {}
};

vector<Foo> foos;
vector<int> sortedIndex;

sortedIndex contain the sorted indices of foos.

Now, I want to insert something to foos, and keep it sorted externally (sorting key is .bar) in sortedIndex. e.g.

foos.push_back(Foo(10,20,30.0));
sortedIndex.insert(
                   lower_bound(sortedIndex.begin(),
                               sortedIndex.end(),
                               10 /* this 10 won't work*/,
                               some_compare_function
                   ),
                   1,
                   foos.size()-1
);

Apparently, the number 10 won't work: The vector sortedIndex contains indices, not value, some_compare_function will be confused, as it does not know when to use direct value, and when to transform the index to value (foo[i].bar rather than just i) before comparison.

Any idea? I have seen the answer to this question. The answer suggests that I can use compare function bool comp(foo a, int b). However, how can the binary search algorithm know that the int b refers to .bar not .other, since both are defined as int?

I would like also to know if the answer will be different for C++03 and C++11. Please mark your answer C++03/C++11. Thanks.

Upvotes: 1

Views: 1598

Answers (1)

Anton Savin
Anton Savin

Reputation: 41301

some_compare_function won't be "confused". Its first parameter is always an element of sortedIndex, and the second parameter is a value to compare to, that is 10 in your example. So in C++11 you can implement it like this:

sortedIndex.insert(
    lower_bound(sortedIndex.begin(),
        sortedIndex.end(),
        10,
        [&foos](int idx, int bar) {
            return foos[idx].bar < bar;
        }
    ),
    foos.size()-1
);

Upvotes: 2

Related Questions