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