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.

Constructors and destructor

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.

Overloaded operators

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.

Member functions for accessing values

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.

Member functions for reporting status

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.

Member functions for inserting one or more values

s.insert(kVal)
Try to insert kVal into s and return
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.

Member functions for deleting one or more values

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.

Member functions for counting and searching

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).

Miscellaneous member functions

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.)

Miscellaneous notes

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.

Sample programs

There are two groups of sample programs:

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.

Member function prototypes

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;