Block 2 Associative Containers

Associative containers store elements sorted by key and allow fast searching, insertion, and deletion.

Main associative containers:

std::set
std::multiset
std::map
std::multimap

All of them are located in:

#include <set>
#include <map>

2.1 Characteristics and Use Cases

1️⃣ std::set

Purpose

Stores unique elements in sorted order.

Characteristics

Elements are automatically sorted
Duplicates are not allowed
Implemented using balanced tree
Search operations are logarithmic

Example

#include <iostream>
#include <set>int main()
{
    std::set<int> s;    s.insert(10);
    s.insert(20);
    s.insert(10);     for(int x : s)
        std::cout << x << " ";
}

Output

10 20

Use Cases

Removing duplicates
Maintaining sorted collections
Fast searching

2️⃣ std::multiset

Purpose

Stores sorted elements but allows duplicates.

Characteristics

Multiple identical elements allowed
Elements sorted automatically
Search complexity O(log n)

Example

std::multiset<int> ms;ms.insert(10);
ms.insert(10);
ms.insert(20);

Output

10 10 20

Use Cases

Frequency counting
Sorted collections with duplicates

3️⃣ std::map

Purpose

Stores key-value pairs with unique keys.

Characteristics

Keys are unique
Elements stored in sorted order by key
Fast lookup using keys
Each element is a pair

Example

#include <map>std::map<int, std::string> students;students[1] = "Venkat";
students[2] = "John";

Stored as

key -> value
1   -> Venkat
2   -> John

Use Cases

Dictionaries
Lookup tables
Configuration storage

4️⃣ std::multimap

Purpose

Stores multiple values for the same key.

Characteristics

Keys can repeat
Sorted by key
Similar to map but allows duplicates

Example

std::multimap<int, std::string> mm;mm.insert({1,"A"});
mm.insert({1,"B"});

Output

1 A
1 B

Use Cases

Grouping values by same key
Database-like relationships

2.2 Standard Methods

Common Operations

Operation	Description
`insert()`	Add element
`erase()`	Remove element
`find()`	Search element
`count()`	Number of occurrences
`size()`	Number of elements
`clear()`	Remove all elements

Insertion

set / multiset

std::set<int> s;s.insert(10);
s.insert(20);

map

std::map<int,std::string> m;m.insert({1,"Alice"});
m[2] = "Bob";

multimap

std::multimap<int,std::string> mm;mm.insert({1,"A"});
mm.insert({1,"B"});

Searching

auto it = s.find(10);if(it != s.end())
{
    std::cout << "Found";
}

Deletion

s.erase(10);

For map

m.erase(1);

2.3 Using Simple and Complex Data Types

Associative containers support:

Built-in types

std::set<int> numbers;
std::map<int,double> values;

User-defined types

Example

struct Person
{
    int id;
    std::string name;
};

Use inside container

std::map<int,Person> people;

Insert

people[1] = {1,"Venkat"};

Custom comparison

Associative containers require ordering.

Example comparator

struct Compare
{
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};std::set<int, Compare> s;

This sorts elements descending.

2.4 Traversing Associative Containers

Associative containers use iterators.

Using iterators

std::set<int> s = {10,20,30};for(auto it = s.begin(); it != s.end(); ++it)
{
    std::cout << *it;
}

Range-based loop

for(int x : s)
{
    std::cout << x;
}

Map traversal

std::map<int,std::string> m;m[1] = "A";
m[2] = "B";for(auto it = m.begin(); it != m.end(); ++it)
{
    std::cout << it->first << " " << it->second;
}

Output

1 A
2 B

2.5 Operations Using Member Functions and Iterators

Accessing elements

map

std::map<int,std::string> m;m[1] = "Venkat";std::cout << m[1];

std::cout << m.at(1);

Modifying elements

m[1] = "Updated";

Erasing using iterator

auto it = m.find(1);if(it != m.end())
{
    m.erase(it);
}

Counting elements

std::multiset<int> ms;ms.insert(10);
ms.insert(10);std::cout << ms.count(10);

Output

Time Complexity

Operation	Complexity
Insert	O(log n)
Search	O(log n)
Delete	O(log n)

Comparison Table

Container	Duplicates	Stored Data
set	No	value
multiset	Yes	value
map	No	key-value
multimap	Yes	key-value

Key Points for Exam

Associative containers are ordered containers.
They internally use balanced binary trees (Red-Black Trees).
Elements are sorted automatically.
Operations usually run in O(log n) time.
map and set allow unique keys, while multimap and multiset allow duplicates.

✅ Summary

Associative containers are used when:

Fast searching is required
Data must remain sorted
Key-value relationships are needed