In C++, std::set is a powerful associative container provided by the Standard Template Library (STL) that stores unique elements in a specific sorted order. Unlike a std::vector or std::list, where elements are stored in a linear sequence based on their insertion order, a std::set automatically organizes its data, ensuring that no two elements are identical and that the entire collection remains sorted at all times.

What Is std::set in C++?

The std::set container is defined in the <set> header file. It is typically implemented as a self-balancing binary search tree, most commonly a Red-Black Tree. This architectural choice gives it several distinct advantages, particularly in terms of search, insertion, and deletion performance, which all maintain a logarithmic time complexity of $O(\log n)$.

In a std::set, the value of an element is also its key. This means that you cannot change the value of an element once it is stored in the set; instead, you must remove the old value and insert a new one. This immutability of keys is essential for maintaining the integrity of the underlying tree structure.

Core Properties of the C++ Set Container

Understanding the behavior of std::set requires a grasp of its four fundamental properties:

  1. Unique Elements: A std::set cannot contain duplicate values. If you attempt to insert an element that is already present, the set will simply ignore the operation.
  2. Sorted Order: By default, elements are sorted in ascending order using the < operator (less than). However, this behavior can be customized using a comparison object.
  3. Immutability of Values: Once an element is placed inside a set, it is treated as a const value. You can add or remove elements, but you cannot modify them directly because changing a value could break the sorted order of the tree.
  4. Associative Nature: Elements are retrieved by their value (the key) rather than by their index. You cannot access the "third element" of a set using an index like mySet[2].

Getting Started: Syntax and Initialization

To use a set, you must include the appropriate header and specify the data type.