Computing › Stl › Containers › Associative ›

Set

A set is an associative container data structure which contains a sorted set of unique objects.

View version details

Contents

Definition
Description
Performance
Set Operations
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

Definition

The set template is defined in the standard header <set>, and in the nonstandard backward-compatibility header <set.h>.

#include <set>
namespace std {
       template < class T,
                 class Compare = less<T>,
                 class Allocator = allocator<T> >
       class set;
}

Description

Set is a Sorted Associative Container that stores values in an unspecified order and provides very fast lookup of the values.

A set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set.

The main characteristics of a set are:

unique element value (in a set, no two values are same,which means set is also an Unique Associative Container)
each Element value is itself a key
elements follow strict weak ordering at all times

A strict weak ordering is a binary relation $\inline <$ on a set $\inline S$ that is a strict partial order (a transitive relation that is irreflexive, or equivalently, that is asymmetric) in which the relation "neither $\inline a < b$ nor $\inline b < a$ " is transitive.

A short example declaring a set is:

set<string> setStr; // declar a string set

Performance

Sets perform operations of insertion, deletion, and testing if 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 bidirectional iterator.

Set is useful in situations where you need to keep track of a collection of elements and must rapidly look up if an element is contained.

Set Operations

Create, Copy, and Destroy Operations

Operation	Effect
set s	Creates an empty set without any elements
set s(op)	Creates an empty set that uses op as the sorting criterion
set s1(s2)	Creates a copy of another set of the same type (all elements are copied)
set s(beg,end)	Creates a set initialized by the elements of the range [beg,end)
set s(beg,end, op)	Creates a set with the sorting criterion op initialized by the elements of the range [beg,end)
s.~set()	Destroys all elements and frees the memory

Set	Effect
set<el>	A set that sorts with `less<>` (operator `<`)
set<el,op>	A set that sorts with op

Nonmodifying Operations of Sets

Operation	Effect
s.size()	Returns the number of elements
s.empty()	Returns if the container is empty (equivalent to size()==0)
s.max_size()	Returns the maximum number of elements possible
s1==s2	Returns if s1 is equal to s2
s1!=s2	Returns if s1 is not equal to s2 (equivalent to !(s1==s2))
s1<s2	Returns if s1 is less than s2
s1>s2	Returns if s1 is greater than s2 (equivalent to s2<s1)
s1<=s2	Returns if s1 is less than or equal to s2 (equivalent to !(s2<s1))
s1>=s2	Returns if s1 is greater than or equal to s2 (equivalent to !(s1<s2))

Special Search Operations of Sets

Operation	Effect
count(el)	Returns the number of elements with value el
find(el)	Returns the position of the first element with value el or end()
lower_bound(el)	Returns the first position, where el would get inserted (the first element >= el)
upper_bound(el)	Returns the last position, where el would get inserted (the first element > el)
equal_range(el)	Returns the first and last position, where el would get inserted (the range of elements == el)

Assignment Operations of Sets

Operation	Effect
s1=s2	Assigns all elements of s2 to s1
s1.swap(s2)	Swaps the data of s1 and s2
swap(s1,s2)	Same (as global function)

Iterator Operations of Sets

Operation	Effect
s.begin()	Returns a bidirectional iterator for the first element (elements are considered `const`)
s.end()	Returns a bidirectional iterator for the position after the last element (elements are considered `const`)
s.rbegin()	Returns a reverse iterator for the first element of a reverse iteration
s.rend()	Returns a reverse iterator for the position after the last element of a reverse iteration

Inserting and Removing Elements of Sets

Operation	Effect
s.insert(el)	Inserts a copy of el and returns the position of the new element and if it succeeded
s.insert(pos, el)	Inserts a copy of el and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
s.insert(beg,end)	Inserts a copy of all elements of the range [beg,end) (returns nothing)
s.erase(el)	Removes all elements with value el and returns the number of removed elements
s.erase(pos)	Removes the element at iterator position pos (returns nothing)
s.erase(beg,end)	Removes all elements of the range [beg,end) (returns nothing)
s.clear()	Removes all elements

References:

http://www.sgi.com
Nicolai M. Josuttis: "The C++ Standard Library"

Example:

Example - initialize a set

Problem

This example of program illustrates how to use an array in order to initialize a set.

Workings

#include <iostream>
#include <algorithm>
#include <iterator>
#include <set>
 
using namespace std;
 
int main()
{
  double s[5]={1.0, 4.4, 67.1, 1.0, 23.7, 67.1};
  std::set< double, std::less<double> > ds(s, s+5);
  std::ostream_iterator< double > output( cout, " " );
 
  cout <<"The set contains: ";
  std::copy(ds.begin(), ds.end(), output);
  cout <<endl;
 
  return 0;
}

Solution

Output:

The set contains: 1.0 4.4 23.7 67.1