Cppin a Nutshell-13.41 <set>

13.41 <set>

The <set> header is one of the standard container template headers. It declares the set and multiset class templates and a few global function templates that operate on set and multiset objects.

A set is a container that stores keys. Looking up keys, inserting keys, and deleting keys can all be performed in logarithmic or better time. Sets support bidirectional iterators (not random access).

See Chapter 10 for information about containers.

multiset class template

Set container with duplicate keys

template <typename Key, typename Compare = less<Key>,
          typename Alloc = allocator<Key> >
class multiset {
public:
  typedef Key key_type;
  typedef Key value_type;
  typedef Compare key_compare;
  typedef Compare value_compare;
  typedef Alloc allocator_type;
  typedef typename Alloc::reference reference;
  typedef typename Alloc::const_reference const_reference;
  typedef  . . .  iterator;
  typedef  . . .  const_iterator;
  typedef  . . .  size_type;
  typedef  . . .  difference_type;
  typedef typename Alloc::pointer pointer;
  typedef typename Alloc::const_pointer const_pointer;
  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
   
  explicit multiset(const Compare& comp = Compare(  ), const Alloc& = Alloc(  ));
  template <class InputIterator>
  multiset(InputIterator first, InputIterator last,
           const Compare& comp = Compare(  ), const Alloc& = Alloc(  ));
  multiset(const multiset<Key,Compare,Alloc>& x);
  ~multiset(  );
  multiset<Key,Compare,Alloc>& operator=(const multiset<Key,Compare,Alloc>& x);
  allocator_type get_allocator(  ) const;
  // Iterators
  iterator begin(  );
  const_iterator begin(  ) const;
  iterator end(  );
  const_iterator end(  ) const;
  reverse_iterator rbegin(  );
  const_reverse_iterator rbegin(  ) const;
  reverse_iterator rend(  );
  const_reverse_iterator rend(  ) const;
   
  bool empty(  ) const;
  size_type size(  ) const;
  size_type max_size(  ) const;
   
  iterator insert(const value_type& x);
  iterator insert(iterator hintpos, const value_type& x);
  template <class InputIterator>
  void insert(InputIterator first, InputIterator last);
  void erase(iterator position);
  size_type erase(const key_type& x);
  void erase(iterator first, iterator last);
  void swap(multiset<Key,Compare,Alloc>&);
  void clear(  );
   
  key_compare key_comp(  ) const;
  value_compare value_comp(  ) const;
   
  iterator find(const key_type& x) const;
  size_type count(const key_type& x) const;
  iterator lower_bound(const key_type& x) const;
  iterator upper_bound(const key_type& x) const;
  pair<iterator,iterator> equal_range(const key_type& x) const;
};

The multiset class template is a standard container that contains an ordered set of keys of type T. The keys can be duplicated, that is, the multiset can contain more than one instance of a particular key.

A multiset's iterators are bidirectional. Note that keys are const in the set. You must not change the key while it is stored in a set. More precisely, you must not change the key in a way that alters its relative order with the other keys in the set. If you need to modify a key, erase the key from the set, modify the key, and insert the new key, as shown in Example 13-34 (in the set class template).

Within a multiset, keys are ordered in ascending order, according to the Compare template parameter (which can be a function pointer or functor that compares two objects of type Key and returns true if the first argument should come before the second). Keys do not need to be unique. When searching for keys, they are compared using the function or functor specified by the Compare template parameter. Two objects, a and b, are different if Compare(a, b) is true or Compare(b, a) is true. See set later in this section for a set container that stores unique keys.

Inserting into a multiset does not invalidate any iterators for that set or references to items in the set. Erasing an element invalidates only iterators and references that refer to that element.

Inserting into a set and searching for an element in a set usually take logarithmic time. Erasing a single element, given an iterator, takes constant time, amortized over many erasures.

The following are the member functions of multiset:

explicit multiset(const Compare& comp = Compare( ), const Alloc& = Alloc( ))

Constructs an empty multiset.

template <class InputIterator>

multiset(InputIterator first, InputIterator last, const Compare& comp = Compare( ), const Alloc& = Alloc( ))

Constructs an empty multiset and then copies all items in the range [first, last) into the new set. The complexity is linear if the keys in [first, last) are already sorted. If they are not sorted, the complexity is N log N, in which N is last - first.

multiset(const multiset<Key,Compare,Alloc>& x)

Constructs a new multiset and copies the allocator and all the items from x to the new set.

iterator begin( )

const_iterator begin( ) const

Returns an iterator that points to the first element of the set.

void clear( )

Erases every item in the set.

size_type count(const key_type& x) const

Returns the number of keys that are equivalent to x. The complexity is log(size( )) + r, in which r is the return value.

bool empty( ) const

Returns size( ) == 0.

iterator end( )

const_iterator end( ) const

Returns an iterator that points to one past the last element of the set.

pair<iterator,iterator> equal_range(const key_type& x) const

Returns the lower bound and upper bound as a pair:

std::make_pair(lower_bound(x), upper_bound(x))

The complexity is log(size( )).

void erase(iterator position)

size_type erase(const key_type& x)

void erase(iterator first, iterator last)

Erases one or more elements from the set. The first version erases the item at position in constant time (amortized over many calls). The second version erases the items equivalent to x, if any are present, returning a count of the number of items erased. The third version erases all elements in the range [first, last). The last two forms run in time proportional to log(size( )) + r, in which r is the number of items erased.

iterator find(const key_type& x) const

Searches for a key that is equivalent to x and returns an iterator that points to that key or end( ) if it is not found. If x occurs more than once, the iterator might point to any of its occurrences in the multiset. The complexity is log(size( )).

allocator_type get_allocator( ) const

Returns the set's allocator.

pair<iterator,bool> insert(const value_type& x)

iterator insert(iterator hintpos, const value_type& x)

template <class InputIterator>

void insert(InputIterator first, InputIterator last)

Inserts one or more items into the set. The first version inserts x in logarithmic time.

The second version inserts x using hintpos as a position hint. If x is inserted immediately after hintpos, the performance is constant (amortized over many insertions); at any other position, the performance is logarithmic.

The third version copies all the items in the range [first, last), which must be pointing to a different multiset object. If the items are already in the desired order, the performance is linear; otherwise, it is N log (size( ) + N), in which N is last - first.

key_compare key_comp( ) const

Returns the comparator function pointer or object. The key_compare type is the same as the Compare template parameter.

iterator lower_bound(const key_type& x) const

Returns an iterator that points to the first item in the set that does not come before x. That is, if x is in the set, the iterator points to the position of its first occurrence; otherwise, the iterator points to the first position where x should be inserted. The complexity is log(size( )).

size_type max_size( ) const

Returns the largest number of items that can be in the set.

reverse_iterator rbegin( )

const_reverse_iterator rbegin( ) const

Returns a reverse iterator that points to the last element of the set.

reverse_iterator rend( )

const_reverse_iterator rend( ) const

Returns a reverse iterator that points to one position before the first element of the set.

size_type size( ) const

Returns the number of items in the set.

void swap(multiset<Key,Compare,Alloc>&)

Swaps the contents of the set with the contents of x.

iterator upper_bound(const key_type& x) const

Returns an iterator that points to the first item in the set that comes after all occurrences of x. The complexity is log(size( )).

value_compare value_comp( ) const

Returns the comparator function pointer or functor object. The value_compare type is the same as the Compare template parameter.

multiset<Key,Compare,Alloc>& operator=(const multiset<Key,Compare,Alloc>& x)

Erases all the elements of the set and replaces them with copies of the elements of x.

Example

Example 13-34. One way to modify a key in a set

template <typename T, typename C, typename A>
void change_key(std::set<T, C, A>& s,
  const T& oldkey, const T& newkey)
{
  using std::set;
  typedef typename set<T, C, A>::iterator set_iterator;
  set_iterator i = s.find(oldkey);
  if (i != s.end(  )) {
    m.erase(i);
    m.insert(newkey);
  }
  // Exercise: What if newkey is already in s?
}

Within a set, keys are ordered in ascending order, according to the Compare template parameter (which can be a function pointer or functor that compares two objects of type Key and returns true if the first argument should come before the second). Keys must be unique, but note that uniqueness is determined only by calling Compare, not by using the == operator. That is, two objects, a and b, are different (and therefore can both be present in a single set object) if Compare(a, b) is true or Compare(b, a) is true. See multiset earlier in this section for a set container that can store non-unique keys.

Inserting into a set does not invalidate any iterators for that set or any references to items in the set. Erasing an element invalidates only iterators or references that refer to that element.

Inserting into a set and searching for an element in a set usually take logarithmic time. Erasing a single element, given an iterator, takes constant time, amortized over many erasures.

The following are the member functions of set:

explicit set(const Compare& comp = Compare( ), const Alloc& = Alloc( ))

Constructs an empty set.

template <class InputIterator>

set(InputIterator first, InputIterator last, const Compare& comp = Compare( ), const Alloc& = Alloc( ))

Constructs an empty set and then copies all items in the range [first, last) into the new set. The complexity is linear if the keys in [first, last) are already sorted. If they are not sorted, the complexity is N log N, in which N is last - first.

set(const set<Key,Compare,Alloc>& x)

Constructs a new set and copies the allocator and all the items from x to the new set.

iterator begin( )

const_iterator begin( ) const

Returns an iterator that points to the first element of the set.

void clear( )

Erases every item in the set.

size_type count(const key_type& x) const

Returns the number of keys that are equivalent to x. This value is always 0 or 1. The complexity is log(size( )).

bool empty( ) const

Returns size( ) == 0.

iterator end( )

const_iterator end( ) const

Returns an iterator that points to one past the last element of the set.

pair<iterator,iterator> equal_range(const key_type& x) const

Returns the lower bound and upper bound as a pair:

std::make_pair(lower_bound(x), upper_bound(x))

The complexity is log(size( )).

void erase(iterator position)

size_type erase(const key_type& x)

void erase(iterator first, iterator last)

Erases one or more elements from the set. The first version erases the item at position in constant time (amortized over many calls). The second version erases the item equivalent to x, if it is present, returning a count of the number of items erased, that is, 0 or 1. It runs in logarithmic time. The third version erases all elements in the range [first, last) in a time proportional to log(size( )) + r, in which r is last - first.

iterator find(const key_type& x) const

Searches for a key that is equivalent to x and returns an iterator that points to that key or end( ) if it is not found. The complexity is log(size( )).

allocator_type get_allocator( ) const

Returns the set's allocator.

pair<iterator,bool> insert(const value_type& x)

iterator insert(iterator hintpos, const value_type& x)

template <class InputIterator>

void insert(InputIterator first, InputIterator last)

Inserts one or more items into the set, but only if an equivalent key is not already present in the set. If the key is already present, the insert attempt is ignored. The first version attempts to insert x in logarithmic time.

The third version copies all the items in the range [first, last), which must be pointing to a different set object. If the items are already in the desired order, the performance is linear; otherwise, it is N log(size( ) + N), in which N is last - first.

key_compare key_comp( ) const

Returns the comparator function pointer or object. The key_compare type is the same as the Compare template parameter.

iterator lower_bound(const key_type& x) const

Returns an iterator that points to the first item in the set that does not come before x. That is, if x is in the set, the iterator points to its position; otherwise, the iterator points to the first position where x should be inserted. The complexity is log(size( )).

size_type max_size( ) const

Returns the largest number of items that can be in the set.

reverse_iterator rbegin( )

const_reverse_iterator rbegin( ) const

Returns a reverse iterator that points to the last element of the set.

reverse_iterator rend( )

const_reverse_iterator rend( ) const

Returns a reverse iterator that points to one position before the first element of the set.

size_type size( ) const

Returns the number of items in the set.

void swap(set<Key,Compare,Alloc>&)

Swaps the contents of the set with the contents of x.

iterator upper_bound(const key_type& x) const

Returns an iterator that points to the first item in the set that comes after x. The complexity is log(size( )).

value_compare value_comp( ) const

Returns the comparator function pointer or functor object. The value_compare type is the same as the Compare template parameter.

set<Key,Compare,Alloc>& operator=(const set<Key,Compare,Alloc>& x)

Erases all the elements of the set and replaces them with copies of the elements of x.

13.41 <set>

See Also

See Also

See Also

Example

Example 13-34. One way to modify a key in a set

See Also

See Also