set class template — Set container with unique keys
template <typename Key, typename Compare = less<Key>, typename Alloc = allocator<Key> > class set { 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 set(const Compare& comp = Compare( ), const Alloc& = Alloc( )); template <class InputIterator> set(InputIterator first, InputIterator last, const Compare& comp = Compare( ), const Alloc& = Alloc( )); set(const set<Key,Compare,Alloc>& x); ~set( ); set<Key,Compare,Alloc>& operator=(const set<Key,Compare,Alloc>& x); allocator_type get_allocator( ) const; 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; 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); void erase(iterator position); size_type erase(const key_type& x); void erase(iterator first, iterator last); void swap(set<Key,Compare,Alloc>&); void clear( ); // Observers key_compare key_comp( ) const; value_compare value_comp( ) const; // Set operations 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 set
class template is a
standard container that contains an ordered set of unique keys of
type T
.
A set'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.
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 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 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
.