SGI-STL defines key-value pairs using the following template:

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    
    pair(): first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b): first(a), second(b) {}
};

The type alias typedef pair<const key, T> value_type; is used extensively in associative containers. All four associative containers discussed here utilize red-black trees as their underlying data structure, maintaining elements in sorted order.

Set Container

When inserting values into a set, the container internally stores them as key-value pairs <value, value>. Sets automatically remove duplicate elements and maintain sorted order. Elements within a set are immutable to preserve ordering, though new elements can be inserted and existing ones removed. By default, sets traverse elements in ascending order using in-order traversal.

Set Construction

• Default constructor creates an empty set
• Range constructor initializes from [first, last)
• Copy constructor duplicates existing set

Set Iterators

Standard iterators include forward and reverse variants, with const versions available. Example usage:

#include <iostream>
#include <set>
using namespace std;

int main()
{
    int values[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
    set<int> num_set(values, values + sizeof(values) / sizeof(values[0]));
    
    set<int>::iterator iter = num_set.begin();
    while (iter != num_set.end())
    {
        cout << *iter << " ";
        iter++;
    }
    cout << endl;
    return 0;
}

Set Operations

Insert Method pair<iterator,bool> insert (const value_type& val) returns both an iterator and insertion status:

pair<set<int>::iterator, bool> result = num_set.insert(100);
cout << *(result.first) << " " << result.second << endl;

• Successful insertion returns iterator to new element and true
• Duplicate element returns iterator to existing element and false

Erase Method Remove elements by value or iterator:

num_set.erase(100);
set<int>::iterator pos = num_set.find(1);
num_set.erase(pos);

Count Method Returns 1 if element exists, 0 otherwise. Primarily used for existence checks.

Bound Methods

• lower_bound(x) returns iterator to first element ≥ x
• upper_bound(x) returns iterator to first element > x

Combined usage to range deletion:

num_set.erase(num_set.lower_bound(1), num_set.upper_bound(5));

Multiset Container

Similar to set but allows duplicate elements. The insert method returns only an iterator without boolean status.

Map Container

Stores key-value pairs <key, T> with sorting based solely on keys. Keys are unique and immutable. Provides [] operator for direct value access.

Map Construction

Uses same construction paterns as set.

Map Iterators

Iterator behavior identical to set.

Map Operations

Insert Method Multiple insertion approaches:

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
    map<string, string> dict;
    
    dict.insert(pair<string, string>("apple", "苹果"));
    dict.insert(make_pair("banana", "香蕉"));
    dict.insert({ "fruit","水果" });
    
    for (auto& entry : dict)
    {
        cout << entry.first << " : " << entry.second << endl;
    }
    return 0;
}

Subscript Operator mapped_type& operator[] (const key_type& k) provides key-based access:

string items[] = { "香蕉", "苹果", "葡萄" };
map<string, int> counter;

for (auto& item : items)
{
    counter[item]++;
}

for (auto& entry : counter)
{
    cout << entry.first << " " << entry.second << endl;
}

The operator implementation follows this logic: (*((this->insert(make_pair(k, mapped_type()))).first)).second

Multimap Container

Allows duplicate keys while maintaining other map characteristics.