C++ header series of set details

Introduction to the

The header file contains the set and multiset templates. The concepts described here are very similar to map, and even the member functions are almost identical, so this essay will be very short.

set

set is an ordered set of only 1, which is similar to map in nature:

Correlation between Element singleness The dynamic growth order

Another important feature is:

Key and Value are the same object (self-mapping)

set == map

To define set, you only need to pass in one type parameter, which is key and value. In fact, set is a special case of map. Although set does not have key-value pairs as an element form, key of set is itself value. The key-value pair mapping on map can be seen here as a mapping of the element itself to itself. So there should be a big overlap in the implementation. Conceptually, set can be fully implemented by map as a container adapter. But the reason for not doing that, I think, is mostly to save memory, because the value value is completely unnecessary.

implementation

Looking at the C++ header file in VS 2013, you can see that both set and map are directly inherited _Tree class (red-black tree) without any other private members. This idea is supported by the reusability of the code.

Different from map

If anything, set does not provide the ability to modify elements -- no operator[], at functions.

When an element is inserted into a collection, it can only be deleted and cannot be re-assigned. Perhaps the action of modifying elements is so unusual for the concept of collections that the standard library has removed it.

multiset

Like multimap, this class template is equivalent to a version of set that supports multiple key values.