Sets
A set is a type of associative container (fast searching) in which ever element is identified by its value, thus making every element unique with no duplicates.
In a set, the value of the element is also the key. Since every element must be different, you can only add or delete elements from the set. A modification to a set element would essentially consist of deleting and re-adding.
set<int> my_set;
my_set.insert(1); // 1 = key and 1 = value
The elements in the set are ordered sequentially by default. Ie. numbers are ordered from smallest to largest and strings are ordered alphabetically. For a list of all the member functions see: http://www.cplusplus.com/reference/set/set/
Here is an example of a set
#include <iostream>
#include <set>
#include <iterator>
#include <ctime>
#include <cstdlib>
/* A set is typically a binary tree of elements sorted
- sequentaily, in which no element may exist
- twice.
*/
using namespace std;
void set_ex() {
/* Create set of type int */
set<int> my_set;
/* Add random (between 0 and 100) numbers to set */
srand(time(0));
for(int i = 0; i <= 20; i++) {
my_set.insert(rand() % 100);
}
/* Create iterator of type set<int> */
set<int>::iterator itr;
/* Print my_set1 /
cout << "my_set : \n";
for (itr = my_set.begin(); itr != my_set.end(); itr++) {
/ dereference itr */
cout << "\t" << *itr << endl;
}
}
int main()
{
set_ex();
return 0;
}
Output
my_set :
0
2
20
23
32
36
43
54
55
56
58
63
65
87
93
94
98
Here is an example of a set using a reverse sorting algorithm instead of the default
#include <iostream>
#include <set>
#include <iterator>
#include <ctime>
#include <cstdlib>
using namespace std;
struct ReverseSort {
bool operator()(const int& first, const int& second) {
return (second < first);
}
};
void set_reverse_sort_ex() {
/* Create set with a reverse sorting algorithm */
set<int, ReverseSort> my_set;
/* Fill with random numbers*/
srand(time(0));
for (int i = 0; i <= 20; i++) {
my_set.insert(rand() % 100);
}
set<int>::iterator itr;
cout << "my_set : \n";
for(itr = my_set.begin(); itr != my_set.end(); itr++) {
cout << "\t" << *itr << endl;
}
}
int main()
{
set_reverse_sort_ex();
return 0;
}
Output
my_set :
98
88
87
83
72
71
67
62
54
35
32
29
27
20
19
17
10
Here is another example of a set showing the erase member function
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
void set_erase_ex() {
set<int> my_set;
/* my_set = 0 10 20 30 40 50 60 70 80 90 100 */
for (int i = 0; i <= 100; i += 10) {
my_set.insert(i);
}
set<int>::iterator itr;
cout << "Full version of my_set :\n";
for (itr = my_set.begin(); itr != my_set.end(); itr++) {
cout << *itr << endl;
}
/* Grap a section within the set */
set<int>::iterator lower = my_set.lower_bound(30);
set<int>::iterator upper = my_set.upper_bound(70);
/* Delete this section */
my_set.erase(lower, upper);
/* You can also erase a signle element */
my_set.erase(100);
/* Print again */
cout << "New version of my_set :\n";
for (itr = my_set.begin(); itr != my_set.end(); itr++) {
cout << *itr << endl;
}
}
int main()
{
set_erase_ex();
return 0;
}
Output
Full version of my_set :
0
10
20
30
40
50
60
70
80
90
100
New version of my_set :
0
10
20
80
90
Multisets
A multiset is a set that can hold multiple copies of the same element. Un-like a regular set, a multiset can hold the same element multiple times. Multisets and sets share the same member function names. For a list of all the member functions see: http://www.cplusplus.com/reference/set/multiset/
Ex Code
#include <iostream>
#include <set>
#include <iterator>
#include <string>
using namespace std;
void multiset_ex() {
multiset<string> names;
names.insert("Victor");
names.insert("Roger");
names.insert("Greg");
names.insert("Andrea");
names.insert("Wilbur");
names.insert("Victor");
names.insert("Andrea");
names.insert("Victor");
names.insert("Greg");
/* Go backwards this time */
multiset<string>::reverse_iterator rit;
/* Print out names in reverase alphebetical order */
for (rit = names.rbegin(); rit != names.rend(); rit++) {
cout << *rit << endl;
}
}
int main() {
multiset_ex();
return 0;
}
Output
Wilbur
Victor
Victor
Victor
Roger
Greg
Greg
Andrea
Andrea
The order of the duplicates do not matter since they are same values/keys