set (C++)

A set is an associative container data structure that is available as part of the C++ Standard Library (STL), and contains a sorted set of unique objects.

Although the abstract concept of a set does not necessarily imply an ordered collection, the standard library set data structure is always ordered. Its functionality in the STL is provided as a template class, such that any valid C++ object can be used with it. Sets are guaranteed to perform operations of insertion, deletion, and testing whether an element is in it, in logarithmic time - O(log n). As such, they are typically implemented using self-balancing binary search trees and support's bidirectional iterator.

Design

There are 2 types of sets available in the C++ STL: std::set and std::multiset.

• Set. Every element is unique, and insertions of values that are already present in the container are ignored.
• Multiset. Multiple occurrences of the same value are allowed.

Characteristics

• Unique element value: In a set, no two values are same.
• In a Set each Element value is itself a key.
• Elements follow strict weak ordering at all times.

Overview of functions

Function	Member	Description
	set::set (constructor)	Constructs the set from variety of sources.
	set::~set (destructor)	Destructs the set and the contained elements.
	set::operator=	Assigns values to the set.
	set::get_allocator	Returns the allocator used to allocate memory for the elements.
Iterator
	set::begin	Returns an iterator to the beginning of the set.
	set::end	Returns an iterator to the end of the set.
	set::rbegin	Returns a reverse iterator to the reverse beginning of the set.
	set::rend	Returns a reverse iterator to the reverse end of the set.
Modifier
	set::clear	Clears the contents.
	set::insert	Inserts elements.
	set::emplace (C++11)	Constructs elements in-place
	set::emplace_hint (C++11)	Constructs elements in-place using a hint.
	set::erase	Erases elements.
	set::swap	Swaps the contents with another set
Lookup
	set::count	Returns the number of elements matching specific key.
	set::find	Finds an element with specific key.
	set::equal_range	Returns a range of elements matching specific key.
	set::lower_bound	Returns an iterator to the first element not less than the given value.
	set::upper_bound	Returns an iterator to the first element greater than a certain value.
Capacity
	set::empty	Checks whether the set is empty.
	set::size	Returns the number of elements in the set.
	set::max_size	Returns the maximum possible number of elements in the set.
Observer	set::key_comp	Returns key comparison function.
	set::value_comp	Returns value comparison function. Since values are keys in sets, this function is essentially equivalent to key_comp.

Template Parameter

Parameter	Description	Default
Key	Every element is key, It is defined as std:set::key_type: in associative container and set::value_type in container.
compare	It is key comparison function defined as comp(a,b) returns bool.Returns true if first argument greater than second argument, otherwise false. It is strict weakly ordering operation.	less <key>
Alloc	It is Set's allocator , used for memory allocation.	alloc

See Also

• Set (computer science)
• multiset

External links

• C++ reference for std::set