What is the difference between std::set and std::vector, which one is more efficient and why?

Question

I'm curious as to why libstdc++ is using a RB-tree to implement std::set (details here
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/set and here https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/include/bits/stl_tree.h ),
when there are faster alternatives?

I'm mainly curious, because from all the people I've asked there hasn't been a single answer in favor of RB-trees, other than "they're already popular" or "easy to implement".

If you'd like more details on that, here's a link to my question on stackexchange http://cs.stackexchange.com/questions/41969/why-are-red-black-trees-so-popular,
where nobody has yet answered as well.

Using a variant of B-tree (or (a,b)-tree) should be faster, and everyone seems to suggest so, which makes me wonder what is the reason for picking RB-trees? This is not a question about their theoretical speed, but about real world behavior on real hardware with respect to CPU caches, etc.

Answer 1

1.A set is ordered. It is guaranteed to remain in a specific ordering, according to a functor that you provide. No matter what elements you add or remove (unless you add a duplicate, which is not allowed in a set), it will always be ordered(from Documentation).
2.A vector has exactly and only the ordering you explicitly give it. Items in a vector are where you put them. If you put them in out of order, then they're out of order; you now need to sort the container to put them back in order.
3.set has relatively limited use. With proper discipline, one could insert items into a vector and keep it ordered. However, if you are constantly inserting and removing items from the container, vector will run into many issues. It will be doing a lot of copying/moving of elements and so forth, since it is effectively just an array.Sometimes it gives fatal error too just because of these operations for big operations.
4.The time it takes to insert an item into a vector is proportional to the number of items already in the vector. The time it takes to insert an item into a set is proportional to the log of the number of items. If the number of items is large, that's a huge difference. Log(100,000) is 5; that's a major speed improvement. The same goes for removal.
5.if you do all of your insertions at once, at initialization time, then there's no problem. You can insert everything into the vector, sort it using sort(), and then use standard algorithms for sorted vectors to find elements and iterate over the sorted list. And while iteration over the elements of a set isn't exactly slow, iterating over a vector is faster.

So there are cases where a sorted vector beats a set. You really shouldn't bother with the expense of this kind of optimization unless you know that it is necessary. So use a set unless you have experience with the kind of system you're writing (and thus know that you need that performance) or have profiling data in hand that tells you that you need a vector and not a set.I suggest you to go for set then vector.
Consider this Problem with its solution for better difference :
Link: https://discuss.codechef.com/questions/81063/ksum-editorial