C++ Associative Container - Sets and Multisets

in #cpp3 years ago

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

Sort:  

Congratulations @jd3! You have completed some achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of posts published

Click on any badge to view your own Board of Honor on SteemitBoard.

To support your work, I also upvoted your post!
For more information about SteemitBoard, click here

If you no longer want to receive notifications, reply to this comment with the word STOP

Upvote this notification to help all Steemit users. Learn why here!