Set (C++)

A set is an associative container data structure that is available as part of the C++ Standard Library (STL), and contains a sorted set of unique objects.

Although the abstract concept of a set does not necessarily imply an ordered collection, the standard library set data structure is always ordered. Its functionality in the STL is provided as a template class, such that any valid C++ object can be used with it. Sets are guaranteed to perform operations of insertion, deletion, and testing whether an element is in it, in logarithmic time - O(log n). As such, they are typically implemented using self-balancing binary search trees and support's bidirectional iterator

Types

There are 2 types of sets available in the C++ STL: std::set and std::multiset.

Set

In a set, every element is unique, and insertions of values that are already present in the container are ignored.

Multiset

In a multiset, multiple occurrences of the same value are allowed.

Characteristics

• Unique element value: In a set, no two values are same.
• Element value is itself a key.
• Elements follow strict weak ordering at all times.

Overview of functions

• Iterators
  • set::begin - Returns an iterator to the beginning of the set
  • set::end - Returns an iterator to the end of the set
  • set::rbegin - Returns a reverse iterator to the reverse beginning of the set
  • set::rend - Returns a reverse iterator to the reverse end of the set
• Capacity
  • set::empty - Checks whether the set is empty
  • set::size - Returns the number of elements in the set.
  • set::max_size - Returns the maximum possible number of elements in the set.
• Modifiers
  • set::clear - Clears the contents
  • set::insert - Inserts elements
  • set::emplace (C++11) - Constructs elements in-place
  • set::emplace_hint (C++11) - Constructs elements in-place using a hint
  • set::erase - Erases elements
  • set::swap - Swaps the contents with another set
• Lookup
  • set::count - Returns the number of elements matching specific key
  • set::find - Finds an element with specific key
  • set::equal_range - Returns a range of elements matching specific key
  • set::lower_bound - Returns an iterator to the first element not less than the given value
  • set::upper_bound - Returns an iterator to the first element greater than a certain value
• Observers
  • set::key_comp - Constant time function which returns Key comparison function.
  • set::value_comp - Constant time function which compares keys and returns Key comparison function.

External links

• C++ reference for std::set