Set

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.

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

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

View versions (1)

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.

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 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 1

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

Example 2

Problem

This program illustrates the construction of a set from an array of pairs and the use of the operators =, !=, ++, --, *, -> and == with set iterators.

Workings

#include <iostream>
#include <set>

using namespace std;

int main()
{
  // create an array of pairs
  pair <char, int> a[] =
  {
    pair <char, int>('C', 67),
    pair <char, int>('A', 65),
    pair <char, int>('E', 69),
    pair <char, int>('D', 68),
    pair <char, int>('B', 66)
  };
  
  // initialize a map with values from the array
  
  set<pair<char, int>>s(a,a+5);
  cout <<endl;

  set<pair<char, int>>::iterator it;
  for(it=s.begin();it!=s.end();++it)
    cout <<it->first<<" has an ASCII code of "<<it->second<<".\n";
  if(it==s.end())
    cout <<"The iterator is now pointing to one-past-the-last position.";

  it=s.end();
  cout <<endl;
  while(it!=s.begin())
  {
    --it;
    cout <<it->first<<" has an ASCII code of "<<it->second<<".\n";
  }
  if(it==s.begin())
    cout <<"The iterator is now pointing to the first position.";
  if(*it==*s.begin())
    cout <<"\nChecking component equality as well.";
  
  return 0;
}

Solution

Output:

A has an ASCII code of 65.
B has an ASCII code of 66.
C has an ASCII code of 67.
D has an ASCII code of 68.
E has an ASCII code of 69.
The iterator is now pointing to one-past-the-last position.

E has an ASCII code of 69.
D has an ASCII code of 68.
C has an ASCII code of 67.
B has an ASCII code of 66.
A has an ASCII code of 65.
The iterator is now pointing to the first position.
Checking component equality as well.

Example 3

Problem

This example of program shows the count() member function for sets.

Workings

#include <iostream>
#include <set>
#include <string>

using namespace std;

int main()
{
  // create an array of name strings, and a set of name strings from that    array
  string a[]={"X", "Y", "Z", "W"};
  set<string>s(a,a+4);

  cout <<"\nHere are the "<<s.size()<<" names in the set:\n";
  set<string>::iterator it =s.begin();
  while(it!=s.end())
    cout <<*it++<<" ";

  cout <<"\nThe number of times Y appears in the set is"<<s.count("Y")<<".";
  cout <<"\nThe number of times A appears in the set is"<<s.count("A")<<".";

  return 0;
}

Solution

Output:

Here are the 4 names in the set:
X Y Z W

The number of times Y appears in the set is 1.
The number of times A appears in the set is 0.

Example 4

Problem

This example of program shows the comparison of sets using the relational operators.

Workings

#include <iostream>
#include <set>
#include <iomanip>

using namespace std;

int main()
{
  char a[]={'A', 'B', 'C', 'D', 'E'};
  
  set<char> set1(a, a+4);
  set<char> set2(a, a+5);
  set<char> set3(a, a+5);

  // create three sets
  cout <<"The values in the first set: "  
  set<char>::iterator it = set1.begin();
  while(it!=set1.end())
    cout <<*it++<<" ";

  cout <<"The values in the second set: "
  it = set2.begin();
  while(it!=set2.end())
    cout <<*it++<<" ";

  cout<<"The values of the third set are the same as the second."

  // display the results of some set comparation

  cout <<"\nset1 < set2 = "<<boolalpha<<(set1<set2);
  cout <<"\nset1 <= set2 = "<<boolalpha<<(set1<=set2);
  cout <<"\nset1 > set2 = "<<boolalpha<<(set1>set2);
  cout <<"\nset1 >= set2 = "<<boolalpha<<(set1>=set2);
  cout <<"\nset1 == set2 = "<<boolalpha<<(set1==set2);
  cout <<"\nset1 != set2 = "<<boolalpha<<(set1!=set2);

  return 0;
}

Solution

Output:

The values in the first set:
A B C D

The values in the second set:
A B C D E

The valuess of the third set are the same as the second.

set1<set2 = true
set1<=set2 = true
set1>set2 = false
set1 >= set2 = false
set2 == set3 = true
set2 != set3 = false

Example 5

Problem

This program illustrates a const set iterator.

Workings

#include <iostream>
#include <string>
#include <set>

using namespace sdt;

void DisplayNames
(
  const set<string>& names //in
);

int main()
{
  cout <<"\nFirst we create an array of name strings, and\nthen a set "
         "of name strings from that array.";
  string a[] = {"Tom", "Dick", "Harry", "Alice"};
  set<string> setOfNames(a, a+4);

  DisplayNames(setOfNames);
  return 0;
}

void DisplayNames
(
  const set<string>& names //in
)
{
  //const input parameter requires const_iterator
  set<string>::const_iterator p = names.begin();
  cout <<"\nHere are the "<<names.size()<<" names in the set:\n";
  while (p != names.end()) 
    cout <<*p++<<endl;
}

Solution

Output:

First we create an array of name strings, and
then a set of name strings from that array.

Here are the 4 names in the set:
Alice
Dick
Harry
Tom