Is there a sorted_vector class, which supports insert() etc.?

Question

Often, it is more efficient to use a sorted std::vector instead of a std::set. Does anyone know a library class sorted_vector, which basically has a similar interface to std::set, but inserts elements into the sorted vector (so that there are no duplicates), uses binary search to find elements, etc.?

I know it's not hard to write, but probably better not to waste time and use an existing implementation anyway.

Update: The reason to use a sorted vector instead of a set is: If you have hundreds of thousands of little sets that contain only 10 or so members each, it is more memory-efficient to just use sorted vectors instead.

Answer 1

Boost.Container flat_set

Boost.Container flat_[multi]map/set containers are ordered-vector based associative containers based on Austern's and Alexandrescu's guidelines. These ordered vector containers have also benefited recently with the addition of move semantics to C++, speeding up insertion and erasure times considerably. Flat associative containers have the following attributes:

• Faster lookup than standard associative containers
• Much faster iteration than standard associative containers.
• Less memory consumption for small objects (and for big objects if shrink_to_fit is used)
• Improved cache performance (data is stored in contiguous memory)
• Non-stable iterators (iterators are invalidated when inserting and erasing elements)
• Non-copyable and non-movable values types can't be stored
• Weaker exception safety than standard associative containers (copy/move constructors can throw when shifting values in erasures and insertions)
• Slower insertion and erasure than standard associative containers (specially for non-movable types)

Live demo:

#include <boost/container/flat_set.hpp> #include <iostream> #include <ostream>  using namespace std;  int main() {     boost::container::flat_set<int> s;     s.insert(1);     s.insert(2);     s.insert(3);     cout << (s.find(1)!=s.end()) << endl;     cout << (s.find(4)!=s.end()) << endl; } 

---

jalf: If you want a sorted vector, it is likely better to insert all the elements, and then call std::sort() once, after the insertions.

boost::flat_set can do that automatically:

template<typename InputIterator>  flat_set(InputIterator first, InputIterator last,           const Compare & comp = Compare(),           const allocator_type & a = allocator_type()); 

Effects: Constructs an empty set using the specified comparison object and allocator, and inserts elements from the range [first, last).

Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise N*log(N), where N is last - first.

Answer 2

The reason such a container is not part of the standard library is that it would be inefficient. Using a vector for storage means objects have to be moved if something is inserted in the middle of the vector. Doing this on every insertion gets needlessly expensive. (On average, half the objects will have to be moved for each insertion. That's pretty costly)

If you want a sorted vector, it is likely better to insert all the elements, and then call std::sort() once, after the insertions.