The set and the multiset are both containers that manage data
components that have keys, but the keys and the rest of the data are
not separated and placed in pair values like they are in maps
and multimaps. In the simplest cases the data in a set or multiset
component consists of just the key alone. The essential difference
between the set and the multiset is that in a set the keys must be
unique, while a multiset permits duplicate keys. This is analogous to
the situation with maps and multimaps. In both sets and multisets, the
sort order of components is the sort order of the keys, so the
components in a multiset that have duplicate keys may appear in any
order. Nearly everything said here about sets is also true of
multisets, with minor differences showing up in the count()
member function and one of the insert() member functions.
Default Constructor
- set<Ktype> s;
- Construct an empty set s which can hold values of type
Ktype.
Copy Constructor
There is, of course, only one copy constructor, but there are two
syntactic forms that invoke it, and both are shown.
- set<Ktype> s(otherSet);
- Construct s as a copy of otherSet, whose
component type must be Ktype. The copy has the same size as
the original.
- set<Ktype> s = otherSet;
- Copy constructor (alternate usage syntax).
Other Constructors
- set<Ktype> s(binPred);
- Construct an empty set s which can hold values of type
Ktype, and which uses binPred to sort keys.
- set<Ktype> s(inIterBegin, inIterEnd);
- Construct s containing values from the range
[inIterBegin,inIterEnd) in another (not necessarily set)
container, but whose component type is the same as the component type
of s.
- set<Ktype> s(inIterBegin, inIterEnd, binPred);
- Construct s containing values from the range
[inIterBegin,inIterEnd) in another (not necessarily set)
container, but whose component type is the same as the component type
of s, and which uses binPred to sort keys.
Destructor
- s.~set<Ktype>()
- Destroy all components of s and free the associated
memory.
Assignment operator
- s1 = s2
- Assign s2 to s1, and return the common value.
The set on the left of an assignment receives the values and size of
the one on the right.
Relational operators
Sets are compared in the "lexicographic ordering" sense. This
essentially means that the two sets are compared by comparing their
values pairwise, starting at the beginning, with each comparison
looking at two values in corresponding positions, until a determination
of the relationship between the two sets can be made. Only sets of the
same component type can be compared of course.
- s1 == s2
- Return true if s1 and s2 have the same
component type and the same size, and the components with the same
keys have the same value; otherwise return false.
- s1 != s2
- Return true if s1==s2 returns false;
otherwise return false.
- s1 < s2
- Return true if, in the pairwise comparison of values
from s1 and s2, in the first pair in which the two
values differ, the one from s1 is less than the one from
s2; otherwise return false.
- s1 <= s2
- Return true if either s1<s2 or
s1==s2 is true; otherwise return
false.
- s1 > s2
- Return true if s2<s1 is true;
otherwise return false.
- s1 >= s2
- Return true if either s1>s2 or
s1==s2 is true, otherwise return
false.
Each of the member functions in this section has both a
const and a non-const version.
- s.begin()
- Return an iterator (or const_iterator) pointing
to the first component of s.
- s.end()
- Return an iterator (or const_iterator) pointing
to one-past-the-last component of s.
- s.rbegin()
- Return a reverse_iterator (or
const_reverse_iterator) pointing to the last component of
s.
- s.rend()
- Return a reverse_iterator (or
const_reverse_iterator) pointing to one-before-the-first
component of s.
- s.max_size()
- Return a value of type size_type giving the maximum
possible size of s, which will depend on the size of the
component type <Ktype> of the set object, and the
amount of available memory.
- s.size()
- Return a value of type size_type giving the number of
values currently in s.
- s.empty()
- Return true if s is empty (contains zero
values); otherwise return false.
- s.insert(kVal)
-
Try to insert kVal into s and return
- for a set, a value of type pair<iterator,
bool>, with the iterator value pointing at the
new component, if it actually went into the set, and the
bool value being true if the insertion
succeeded; otherwise the iterator points at the value that was
already in the set, and the bool value is
false
- for a multiset, an iterator pointing at the newly inserted
component
- s.insert(iter, kVal)
- Try to insert kVal into s, using iter
as a "hint" for where the search for the insertion point should
begin, and return an iterator pointing to the new component, or to
the old component if the value was already in s.
- s.insert(inIterBegin, inIterEnd)
- Try to insert into s the values from the range
[inIterBegin,inIterEnd) in another (not necessarily set)
container, but whose values must be of the same type as the values of
s.
- s.clear()
- Delete all values of s. The size of s is
reduced to zero.
- s.erase(kVal)
- Delete all components for which the key is kVal and
return the number of deleted values (0 or 1). The size of s
is reduced by this value.
- s.erase(iter)
- Delete the value of s pointed to by iter. The
size of s is reduced by one.
- s.erase(iterBegin, iterEnd)
- Delete all values of s from the range
[iterBegin,iterEnd). The size of s is reduced by
the number of values in this range.
- s.count(kVal)
- Return the number of components in s which have their
key equal to kVal. This number is restricted to be 0 or 1
for a set, since keys are unique.
- s.find(kVal)
- Return an iterator pointing to the component in
s in which the key value is kVal, or to
one-past-the-last if this component does not exist.
- s.lower_bound(kVal)
- Return an iterator pointing to the first component in
s in which the key value is >= kVal, or to
one-past-the-last if this component does not exist. (This is the
first place that a component with a key value of kVal could
be inserted.)
- s.upper_bound(kVal)
- Return an iterator pointing to the first component in
s in which the key value is > kVal, or to
one-past-the-last if this component does not exist. (This is the last
place that a component with a key value of kVal could be
inserted.)
- s.equal_range(kVal)
- Return a pair with both components of type iterator
containing the same two iterators that would be returned by
lower_bound() and upper_bound() (in that
order).
- s.swap(otherSet)
- Exchange values in s with those in otherSet.
The sizes are swapped as well.
- s.key_comp()
- Return the function object used to compare values of type
Ktype.
- s.value_comp()
- Return the function object used to compare values of type
VType.
- s.getallocator()
- Return the allocator of s. (This is possibly the most
infrequently used of all member functions of the set class.)
- Implementation
- Standard C++ does not say how the STL containers and algorithms
must be implemented. It does, however, state certain constraints,
such as complexity constraints, to which each implementation must
adhere. Thus it is much better to base your programs on the STL's
performance guarantees, rather than upon any assumption about how a
particular feature, like the set or multiset classes, may be
implemented. As users, all we have a right to assume is that sets and
multisets sort their components automatically according to the sort
order of the component keys. That having been said, we can also say
that sets and multisets are generally implelmented using some
variation of a balanced binary search tree, not because the Standard
mandates this, but because that is the most logical choice, given the
perfomance constraints imposed on these two contiainers.
There are two groups of sample programs:
- The first group involves only STL sets and generic C++.
- The second group highlights the differences between sets and
multisets.
The programs should be studied in the sequence given, since the
description of each new sample program in the sequence mentions only
the new features illustrated for the first time in that particular
program, and features seen in earlier sample programs will continue to
reappear in later programs.
All of the programs have been compiled and run successfully under
Microsoft Visual Studio .NET 2005, unless otherwise noted.
Programs involving only sets (and generic C++)
- set01.cpp | Windows_executable | program_output (text)
- Illustrates a non-default set constructor, the size()
member function, and the default (bidirectional) iterator for the set
class, as well as member functions begin() and
end().
- set02.cpp | Windows_executable | program_output (text)
- Illustrates the set copy constructor and the overloaded
assignment operator for sets, as well as the default constructor for
the set class, and the empty() member function.
- set03.cpp | Windows_executable | program_output (text)
- Illustrates member function max_size(), and how the
maximum size for a set object depends on the size of its component
type.
- set04.cpp | Windows_executable | program_output (text)
- Illustrates how to use a built-in function object to alter the
sort order from the default used by the set class.
- set05.cpp | Windows_executable | program_output (text)
- Illustrates the use of operators =, ++,
--, ==, !=, -> and *
with set iterators.
- set06.cpp | Windows_executable | program_output (text)
- Illustrates more set construction and manipulation.
- set07.cpp | Windows_executable | program_output (text)
- Illustrates reverse iterators for the set class, as well as
member functions rbegin() and rend().
- set08.cpp | Windows_executable | program_output (text)
- Illustrates a typical use of a const iterator.
- set09.cpp | Windows_executable | program_output (text)
- Illustrates the count() member function.
- set10.cpp | Windows_executable | program_output (text)
- Illustrates the find() member function.
- set11.cpp | Windows_executable | program_output (text)
- Illustrates the insert() member function.
- set12.cpp | Windows_executable | program_output (text)
- Illustrates the clear() and erase() member
functions.
- set13.cpp | Windows_executable | program_output (text)
- Illustrates the lower_bound() member function.
- set14.cpp | Windows_executable | program_output (text)
- Illustrates the upper_bound() member function.
- set15.cpp | Windows_executable | program_output (text)
- Illustrates the equal_range() member function.
- set16.cpp | Windows_executable | program_output (text)
- Illustrates the swap() member function.
- set17.cpp | Windows_executable | program_output (text)
- Illustrates how the relational operators can be used to compare
one set with another.
- set18.cpp | Windows_executable | program_output (text)
- Illustrates a set in which each component is a class object
containing the name of a Canadian province and the name of its
capital city.
Programs highlighting the differences between sets and
multisets
Since the multiset interface is very nearly the same as the set
interface, the sample programs in this section are designed to
highlight the differences between sets and multisets.
- multiset01.cpp |
Windows_executable | program_output (text)
- Illustrates the difference in behavior when you try to insert
duplicate keys into a set and into a multiset.
- multiset02.cpp |
Windows_executable | program_output (text)
- Illustrates how to find the first of several duplicate keys and
then process all components with that key.
- multiset03.cpp |
Windows_executable | program_output (text)
- Illustrates how to store and retrieve book objects in a
multiset.
- multiset04.cpp |
Windows_executable | program_output (text)
- Illustrates the use of a multiset to record responses to a
polling question. First we create a multiset of responses, some of
which are, of course, duplicates. Then we display a summary of the
responses.
- multiset05.cpp |
Windows_executable | program_output (text)
- Displays first a set, then a multiset, of positive integer
values. In each case, the user is permitted to enter values of the
user's choice and the program provides the lower and upper bound of
each value entered, relative to the set of values, or the multiset of
values, as the case may be.
For enhanced readability in each of the prototypes given below, each
parameter in each parameter list appears on a separate line. Also, some
formatting liberties are taken, in the interest of greater readability.
For example, rather than aligning all prototypes at the left margin,
const and non-const versions of a member function are
aligned in such a way as to allow the reader to more easily compare the
two visually.
Template specification for the set class
template<class Ktype,
class BinaryPred less<Ktype>,
class Allocator = allocator<Ktype> >
class set { ... }
Constructors
explicit set(const BinaryPred& binPred = BinaryPred(),
const Allocator& a = Allocator());
template<class InIterator>
set(InIterator inIterBegin,
InIterator inIterEnd,
const BinaryPred& binPred = BinaryPred(),
const Allocator& a = Allocator());
Copy Constructor
set(const set<Ktype, BinaryPred, Allocator>& otherSet);
Destructor
~set();
begin
iterator begin();
const_iterator begin() const;
clear
void clear();
count
size_type count(const Ktype& kVal) const;
empty
bool empty() const;
end
iterator end();
const_iterator end() const;
equal_range
pair<iterator, iterator> equal_range(const Ktype& kVal) const;
erase
size_type erase(const Ktype& kVal);
void erase(iterator iter);
void erase(iterator iterBegin,
iterator iterEnd);
find
iterator find(const Ktype& kVal) const;
get_allocator
allocator_type get_allocator() const;
insert
pair<iterator, bool> insert(const Ktype& kVal);
iterator insert(iterator iter,
const Ktype& kVal);
template<class InIterator>
void insert(InIterator inIterBegin,
InIterator inIterEnd);
key_comp
key_compare key_comp() const;
lower_bound
iterator lower_bound(const Ktype& kVal) const;
max_size
size_type max_size() const;
rbegin
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
rend
reverse_iterator rend();
const_reverse_iterator rend() const;
size
size_type size() const;
swap
void swap(set<T, BinaryPred, Allocator>& otherSet);
upper_bound
iterator upper_bound(const Ktype& kVal) const;
value_comp
value_compare value_comp() const;