How to insert to a vector to ensure it remains sorted?

Question

So, I'm storing data in std::vector's, because I need my data to be stored contiguously. I want to be able to perform binary searches on this data, but I don't want to be calling std::sort all the time, so naturally the place to look is at how data is inserted and deleted into the vector. How would I go about doing this?

From my understanding the best way to find the proper place to insert is use a binary search. From what I know of binary searches, though:

T binarySearchRecursive(int key, int start, int end)
{
   if (end < start)
      //key does not exist in the vector

   mid = (start + end) / 2;

   if (data[mid] > key)
      return binarySearchRecursive(key, start, mid-1);
   else if (data[mid] < key
      return binarySearchRecursive(key, mid+1, end);
   else // if (data[mid] == key)
      return data[mid];
}

What I'm most interested in is the "if (end < start)" part, this implies that the entry I'm trying to insert doesn't already exist in the vector. What I need, however, is a way to return an index or an iterator that would allow me to "std::vector::insert()" or "std::vector::emplace()" to insert an element at that position. Between start, end, and mid I should be able to gleam this information, I just don't know how.

Allowing multiple keys to be inserted into vector would simple be a matter of if (data[mid] == key) data.emplace(mid, args...);

So, how do I find the correct iterator/index to insert an element into a vector such that it remains sorted?

@Benjamin Thanks, std::lower_bound was exactly what I was looking for. Why bother writing a binary search that might be buggy, when I can rely on the STL to write a guaranteed correct version for me? — Haydn V. Harach, Aug 27 '14 at 09:26

How to insert to a vector to ensure it remains sorted?

0 Answers0