is it possible for set to have std::vector as underlying storage for storage of its elements?

Question

For small collections std::vector is almost certainly the best container whatever the operations applied to it are. Is it possible to have std::vector as underlying storage for the elements set container instead red-black tree involving a lot of heap allocations (maybe boost has something?) or do I have to invent it myself?

Plain std::vector and std::sort is not an option due to performance reasons and std::inplace_merge is prone to coding errors (invalidation of iterators, etc..).

EDIT: clarified the question

Answer 1

If you mean can you have

std::set<std::vector<MyType> > myIdealContainer;

then the answer is yes, provided you are able to meaningfully wrap the vector in something that makes it sortable (so set can order its members). Watch out for copying inefficiency though.

If you mean can I instantiate set with vector as the storage for a custom allocator, then I don't know how you would do that (or why you would want to).

If you mean can you treat a vector the same way you would a set, then the answer is no. if your dataset is small and matching the container member is cheap, use vector, preserve ordering on inserts and scan linearly for matches using std::find. If dataset is large and/or matching is expensive, use set.

Answer 2

for small size all containers are pretty efficient; just use set unless you know that you have a performance problem

in your case

using vector trades functionality (sorting, uniqueness) for storage size

using set does the opposite

If you need sorting and uniqueness then choose the container with that feature unless you are sure its a bad trade

Answer 3

No, it is not possible to specify the container to use for std::set, you can do that only with container adapters like std::queue or std::stack. std::set is one of the basic container with its own performance requirement. std::vector may not be the best container for all cases. For example, of you want a good lookup performance you would chose set, as find is O(log n) where as for vector it is O(n)

Answer 4

Maybe i've misunderstood you but if you are trying to use a std::set which has a std::vector for data storage (so all data of the set is actually stored int the vector), then the answer should be "no".
The reason for this is simply that the c++ std::set implementation is a binary search tree and a std::vector manages just a simple array/memory block.

Answer 5

There is no way to specify the underlying structure of an STL set. At best you can write an allocator that uses a vector to provide the memory used by set which may or may not be what you want.