Using insert () on empty std :: vector when sorting
I know it's ideal to add to std::vector
no problem I have to use push_back()
. However, my problem is that I need clean code to check if the value I am entering is already in std::vector
, and if not, I have to enter sequential, ascending. To do this, I do:
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
}
else
will only work if the value b
doesn't already exist in the std::vector
. If this is the first value checked against it, the mileage else
(starting from its empty) and std::iterator
equals books[0]
(?).
What I'm worried about is that when debugging the line, the insert()
value _it
reads "Error Reading ...." for each of the members it points std::iterator
to. The program now functions and gives the expected results, but is it wrong?
source to share
What you are doing works great. However, this is not the most efficient way. The usage std::find
doesn't take advantage of the fact that the data in the vector is sorted, it visits each element until it finds the correct one.
Instead, std::find
you can use std::lower_bound
from the beginning, because it will find your element if it exists, and if not, it will find the right place to insert a new one.
Also it will use binary search, so it will jump and bound faster than std::find
. Also you cannot find the insertion / replacement 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);
}
source to share
The code is pretty good. An lower_bound(books.begin(), books.end(), b)
iterator will be returned for an empty vector end()
. Passing it to std :: vector :: insert will work fine.
pos
- the iterator before which the content will be inserted.pos
can be an iteratorend()
and about your concern:
What I am concerned, is the fact that when debugging in a string
insert()
value_it
reads "Error Reading ...." for each of the members, which pointsstd::iterator
to.
This is because the iterator end()
points to the position following the last element, so it is not valid to access it (to get a nonexistent element).
source to share
This is a well-defined behavior.
lower_bound
will return the ending iterator ( books.end()
in your case) for an empty range or if it b
should appear after the last element. insert
will add a new element before the iterator goes to it, so that will be before end
. On an empty vector, this will add the element to the vector.
source to share