how do you insert the value in a sorted vector?

by

The simple answer to the question:

template< typename T >
typename std::vector<T>::iterator 
   insert_sorted( std::vector<T> & vec, T const& item )
{
    return vec.insert
        ( 
            std::upper_bound( vec.begin(), vec.end(), item ),
            item 
        );
}

Version with a predicate.

template< typename T, typename Pred >
typename std::vector<T>::iterator
    insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
{
    return vec.insert
        ( 
           std::upper_bound( vec.begin(), vec.end(), item, pred ),
           item 
        );
}

Where Pred is a strictly-ordered predicate on type T.

For this to work the input vector must already be sorted on this predicate.

The complexity of doing this is O(log N) for the upper_bound search (finding where to insert) but up to O(N) for the insert itself.

For a better complexity you could use std::set<T> if there are not going to be any duplicates or std::multiset<T> if there may be duplicates. These will retain a sorted order for you automatically and you can specify your own predicate on these too.

There are various other things you could do which are more complex, e.g. manage a vector and a set / multiset / sorted vector of newly added items then merge these in when there are enough of them. Any kind of iterating through your collection will need to run through both collections.

Using a second vector has the advantage of keeping your data compact. Here your “newly added” items vector will be relatively small so the insertion time will be O(M) where M is the size of this vector and might be more feasible than the O(N) of inserting in the big vector every time. The merge would be O(N+M) which is better than O(NM) it would be inserting one at a time, so in total it would be O(N+M) + O(M²) to insert M elements then merge.

You would probably keep the insertion vector at its capacity too, so as you grow that you will not be doing any reallocations, just moving of elements.

More Related Contents:

  1. What’s the most efficient way to erase duplicates and sort a vector?
  2. How do I sort a std::vector by the values of a different std::vector?
  3. Sorting a vector in descending order
  4. How to use std::sort with a vector of structures and compare function?
  5. Sorting a std::vector by the string?
  6. Insertion sort stops working after million input
  7. Thou shalt not inherit from std::vector
  8. C++ sorting and keeping track of indexes
  9. std::vector::resize() vs. std::vector::reserve()
  10. Is std::vector so much slower than plain arrays?
  11. vector vs. list in STL
  12. How do I erase an element from std::vector by index?
  13. problem sorting using member function as comparator
  14. Is it safe to assume that STL vector storage is always contiguous?
  15. Efficient way of reading a file into an std::vector?
  16. Looking for C++ STL-like vector class but using stack storage
  17. Sort list using STL sort function
  18. How to initialize std::vector from C-style array?
  19. Appending a vector to a vector [duplicate]
  20. Why is it OK to return a ‘vector’ from a function?
  21. C++, Sort One Vector Based On Another One [duplicate]
  22. Is the use of std::vector objects in C++ acceptable, or should I use an alternative?
  23. std::vector reserve() and push_back() is faster than resize() and array index, why?
  24. Vector Iterators Incompatible
  25. Which type of sorting is used in the std::sort()?
  26. Why the libc++ std::vector internally keeps three pointers instead of one pointer and two sizes?
  27. Why is a C++ Vector called a Vector? [closed]
  28. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  29. C++ STL: Array vs Vector: Raw element accessing performance
  30. How to cheaply assign C-style array to std::vector?

Leave a Comment