# Set

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

## 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 on a set that is a strict partial order (a transitive relation that is irreflexive, or equivalently, that is asymmetric) in which the relation "neither nor " 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

Last Modified: 23 Dec 11 @ 16:14 Page Rendered: 2022-03-14 16:02:34