Using insert() on empty std::vector when sorting

Question

I know ideally to add to a std::vector without worry I should use push_back(). However my problem set is that I need a clean code to check if the value I am entering is already in the std::vector and if not, I have to put in sequential, ascending order. To do that I am doing:

vector<Book>::iterator it;
it = std::find(books.begin(), books.end(), b);
if (it != books.end()) {
    *it = b; // if b exists in books, overwrite the iterator
}
else {
    vector<Book>::iterator _it;
    _it = lower_bound(books.begin(), books.end(), b);
    books.insert(_it, b); // here on an empty vector, _it has no values
}

The else will only run if the value b doesnt already exist in the std::vector. If this is the first value being checked against it, the else runs (since its empty) and the std::iterator is at books[0](?).

What makes me cautious about using this is that when debugging, on the insert() line, the value of _it reads "Error Reading...." for each of the members for which the std::iterator is pointing to. Now the program functions and yields anticipated results, but is it erroneously?

Answer 1

What you are doing works fine. However it is not the most efficient way. Using std::find doesn't take advantage of the fact that the data in the vector is sorted, it visits every element until if finds the correct one.

Instead of std::find you can use std::lower_bound from the beginning because that will find your element if it exists and if not, it will find the correct place to insert a new one.

Also it will use a binary search so it will be leaps and bounds faster than std::find. Also you don't end up finding the insertion/replacemt point twice.

Something like this should do:

void insert_or_replace(std::vector<Book>& books, Book const& b)
{
    std::vector<Book>::iterator it;

    it = std::lower_bound(books.begin(), books.end(), b);

    if(it != books.end() && *it == b)
        *it = b;
    else
        books.insert(it, b);
}