Ordered Containers

Ordered containers provide sorted iteration and predictable performance by implementing balanced binary search trees. While they offer slower average access than hash containers, they guarantee element ordering and provide consistent O(log n) performance regardless of data distribution.

What are Ordered Containers?

Ordered containers are implemented as balanced binary search trees (typically Red-Black trees in most STL implementations). This structure provides:

• Sorted iteration: Elements are always traversed in sorted order
• Predictable performance: O(log n) operations regardless of data
• Range operations: Efficient queries for ranges of keys
• Nearest key operations: Find keys close to a given value
• Stable performance: No performance degradation from poor hash functions

std::map

Basic Usage

#include <map>
#include <string>
#include <iostream>

// Create an ordered map
std::map<std::string, int> scores;

// Insert elements
scores["Alice"] = 95;
scores["Bob"] = 87;
scores["Charlie"] = 92;
scores["David"] = 89;

// Elements are automatically sorted by key
for (const auto& [name, score] : scores) {
    std::cout << name << ": " << score << std::endl;
}
// Output: Alice: 95, Bob: 87, Charlie: 92, David: 89
// Note: Always alphabetical order!

Insertion and Access

std::map<std::string, int> scores;

// Insert with duplicate handling
auto result = scores.insert({"Alice", 95});
if (result.second) {
    std::cout << "Alice inserted successfully" << std::endl;
} else {
    std::cout << "Alice already exists with score: " << result.first->second << std::endl;
}

// Insert or update
scores["Alice"] = 98;  // Overwrites existing value

// Safe access with bounds checking
auto it = scores.find("Bob");
if (it != scores.end()) {
    std::cout << "Bob's score: " << it->second << std::endl;
} else {
    std::cout << "Bob not found" << std::endl;
}

// Access with default value (creates entry if not exists)
int frank_score = scores["Frank"];  // Creates entry with value 0

Ordered Iteration and Range Operations

std::map<std::string, int> scores = {
    {"Alice", 95}, {"Bob", 87}, {"Charlie", 92}, {"David", 89}
};

// Forward iteration (always sorted)
for (auto it = scores.begin(); it != scores.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

// Reverse iteration (reverse sorted)
for (auto it = scores.rbegin(); it != scores.rend(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

// Range queries
auto lower = scores.lower_bound("Bob");      // First element >= "Bob"
auto upper = scores.upper_bound("Charlie");  // First element > "Charlie"

std::cout << "Range from Bob to Charlie:" << std::endl;
for (auto it = lower; it != upper; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

std::set

Basic Usage

#include <set>
#include <iostream>

// Create an ordered set
std::set<int> numbers;

// Insert elements
numbers.insert(5);
numbers.insert(2);
numbers.insert(8);
numbers.insert(1);
numbers.insert(5);  // Duplicate ignored

// Elements are automatically sorted
for (const auto& num : numbers) {
    std::cout << num << " ";  // Output: 1 2 5 8
}
std::cout << std::endl;

// Check membership
if (numbers.find(3) != numbers.end()) {
    std::cout << "3 is in the set" << std::endl;
} else {
    std::cout << "3 is not in the set" << std::endl;
}

Set Operations

std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {4, 5, 6, 7, 8};

// Check if element exists (C++20)
bool has_three = set1.contains(3);  // true

// Count occurrences (0 or 1 for sets)
size_t count = set1.count(4);  // 1

// Remove elements
set1.erase(3);  // set1 = {1, 2, 4, 5}

// Get size and check emptiness
std::cout << "Size: " << set1.size() << std::endl;
std::cout << "Empty: " << set1.empty() << std::endl;

std::multimap and std::multiset

Allowing Duplicate Keys/Values

#include <map>
#include <set>

// multimap allows multiple values per key
std::multimap<std::string, std::string> phone_book;

phone_book.insert({"Alice", "555-0101"});
phone_book.insert({"Alice", "555-0102"});  // Multiple numbers for Alice
phone_book.insert({"Bob", "555-0201"});

// Find all numbers for Alice
auto range = phone_book.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << "Alice: " << it->second << std::endl;
}

// multiset allows duplicate values
std::multiset<int> scores = {85, 90, 85, 95, 90};

// Count occurrences
std::cout << "Number of 85s: " << scores.count(85) << std::endl;  // 2
std::cout << "Number of 90s: " << scores.count(90) << std::endl;  // 2

// Remove one occurrence
scores.erase(scores.find(85));  // Removes only one 85

Key Differences from Regular Containers

Feature	std::map	std::multimap	std::set	std::multiset
Duplicate Keys	No	Yes	N/A	N/A
Duplicate Values	N/A	N/A	No	Yes
insert() Behavior	Overwrites existing	Adds new entry	Ignores duplicates	Adds duplicates
erase() Behavior	Removes key-value pair	Removes specific entry	Removes value	Removes specific value

Performance and Memory

Time Complexity

Operation	Time Complexity	Notes
Insertion	O(log n)	Balanced tree insertion
Lookup	O(log n)	Binary search tree traversal
Deletion	O(log n)	Tree rebalancing
Iteration	O(n)	Must visit all elements
Range Queries	O(log n + k)	k = number of elements in range

Memory Layout

// Conceptual tree structure
struct TreeNode {
    std::pair<std::string, int> data;
    TreeNode* left;
    TreeNode* right;
    bool is_red;  // Red-Black tree property
};

// Memory layout (conceptual):
//        Bob(87)
//        /      \
//   Alice(95)  Charlie(92)
//                \
//                David(89)

// Elements are scattered in memory (not contiguous)
// Each node has overhead: left/right pointers + color bit

Key Insight: Tree nodes are scattered in memory, providing poor cache locality compared to contiguous containers like std::vector.

When to Use Ordered Containers

Use std::map/std::set when:

• Ordered iteration needed: Elements must be traversed in sorted order
• Range queries required: Need to find elements in specific ranges
• Nearest key operations: Find keys close to a given value
• Predictable performance: Consistent O(log n) regardless of data
• Memory efficiency: Lower overhead than hash containers

Consider alternatives when:

• Fastest average lookup needed: Use std::unordered_map/unordered_set
• Cache performance critical: Use std::vector for sequential access
• Frequent middle insertions: Use std::list for O(1) operations
• Large datasets with simple lookups: Hash containers may be better

Feature Comparison

Feature	std::map	std::unordered_map
Ordering	Always sorted	No ordering guarantee
Lookup	O(log n)	O(1) average
Performance	Predictable	Variable (depends on hash)
Memory	Lower overhead	Higher overhead
Range Queries	Efficient	Inefficient
Cache Locality	Poor	Poor (both tree-based)

Summary

Ordered containers (std::map, std::set, std::multimap, std::multiset) provide:

Advantages:

• Sorted iteration: Elements always traversed in sorted order
• Predictable performance: Consistent O(log n) operations
• Range operations: Efficient queries for key ranges
• Nearest value search: When you need to find close matches
• Predictable performance: When consistent performance is required

Trade-offs:

• Slower access: O(log n) vs O(1) average for hash containers
• Poor cache locality: Tree nodes scattered in memory
• Higher insertion cost: Tree rebalancing required
• Memory overhead: Extra pointers and metadata per node

Best Use Cases:

• Ordered data: When elements must be processed in sorted order
• Range queries: When you need elements in specific key ranges
• Nearest value search: When you need to find close matches
• Predictable performance: When consistent performance is required

Choose ordered containers when you need sorted iteration and range operations, and are willing to trade some performance for these guarantees. For pure lookup performance without ordering requirements, hash containers will be faster.

Questions

Q: What is the time complexity of insertion and lookup in std::map?

std::map provides O(log n) insertion and lookup time because it's implemented as a balanced binary search tree (usually Red-Black tree). This provides predictable performance regardless of data distribution, unlike hash containers which can degrade to O(n) in worst cases.

Q: What is the main advantage of std::map over std::unordered_map?

The main advantage of std::map is that elements are always maintained in sorted order. This allows for ordered iteration, range queries, and finding the nearest key. std::unordered_map provides no ordering guarantees.

Q: When should you use std::multimap instead of std::map?

Use std::multimap when you need to store multiple values for the same key. std::map only allows one value per key, while std::multimap allows multiple values, making it useful for one-to-many relationships like a phone book where one person might have multiple phone numbers.

Q: What happens when you insert a key that already exists in std::map?

When you insert a key that already exists in std::map, the new value overwrites the existing value. std::map maintains the uniqueness constraint - one key can only have one value. If you need multiple values per key, use std::multimap instead.

Q: Which container would you choose for maintaining a sorted list of unique elements with fast insertion and deletion?

std::set is the best choice for maintaining a sorted list of unique elements with fast insertion and deletion. It provides O(log n) insertion/deletion while maintaining sorted order. std::vector would require O(n) insertion/deletion, std::list doesn't maintain order, and std::unordered_set doesn't guarantee sorted iteration.