Set Implementation in C++?

Question

As per the following link - http://www.cplusplus.com/reference/set/set/ sets in C++'s STL are typically implemented as Binary Search Trees, I am able to gauge the behavior of the data type in cases such as sets of ints or characters or floats or strings for that matter as in these cases it is easy to see the BST ordering being imposed on set elements, but considering the binary search tree data structure implementation of sets I am not able to visualize how are the following data types implemented using binary search trees:

1. set<vector<int>> or set<vector<string>> or set<vector<double>> or set<list<int>>
2. set<map<int, int>>
3. set<stack<int>>

or for that matter many other data types, how is the memory allocated for these types and how is the ordering maintained.

Also I am not able to figure out the following, whenever a new vector is added into the set, does the set data type internally check all the vectors in the set for similarity or all the maps for similarity, these are somethings I am not able to figure out. It would be great if someone can help me visualize these concepts.

Answer 1

The set uses a strict weak ordering to determine the position of each element. This is done using std::less<T> by default. This will result in a call to operator<(const T&, const T&). Now, containers such as std::vector have such operators, which just perform a lexicographical comparison of all the elements. That is how an std::set<std::vector<int>> can work out of the box.

When a new element is inserted, the set does not have to check all the elements. Insertion is a logarithmic complexity operation, which is why the implementation tends to be a self-balancing binary tree (I phrase it with this rather odd causality because the C++ standard does not specify what the implementation should be like, just how it should behave.)

Answer 2

A set<T> always works the same, regardless of what concrete type T is. On an insertion, it figures out where in the tree^* to place the new element by comparing it with various existing elements using std::less<T> (which by default calls operator<). If operator< isn't overloaded for T, then it won't compile.

Therefore, the details of how to order instances of T are abstracted from the details of how to maintain a set.

---

_{* Note that std::set doesn't have to use a tree; that's just a typical implementation.}