<set>

std::set

template<
  class Key,
  class Compare = std::less<Key>
  class Allocator = std::allocator<Key>
> class set;

// Since C++17
namespace pmr {
  template<
    class Key,
    class Compare = std::less<Key>
  > using set = std::set<Key, Compare, std::pmr::polymorphic_allocator<Key>>;
}

std::set is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as Red–black trees.

Everywhere the standard library uses the Compare requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).

std::set meets the requirements of Container, AllocatorAwareContainer, AssociativeContainer and ReversibleContainer.

All member functions of std::set are constexpr: it is possible to create and use std::set objects in the evaluation of a constant expression. However, std::set objects generally cannot be constexpr, because any dynamically allocated storage must be released in the same evaluation of constant expression. (Since C++26)

• Member Types

Type	Definition
key_type	Key
value_type	Key
size_type	Unsigned integer type (usually std::size_t)
difference_type	Signed integer type (usually std::ptrdiff_t)
key_compare	Compare
value_compare	Compare
allocator_type	Allocator
reference	value_type&
const_reference	const value_type&
pointer	Allocator::pointer (until C++11)/std::allocator_traits::pointer (since C++11)
const_pointer	Allocator::const_pointer (until C++11)/std::allocator_traits::const_pointer (since C++11)
iterator	Constant LegacyBidirectionalIterator and ConstexprIterator(since C++26) to value_type
const_iterator	LegacyBidirectionalIterator and ConstexprIterator(since C++26) to const value_type
reverse_iterator	std::reverse_iterator
const_reverse_iterator	std::reverse_iterator<const_iterator>
node_type (since C++17)	a specialization of node handle representing a container node
insert_return_type (since C++17)

• Member functions

function	definition
(constructor)	constructs the set
(destructor)	destructs the set
operator=	assigns values to the container
get_allocator	return the associated allocator
begin/cbegin(C++11)	returns an iterator to the beginning
end/cend(C++11)	returns an iterator to the end
rbegin/crbegin(C++11)	returns a reverse iterator to the beginning
rend/crend(C++11)	returns a reverse iterator to the end
empty	checks whether the container is empty
size	returns the number of elements
max_size	returns the maximum possible number of elements
clear	clears the contents
insert	inserts elements or nodes(since C++17)
insert_range (C++23)	inserts a range of elements
emplace (C++11)	constructs element in-place
emplace_hint (C++11)	constructs elements in-place using a hint
erase	erases elements
swap	swaps the contents
extract (C++17)	extracts nodes from the container
merge (C++17)	splices nodes from another container
count	returns the number of elements matching specific key
find	finds element with specific key
contains(C++20)	checks if the container contains element with specific key
equal_range	returns range of elements matching a specific key
lower_bound	returns an iterator to the first element not less than the given key
upper_bound	returns an iterator to the first element greater than the given key
key_comp	returns the function that compares keys
value_comp	returns the function that compares keys in objects of type value_type

• Non-member functions

function	defeinition
operator==	lexicographically compares the values of two sets
operator!= (removed in C++20)	lexicographically compares the values of two sets
operator< (removed in C++20)	lexicographically compares the values of two sets
operator<= (removed in C++20)	lexicographically compares the values of two sets
operator> (removed in C++20)	lexicographically compares the values of two sets
operator>= (removed in C++20)	lexicographically compares the values of two sets
operator<=> (C++20)	lexicographically compares the values of two sets
std::swap	specializes the std::swap algorithm
erase_if (C++20)	erases all elements satisfying specific criteria

• Example

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <set>
#include <string_view>

template <typename T>
std::ostream &operator<<(std::ostream &out, const std::set<T> &set) {
  if (set.empty()) {
    return out << "{}";
  }

  out << "{ " << *set.begin();
  std::for_each(std::next(set.begin()), set.end(),
                [&out](const T &element) { out << ", " << element; });
  return out << " }";
}

int main() {
  std::set<int> set{1, 5, 3};
  std::cout << set << '\n';

  set.insert(2);
  std::cout << set << "\n";

  set.erase(1);
  std::cout << set << "\n\n";

  std::set<int> keys{3, 4};
  for (int key : keys) {
    if (set.contains(key))
      std::cout << set << " does contain " << key << "\n";
    else
      std::cout << set << " doesn't contain " << key << "\n";
  }
  std::cout << "\n";

  std::string_view word = "element";
  std::set<char> characters(word.begin(), word.end());
  std::cout << "There are " << characters.size() << " unique characters in "
            << std::quoted(word) << ":\n"
            << characters << "\n";
}


/**
 * { 1, 3, 5 }
   { 1, 2, 3, 5 }
   { 2, 3, 5 }

   { 2, 3, 5 } does contain 3
   { 2, 3, 5 } doesn't contain 4

   There are 5 unique characters in "element":
   { e, l, m, n, t }
 */

std::multiset

template<
  class Key,
  class Compare = std::less<Key>,
  class Allocator = std::allocator<Key>
> class multiset;

// since C++17
namespace pmr {
  template<
    class Key,
    class Compare = std::less<Key>
  > using multiset = std::multiset<Key, Compare, std::pmr::polymorphoc_allocator<Key>>;
}

std::multiset is an associative container that contains a sorted set of objects of type Key. Unlike set, multiple keys with equivalent values are allowed. Sorting is done using the key comparison function Compare. Search, insertion, and removal operations have logarithmic complexity.

Everywhere the standard library uses the Compare requirements, equivalence is determined by using the equivalence relation as described on Compare. In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).

The order of the elements that compare equivalent is the order of insertion and does not change. (since C++11)

All member functions of std::multiset are constexpr: it is possible to create and use std::multiset objects in the evaluation of a constant expression. However, std::multiset objects generally cannot be constexpr, because any dynamically allocated storage must be released in the same evaluation of constant expression. (since C++26)

• Member types

Type	Definition
key_type	Key
value_type	Key
size_type	Unsigned integer type (usually std::size_t)
difference_type	Signed integer type (usually std::ptrdiff_t)
key_compare	Compare
value_compare	Compare
allocator_type	Allocator
referenc	e value_type&
const_reference	const value_type&
pointer	Allocator::pointer (until C++11)/std::allocator_traits::pointer (since C++11)
const_pointer	Allocator::const_pointer (until C++11)/std::allocator_traits::const_pointer (since C++11)
iterator	Constant LegacyBidirectionalIterator and ConstexprIterator(since C++26) to value_type
const_iterator	LegacyBidirectionalIterator and ConstexprIterator(since C++26) to const value_type
reverse_iterator	std::reverse_iterator
const_reverse_iterator	std::reverse_iterator<const_iterator>
node_type (since C++17)	a specialization of node handle representing a container node

• Member functions

Function	Definition
(constructor)	constructs the multiset
(destructor)	destructs the multiset
operator=	assigns values to the container
get_allocator	returns the associated allocator
begin/cbegin(C++11)	returns an iterator to the beginning
end/cend(C++11)	returns an iterator to the end
rbegin/crbegin(C++11)	returns a reverse iterator to the beginning
rend/crend(C++11)	returns a reverse iterator to the end
empty	checks whether the container is empty
size	returns the number of elements
max_size	returns the maximum possible number of elements
clear	clears the contents
insert	inserts elements (or nodes since C++17)
insert_range (C++23)	inserts a range of elements
emplace(C++11)	constructs element in-place
emplace_hint (C++11)	constructs elements in-place using a hint
erase	erases elements
swap	swap the contents
extract(C++17)	extracts nodes from the container
merge(C++17)	splices nodes from another container
count	returns the number of elements matching specific key
find	finds element with specific key
contains(C++20)	checks if the container contains element with specific key
equal_range	returns range of elements matching a specific key
lower_bound	returns an iterator to the first element not less than the given key
upper_bound	returns an iterator to the first element greater than the given key
key_comp	returns the function that compares keys
value_comp	returns the function that compares keys in objects of type value_type

• Non-member functions

Function	Definition
operator==	lexicographically compares the values of two multisets
operator!= (removed in C++20)	lexicographically compares the values of two multisets
operator< (removed in C++20)	lexicographically compares the values of two multisets
operator<= (removed in C++20)	lexicographically compares the values of two multisets
operator> (removed in C++20)	lexicographically compares the values of two multisets
operator>= (removed in C++20)	lexicographically compares the values of two multisets
operator<=> (C++20)	lexicographically compares the values of two multisets
std::swap	specializes the std::swap algorithm
erase_if (C++20)	erases all elements satisfying specific criteria

Reference

1.cppreference