set Class

The STL container class set is used for the storage and retrieval of data from a collection in which the values of the elements contained are unique and serve as the key values according to which the data is automatically ordered. The value of an element in a set may not be changed directly. Instead, you must delete old values and insert elements with new values.

template <
    class Key, 
    class Traits=less<Key>, 
    class Allocator=allocator<Key> 
>
class set

Parameters

  • Key
    The element data type to be stored in the set.

  • Traits
    The type that provides a function object that can compare two element values as sort keys to determine their relative order in the set. This argument is optional, and the binary predicate less <Key> is the default value.

  • Allocator
    The type that represents the stored allocator object that encapsulates details about the set's allocation and deallocation of memory. This argument is optional, and the default value is allocator*<Key>.*

Remarks

An STL set is:

  • An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value. Further, it is a simple associative container because its element values are its key values.

  • Reversible, because it provides a bidirectional iterator to access its elements.

  • Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.

  • Unique in the sense that each of its elements must have a unique key. Since set is also a simple associative container, its elements are also unique.

A set is also described as a template class because the functionality it provides is generic and independent of the specific type of data contained as elements. The data type to be used is, instead, specified as a parameter in the class template along with the comparison function and allocator.

The choice of container type should be based in general on the type of searching and inserting required by the application. Associative containers are optimized for the operations of lookup, insertion and removal. The member functions that explicitly support these operations are efficient, performing them in a time that is on average proportional to the logarithm of the number of elements in the container. Inserting elements invalidates no iterators, and removing elements invalidates only those iterators that had specifically pointed at the removed elements.

The set should be the associative container of choice when the conditions associating the values with their keys are satisfied by the application. The elements of a set are unique and serve as their own sort keys. A model for this type of structure is an ordered list of, say, words in which the words may occur only once. If multiple occurrences of the words were allowed, then a multiset would be the appropriate container structure. If values need to be attached to a list of unique key words, then a map would be an appropriate structure to contain this data. If instead the keys are not unique, then a multimap would be the container of choice.

The set orders the sequence it controls by calling a stored function object of type key_compare. This stored object is a comparison function that may be accessed by calling the member function key_comp. In general, the elements need to be merely less than comparable to establish this order so that, given any two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements. On a more technical note, the comparison function is a binary predicate that induces a strict weak ordering in the standard mathematical sense. A binary predicate f(x,y) is a function object that has two argument objects x and y and a return value of true or false. An ordering imposed on a set is a strict weak ordering if the binary predicate is irreflexive, antisymmetric, and transitive and if equivalence is transitive, where two objects x and y are defined to be equivalent when both f(x,y) and f(y,x) are false. If the stronger condition of equality between keys replaces that of equivalence, then the ordering becomes total (in the sense that all the elements are ordered with respect to each other) and the keys matched will be indiscernible from each other.

The iterator provided by the set class is a bidirectional iterator, but the class member functions insert and set have versions that take as template parameters a weaker input iterator, whose functionality requirements are more minimal than those guaranteed by the class of bidirectional iterators. The different iterator concepts form a family related by refinements in their functionality. Each iterator concept has its own set of requirements, and the algorithms that work with them must limit their assumptions to the requirements provided by that type of iterator. It may be assumed that an input iterator may be dereferenced to refer to some object and that it may be incremented to the next iterator in the sequence. This is a minimal set of functionality, but it is enough to be able to talk meaningfully about a range of iterators [First, Last) in the context of the class's member functions.

Constructors

set

Constructs a set that is empty or that is a copy of all or part of some other set.

Typedefs

allocator_type

A type that represents the allocator class for the set object.

const_iterator

A type that provides a bidirectional iterator that can read a const element in the set.

const_pointer

A type that provides a pointer to a const element in a set.

const_reference

A type that provides a reference to a const element stored in a set for reading and performing const operations.

const_reverse_iterator

A type that provides a bidirectional iterator that can read any const element in the set.

difference_type

A signed integer type that can be used to represent the number of elements of a set in a range between elements pointed to by iterators.

iterator

A type that provides a bidirectional iterator that can read or modify any element in a set.

key_compare

A type that provides a function object that can compare two sort keys to determine the relative order of two elements in the set.

key_type

The type describes an object stored as an element of a set in its capacity as sort key.

pointer

A type that provides a pointer to an element in a set.

reference

A type that provides a reference to an element stored in a set.

reverse_iterator

A type that provides a bidirectional iterator that can read or modify an element in a reversed set.

size_type

An unsigned integer type that can represent the number of elements in a set.

value_compare

The type that provides a function object that can compare two elements to determine their relative order in the set.

value_type

The type describes an object stored as an element of a set in its capacity as a value.

Member Functions

begin

Returns an iterator that addresses the first element in the set.

cbegin

Returns a const iterator that addresses the first element in the set.

cend

Returns a const iterator that addresses the location succeeding the last element in a set.

clear

Erases all the elements of a set.

count

Returns the number of elements in a set whose key matches a parameter-specified key.

crbegin

Returns a const iterator addressing the first element in a reversed set.

crend

Returns a const iterator that addresses the location succeeding the last element in a reversed set.

emplace

Inserts an element constructed in place into a set.

emplace_hint

Inserts an element constructed in place into a set, with a placement hint.

empty

Tests if a set is empty.

end

Returns an iterator that addresses the location succeeding the last element in a set.

equal_range

Returns a pair of iterators respectively to the first element in a set with a key that is greater than a specified key and to the first element in the set with a key that is equal to or greater than the key.

erase

Removes an element or a range of elements in a set from specified positions or removes elements that match a specified key.

find

Returns an iterator addressing the location of an element in a set that has a key equivalent to a specified key.

get_allocator

Returns a copy of the allocator object used to construct the set.

insert

Inserts an element or a range of elements into a set.

key_comp

Retrieves a copy of the comparison object used to order keys in a set.

lower_bound

Returns an iterator to the first element in a set with a key that is equal to or greater than a specified key.

max_size

Returns the maximum length of the set.

rbegin

Returns an iterator addressing the first element in a reversed set.

rend

Returns an iterator that addresses the location succeeding the last element in a reversed set.

size

Returns the number of elements in the set.

swap

Exchanges the elements of two sets.

upper_bound

Returns an iterator to the first element in a set with a key that is greater than a specified key.

value_comp

Retrieves a copy of the comparison object used to order element values in a set.

Operators

operator=

Replaces the elements of a set with a copy of another set.

Requirements

Header: <set>

Namespace: std

See Also

Reference

<set>

Thread Safety in the C++ Standard Library

Standard Template Library

Concepts

Containers