C++ Notes: A Guide to Choosing STL Containers – Performance Comparison and Usage Scenario Analysis

Choosing the right STL container is an important skill in C++ programming. Different containers have vastly different performance characteristics and applicable scenarios, and a wrong choice can lead to a performance drop of ten times or more. Mastering the art of selecting STL containers is crucial.

Learning Objectives：

• • Understand the performance characteristics and memory features of various STL containers
• • Master the best container selection for different usage scenarios
• • Learn to verify container performance through simple tests
• • Avoid common pitfalls in container selection

Overview of STL Containers

Container Classification

Concept Explanation：STL containers are classified into sequence containers, associative containers, and unordered containersWhy It Matters：Different categories of containers have completely different performance characteristicsApplicable Scenarios：Choose the appropriate container category based on data access patterns

Container Category	Representative Containers	Characteristics	Applicable Scenarios
Sequence Containers	vector, deque, list	Elements are stored in order	Need to maintain insertion order
Associative Containers	map, set, multimap, multiset	Automatically sorted	Need fast lookup and ordered traversal
Unordered Containers	unordered_map, unordered_set	Implemented with hash tables	Only need fast lookup, order does not matter

Performance Complexity Quick Reference Table

Operation	vector	list	map	unordered_map
Insertion (End)	O(1) amortized	O(1)	O(log n)	O(1) average
Insertion (Middle)	O(n)	O(1)	O(log n)	O(1) average
Deletion (End)	O(1)	O(1)	O(log n)	O(1) average
Deletion (Middle)	O(n)	O(1)	O(log n)	O(1) average
Lookup	O(n)	O(n)	O(log n)	O(1) average
Random Access	O(1)	O(n)	❌	❌

Detailed Explanation of Sequence Containers

vector: The Most Common Sequence Container

Core Characteristics Analysis

Concept Explanation：vector is a dynamic array, elements are stored contiguously in memoryWhy It Matters：Contiguous memory layout provides excellent cache performanceApplicable Scenarios：Most scenarios requiring a sequence container

#include <vector>
#include <iostream>
#include <chrono>

// vector performance characteristics demonstration
void vectorPerformanceDemo() {
    std::vector<int> vec;
    
    // 1. Preallocate capacity to avoid frequent reallocations
    vec.reserve(1000);  // Important: preallocate capacity
    
    auto start = std::chrono::high_resolution_clock::now();
    
    // Insertion at the end: O(1) amortized time complexity
    for (int i = 0; i < 1000; ++i) {
        vec.push_back(i);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "Vector end insertion of 1000 elements took: " << duration.count() << " microseconds" << std::endl;
    
    // 2. Random access: O(1) time complexity
    start = std::chrono::high_resolution_clock::now();
    int sum = 0;
    for (size_t i = 0; i < vec.size(); ++i) {
        sum += vec[i];  // Direct index access, very fast
    }
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);
    
    std::cout << "Random access sum took: " << duration.count() << " nanoseconds" << std::endl;
}

Best Practices for Using vector

1. Use reserve() wisely to avoid reallocations

void vectorReserveDemo() {
    // ❌ Bad practice: not preallocating
    std::vector<int> badVec;
    for (int i = 0; i < 10000; ++i) {
        badVec.push_back(i);  // May trigger multiple memory reallocations
    }
    
    // ✅ Good practice: preallocate capacity
    std::vector<int> goodVec;
    goodVec.reserve(10000);  // Allocate enough memory at once
    for (int i = 0; i < 10000; ++i) {
        goodVec.push_back(i);  // Will not trigger reallocations
    }
}

2. Choose the appropriate deletion method

void vectorEraseDemo() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // ❌ Inefficient: deleting from front to back
    for (auto it = vec.begin(); it != vec.end();) {
        if (*it % 2 == 0) {
            it = vec.erase(it);  // O(n) operation, overall O(n²)
        } else {
            ++it;
        }
    }
    
    // ✅ Efficient: use remove_if + erase
    vec.erase(
        std::remove_if(vec.begin(), vec.end(), 
                      [](int x) { return x % 2 == 0; }),
        vec.end()
    );  // O(n) operation
}

Modern C++ Optimization Techniques

Use emplace to avoid unnecessary copies：

void modernVectorUsage() {
    std::vector<std::pair<int, std::string>> vec;
    
    // ❌ Create temporary objects and then copy
    vec.push_back(std::make_pair(1, "hello"));
    vec.push_back({2, "world"});
    
    // ✅ Construct objects directly in the container
    vec.emplace_back(3, "modern");  // Direct construction, avoids copy
    vec.emplace_back(4, "cpp");
    
    // Constructing complex objects
    std::vector<std::string> strings;
    strings.emplace_back(10, 'A');  // Construct a string of 10 'A's
}

Memory Usage Analysis

void vectorMemoryAnalysis() {
    std::vector<int> vec;
    std::cout << "Empty vector size: " << sizeof(vec) << " bytes" << std::endl;
    
    for (int i = 1; i <= 5; ++i) {
        vec.push_back(i);
        std::cout << "Element count: " << vec.size() 
                  << ", Capacity: " << vec.capacity() << std::endl;
    }
}

deque: Double-ended Queue Container

Core Characteristics Analysis

Concept Explanation：deque is a double-ended queue that supports fast insertion and deletion at both ends, while also supporting random accessWhy It Matters：Combines the advantages of vector and list, providing optimal performance in specific scenariosApplicable Scenarios：Scenarios that require frequent operations at both ends but occasionally need random access

#include <deque>

// deque performance characteristics demonstration
void dequePerformanceDemo() {
    std::deque<int> deq;
    
    // 1. Both ends insertion is O(1)
    auto start = std::chrono::high_resolution_clock::now();
    
    for (int i = 0; i < 10000; ++i) {
        if (i % 2 == 0) {
            deq.push_back(i);   // Insert at the end O(1)
        } else {
            deq.push_front(i);  // Insert at the front O(1)
        }
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "Deque insertion of 10000 elements took: " << duration.count() << " microseconds" << std::endl;
    
    // 2. Random access is still O(1) (though slower than vector)
    start = std::chrono::high_resolution_clock::now();
    int sum = 0;
    for (size_t i = 0; i < deq.size(); ++i) {
        sum += deq[i];  // O(1) random access
    }
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "Deque random access sum took: " << duration.count() << " microseconds" << std::endl;
}

Applicable Scenarios for deque

1. Sliding Window Algorithm

// Fixed size sliding window
class SlidingWindow {
private:
    std::deque<int> window;
    size_t maxSize;
    
public:
    SlidingWindow(size_t size) : maxSize(size) {}
    
    void addValue(int value) {
        if (window.size() >= maxSize) {
            window.pop_front();  // O(1) delete the oldest element
        }
        window.push_back(value);  // O(1) add new element
    }
    
    double average() const {
        if (window.empty()) return 0.0;
        return std::accumulate(window.begin(), window.end(), 0.0) / window.size();
    }
    
    int getElement(size_t index) const {
        return window[index];  // O(1) random access
    }
};

2. Double-ended Buffer

// Buffer that can be read and written from both ends
class DoubleEndedBuffer {
private:
    std::deque<char> buffer;
    
public:
    void writeBack(char c) {
        buffer.push_back(c);    // Write from the end
    }
    
    void writeFront(char c) {
        buffer.push_front(c);   // Write from the front
    }
    
    char readBack() {
        char c = buffer.back();
        buffer.pop_back();      // Read from the end
        return c;
    }
    
    char readFront() {
        char c = buffer.front();
        buffer.pop_front();     // Read from the front
        return c;
    }
};

list: Doubly Linked List Container

Core Characteristics Analysis

Concept Explanation：list is a doubly linked list, elements are stored non-contiguously and connected by pointersWhy It Matters：Insertion and deletion at any position are O(1) time complexityApplicable Scenarios：Frequent insertion and deletion of elements in the middle

#include <list>
#include <algorithm>

// Performance comparison of list and vector insertion
void listVsVectorInsert() {
    const int N = 10000;
    
    // Test middle insertion in list
    std::list<int> lst;
    auto start = std::chrono::high_resolution_clock::now();
    
    for (int i = 0; i < N; ++i) {
        auto it = lst.begin();
        std::advance(it, lst.size() / 2);  // Find the middle position
        lst.insert(it, i);  // O(1) insertion
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto listTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    // Test middle insertion in vector
    std::vector<int> vec;
    start = std::chrono::high_resolution_clock::now();
    
    for (int i = 0; i < N; ++i) {
        vec.insert(vec.begin() + vec.size() / 2, i);  // O(n) insertion
    }
    
    end = std::chrono::high_resolution_clock::now();
    auto vecTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "List middle insertion took: " << listTime.count() << " microseconds" << std::endl;
    std::cout << "Vector middle insertion took: " << vecTime.count() << " microseconds" << std::endl;
    std::cout << "Vector is slower than List by: " << (double)vecTime.count() / listTime.count() << " times" << std::endl;
}

Applicable Scenarios for list

1. Scenarios with Frequent Insertions and Deletions

// Practical application: LRU Cache Implementation
class LRUCache {
private:
    std::list<std::pair<int, int>> cache;  // Use list to store key-value pairs
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;
    int capacity;
    
public:
    LRUCache(int cap) : capacity(cap) {}
    
    int get(int key) {
        if (map.find(key) == map.end()) {
            return -1;
        }
        
        // Move to the front of the list (most recently used)
        auto it = map[key];
        int value = it->second;
        cache.erase(it);  // O(1) deletion
        cache.push_front({key, value});  // O(1) insertion
        map[key] = cache.begin();
        
        return value;
    }
    
    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            cache.erase(map[key]);  // O(1) deletion
        } else if (cache.size() >= capacity) {
            // Remove the least recently used element
            int oldKey = cache.back().first;
            cache.pop_back();  // O(1) deletion
            map.erase(oldKey);
        }
        
        cache.push_front({key, value});  // O(1) insertion
        map[key] = cache.begin();
    }
};

2. Sequences that Do Not Require Random Access

// Event queue processing
class EventProcessor {
private:
    std::list<std::function<void()>> eventQueue;
    
public:
    void addEvent(std::function<void()> event) {
        eventQueue.push_back(event);  // O(1) add to the tail
    }
    
    void insertUrgentEvent(std::function<void()> event) {
        eventQueue.push_front(event);  // O(1) insert at the head
    }
    
    void processEvents() {
        while (!eventQueue.empty()) {
            auto event = eventQueue.front();
            eventQueue.pop_front();  // O(1) delete from the head
            event();  // Execute event
        }
    }
};

Detailed Explanation of Associative Containers

map vs unordered_map: Choosing Associative Containers

Performance Characteristics Comparison

Concept Explanation：map is implemented based on a red-black tree and is ordered; unordered_map is implemented based on a hash table and is unorderedWhy It Matters：The performance difference in lookup is significant, and a wrong choice can impact program performanceApplicable Scenarios：Use map when ordered traversal is needed, use unordered_map for fast lookup

#include <map>
#include <unordered_map>
#include <random>

void mapVsUnorderedMapBenchmark() {
    const int N = 100000;
    std::vector<int> keys;
    
    // Generate random keys
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 1000000);
    
    for (int i = 0; i < N; ++i) {
        keys.push_back(dis(gen));
    }
    
    // Test map insertion performance
    std::map<int, int> orderedMap;
    auto start = std::chrono::high_resolution_clock::now();
    
    for (int key : keys) {
        orderedMap[key] = key * 2;  // O(log n) insertion
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto mapInsertTime = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    // Test unordered_map insertion performance
    std::unordered_map<int, int> hashMap;
    start = std::chrono::high_resolution_clock::now();
    
    for (int key : keys) {
        hashMap[key] = key * 2;  // O(1) average insertion
    }
    
    end = std::chrono::high_resolution_clock::now();
    auto hashMapInsertTime = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "Map insertion of " << N << " elements took: " << mapInsertTime.count() << " ms" << std::endl;
    std::cout << "UnorderedMap insertion took: " << hashMapInsertTime.count() << " ms" << std::endl;
    std::cout << "UnorderedMap is faster than Map by: " << (double)mapInsertTime.count() / hashMapInsertTime.count() << " times" << std::endl;
    
    // Test lookup performance
    start = std::chrono::high_resolution_clock::now();
    int mapCount = 0;
    for (int key : keys) {
        if (orderedMap.find(key) != orderedMap.end()) {  // O(log n) lookup
            mapCount++;
        }
    }
    end = std::chrono::high_resolution_clock::now();
    auto mapFindTime = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    start = std::chrono::high_resolution_clock::now();
    int hashMapCount = 0;
    for (int key : keys) {
        if (hashMap.find(key) != hashMap.end()) {  // O(1) average lookup
            hashMapCount++;
        }
    }
    end = std::chrono::high_resolution_clock::now();
    auto hashMapFindTime = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "Map lookup took: " << mapFindTime.count() << " ms" << std::endl;
    std::cout << "UnorderedMap lookup took: " << hashMapFindTime.count() << " ms" << std::endl;
    std::cout << "UnorderedMap is faster than Map by: " << (double)mapFindTime.count() / hashMapFindTime.count() << " times" << std::endl;
}

Selection Guide

When to Use map：

// 1. When ordered traversal is needed
void printSortedWords(const std::vector<std::string>& words) {
    std::map<std::string, int> wordCount;
    
    for (const auto& word : words) {
        wordCount[word]++;
    }
    
    // Automatically output in dictionary order
    for (const auto& pair : wordCount) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}

// 2. When range queries are needed
void findWordsInRange(const std::map<std::string, int>& wordMap, 
                      const std::string& start, const std::string& end) {
    auto lower = wordMap.lower_bound(start);
    auto upper = wordMap.upper_bound(end);
    
    for (auto it = lower; it != upper; ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }
}

When to Use unordered_map：

// 1. When only fast lookup is needed, order does not matter
class UserCache {
private:
    std::unordered_map<int, std::string> userMap;  // User ID -> Username
    
public:
    void addUser(int id, const std::string& name) {
        userMap[id] = name;  // O(1) average
    }
    
    std::string getUser(int id) {
        auto it = userMap.find(id);  // O(1) average
        return it != userMap.end() ? it->second : "";
    }
    
    bool hasUser(int id) {
        return userMap.count(id) > 0;  // O(1) average
    }
};

// 2. For frequency counting and other aggregation operations
std::unordered_map<char, int> countCharacters(const std::string& text) {
    std::unordered_map<char, int> charCount;
    
    for (char c : text) {
        charCount[c]++;  // O(1) average
    }
    
    return charCount;
}

Application of Modern C++ Features

Use string_view to optimize performance：

#include <string_view>

// Avoid unnecessary string copies
class StringProcessor {
private:
    std::unordered_map<std::string, int> wordCount;
    
public:
    // Use string_view to avoid creating temporary strings
    void processWord(std::string_view word) {
        // Note: If needed as a key, still need to convert to string
        std::string key(word);  // Create string only when necessary
        wordCount[key]++;
    }
    
    // Can directly use string_view for lookup (C++20)
    bool hasWord(std::string_view word) const {
        return wordCount.contains(std::string(word));
    }
};

Use emplace to optimize map insertion：

void modernMapUsage() {
    std::map<std::string, std::vector<int>> dataMap;
    
    // ❌ Inefficient: find first then insert
    dataMap["key1"] = std::vector<int>{1, 2, 3};
    
    // ✅ Efficient: use emplace to construct directly
    dataMap.emplace("key2", std::vector<int>{4, 5, 6});
    
    // ✅ Or use emplace_hint to optimize insertion position
    auto hint = dataMap.end();
    hint = dataMap.emplace_hint(hint, "key3", std::vector<int>{7, 8, 9});
    
    // ✅ Use try_emplace to avoid overwriting existing values
    auto result = dataMap.try_emplace("key1", std::vector<int>{10, 11, 12});
    if (!result.second) {
        std::cout << "Key already exists!" << std::endl;
    }
}

set vs unordered_set: Choosing Set Containers

Usage Scenario Analysis

Concept Explanation：set stores unique elements and maintains order, unordered_set only guarantees uniquenessWhy It Matters：Different application scenarios require different performance characteristicsApplicable Scenarios：Use set when sorting is needed, use unordered_set for deduplication

#include <set>
#include <unordered_set>

// Practical application case: Data deduplication
void deduplicationComparison() {
    std::vector<int> data = {5, 2, 8, 2, 1, 9, 5, 3, 8, 1, 7, 6};
    
    // Use set for deduplication (maintaining order)
    std::set<int> orderedUnique(data.begin(), data.end());
    std::cout << "Set deduplication result: ";
    for (int val : orderedUnique) {
        std::cout << val << " ";  // Output: 1 2 3 5 6 7 8 9
    }
    std::cout << std::endl;
    
    // Use unordered_set for deduplication (order not guaranteed)
    std::unordered_set<int> hashUnique(data.begin(), data.end());
    std::cout << "UnorderedSet deduplication result: ";
    for (int val : hashUnique) {
        std::cout << val << " ";  // Output order is uncertain
    }
    std::cout << std::endl;
}

// Permission checking system
class PermissionChecker {
private:
    std::unordered_set<std::string> permissions;  // Fast lookup
    
public:
    void addPermission(const std::string& perm) {
        permissions.insert(perm);  // O(1) average
    }
    
    bool hasPermission(const std::string& perm) const {
        return permissions.count(perm) > 0;  // O(1) average lookup
    }
    
    void removePermission(const std::string& perm) {
        permissions.erase(perm);  // O(1) average
    }
};

// Ordered set application: Score ranking
class ScoreRanking {
private:
    std::set<std::pair<int, std::string>> scores;  // Score + Name, automatically sorted
    
public:
    void addScore(const std::string& name, int score) {
        scores.insert({score, name});  // O(log n) insertion
    }
    
    void printTopN(int n) {
        auto it = scores.rbegin();  // Start from the highest score
        int count = 0;
        
        while (it != scores.rend() && count < n) {
            std::cout << "Rank " << (count + 1) << ": " << it->second 
                      << " - " << it->first << " points" << std::endl;
            ++it;
            ++count;
        }
    }
};

Container Adapters

Design Choices Based on Underlying Containers

Concept Explanation：Container adapters are special interface containers implemented based on other containersWhy It Matters：Choosing the right underlying container directly affects adapter performanceApplicable Scenarios：When specific data structure behavior is needed (stack, queue, priority queue)

#include <stack>
#include <queue>
#include <vector>
#include <deque>

// Performance comparison of different underlying containers
void containerAdapterComparison() {
    // stack: defaults to deque, can also use vector or list
    std::stack<int> defaultStack;              // Based on deque
    std::stack<int, std::vector<int>> vecStack; // Based on vector
    std::stack<int, std::list<int>> listStack;  // Based on list
    
    // queue: defaults to deque, can also use list
    std::queue<int> defaultQueue;              // Based on deque
    std::queue<int, std::list<int>> listQueue; // Based on list
    
    // priority_queue: defaults to vector
    std::priority_queue<int> defaultPQ;        // Based on vector (optimal choice)
    std::priority_queue<int, std::deque<int>> dequePQ; // Based on deque (less optimal)
}

Adapter Selection Guide

stack Adapter：

// Scenario Analysis: Only need Last In First Out (LIFO) operations
class ExpressionEvaluator {
private:
    std::stack<int> operands;           // Operand stack
    std::stack<char> operators;         // Operator stack
    
public:
    int evaluate(const std::string& expression) {
        for (char c : expression) {
            if (std::isdigit(c)) {
                operands.push(c - '0');     // O(1) push
            } else if (c == '+' || c == '-') {
                // Handle operators...
                int b = operands.top(); operands.pop();  // O(1) pop
                int a = operands.top(); operands.pop();
                operands.push(c == '+' ? a + b : a - b);
            }
        }
        return operands.top();
    }
};

queue Adapter：

// Scenario Analysis: Need First In First Out (FIFO) operations
class TaskQueue {
private:
    std::queue<std::function<void()>> tasks;
    
public:
    void addTask(std::function<void()> task) {
        tasks.push(task);               // O(1) enqueue
    }
    
    void processTasks() {
        while (!tasks.empty()) {
            auto task = tasks.front();  // O(1) get front
            tasks.pop();                // O(1) dequeue
            task();
        }
    }
};

priority_queue Adapter：

// Scenario Analysis: Need priority queue operations
struct Task {
    int priority;
    std::string description;
    
    // Overload comparison operator (note: priority_queue is a max heap)
    bool operator<(const Task& other) const {
        return priority < other.priority;  // Higher priority comes first
    }
};

class PriorityTaskManager {
private:
    std::priority_queue<Task> tasks;    // Default based on vector, optimal performance
    
public:
    void addTask(int priority, const std::string& desc) {
        tasks.emplace(priority, desc);  // O(log n) insertion
    }
    
    void processHighestPriorityTask() {
        if (!tasks.empty()) {
            Task highestTask = tasks.top();  // O(1) get highest priority
            tasks.pop();                     // O(log n) delete
            std::cout << "Processing: " << highestTask.description << std::endl;
        }
    }
};

Recommendations for Underlying Container Selection

Adapter	Recommended Underlying Container	Reason	Avoid Choosing
stack	<span>deque</span>（default）	Efficient for both ends operations, memory is contiguous	<span>vector</span>（high cost for resizing）
queue	<span>deque</span>（default）	Both ends operations are O(1)	<span>vector</span>（inefficient for head deletion）
priority_queue	<span>vector</span>（default）	Supports heap operations with random access	<span>list</span>（no random access）

Container Selection Decision Tree

Quick Selection Guide

// Container selection flowchart (code version)
std::string chooseContainer(bool needOrder, bool needRandomAccess, 
                           bool frequentInsertDelete, bool uniqueElements) {
    if (uniqueElements) {
        if (needOrder) {
            return "std::set";  // Need unique and ordered
        } else {
            return "std::unordered_set";  // Only need unique
        }
    } else {
        if (needRandomAccess) {
            return "std::vector";  // Need random access
        } else if (frequentInsertDelete) {
            if (needOrder) {
                return "std::map";  // Need ordered key-value pairs
            } else {
                return "std::list";  // Frequent insertions and deletions but no need for random access
            }
        } else {
            if (needOrder) {
                return "std::vector";  // Need order but rarely modified
            } else {
                return "std::unordered_map";  // Fast lookup for key-value pairs
            }
        }
    }
}

Practical Selection Cases

Case 1: Log Processing System

class LogProcessor {
private:
    // Scenario Analysis: Need to process in chronological order, occasional insertions, frequent traversals
    std::vector<std::string> logs;  // ✅ Choose vector
    
public:
    void addLog(const std::string& log) {
        logs.push_back(log);  // Always add at the end, O(1)
    }
    
    void processLogs() {
        for (const auto& log : logs) {  // Sequential traversal, cache-friendly
            // Process log
        }
    }
};

Case 2: Word Counting System

class WordAnalyzer {
private:
    // Scenario Analysis: Need to count frequency, frequent lookups and updates, no need for order
    std::unordered_map<std::string, int> wordCount;  // ✅ Choose unordered_map
    
public:
    void addWord(const std::string& word) {
        wordCount[word]++;  // O(1) average time complexity
    }
    
    int getWordCount(const std::string& word) {
        auto it = wordCount.find(word);  // O(1) average lookup
        return it != wordCount.end() ? it->second : 0;
    }
    
    // If need to output sorted by frequency, temporarily convert
    std::vector<std::pair<std::string, int>> getTopWords(int n) {
        std::vector<std::pair<std::string, int>> result(wordCount.begin(), wordCount.end());
        
        std::partial_sort(result.begin(), result.begin() + n, result.end(),
                         [](const auto& a, const auto& b) {
                             return a.second > b.second;  // Sort by frequency in descending order
                         });
        
        result.resize(n);
        return result;
    }
};

Case 3: Task Scheduling System

class TaskScheduler {
private:
    // Scenario Analysis: Need to insert/delete tasks at any position, no need for random access
    std::list<std::function<void()>> tasks;  // ✅ Choose list
    
public:
    void addTask(std::function<void()> task) {
        tasks.push_back(task);  // O(1) add
    }
    
    void addUrgentTask(std::function<void()> task) {
        tasks.push_front(task);  // O(1) insert at the front
    }
    
    void insertTaskAfter(std::list<std::function<void()>>::iterator pos, 
                        std::function<void()> task) {
        tasks.insert(pos, task);  // O(1) insert at specified position
    }
    
    void executeTasks() {
        while (!tasks.empty()) {
            auto task = tasks.front();
            tasks.pop_front();  // O(1) delete
            task();
        }
    }
};

Memory Usage Pattern Analysis

Memory Usage Comparison Test

void memoryUsageComparison() {
    const int N = 10000;
    
    // Test memory usage of different containers
    std::vector<int> vec(N);
    std::list<int> lst(N);
    std::set<int> s;
    std::unordered_set<int> us;
    
    for (int i = 0; i < N; ++i) {
        s.insert(i);
        us.insert(i);
    }
    
    std::cout << "Memory usage comparison (" << N << " int elements):" << std::endl;
    std::cout << "vector size: " << vec.size() * sizeof(int) << " bytes" << std::endl;
    std::cout << "list estimated size: " << lst.size() * (sizeof(int) + 2 * sizeof(void*)) << " bytes" << std::endl;
    std::cout << "set estimated size: " << s.size() * (sizeof(int) + 3 * sizeof(void*) + sizeof(bool)) << " bytes" << std::endl;
    std::cout << "unordered_set estimated size: " << us.size() * (sizeof(int) + sizeof(void*)) + us.bucket_count() * sizeof(void*) << " bytes" << std::endl;
}

Cache Friendliness Analysis

Concept Explanation：Accessing contiguous memory is much faster than accessing random memoryWhy It Matters：Cache misses can lead to a performance difference of up to 100 timesApplicable Scenarios：Data structures that require frequent traversal should choose cache-friendly containers

void cachePerformanceTest() {
    const int N = 1000000;
    
    // vector: contiguous memory, cache-friendly
    std::vector<int> vec(N);
    std::iota(vec.begin(), vec.end(), 0);
    
    // list: scattered memory, cache-unfriendly
    std::list<int> lst;
    for (int i = 0; i < N; ++i) {
        lst.push_back(i);
    }
    
    // Test sequential traversal performance
    auto start = std::chrono::high_resolution_clock::now();
    long long sum1 = 0;
    for (int val : vec) {  // Cache-friendly traversal
        sum1 += val;
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto vecTime = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    start = std::chrono::high_resolution_clock::now();
    long long sum2 = 0;
    for (int val : lst) {  // Cache-unfriendly traversal
        sum2 += val;
    }
    end = std::chrono::high_resolution_clock::now();
    auto listTime = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "Vector traversal took: " << vecTime.count() << " ms" << std::endl;
    std::cout << "List traversal took: " << listTime.count() << " ms" << std::endl;
    std::cout << "List is slower than Vector by: " << (double)listTime.count() / vecTime.count() << " times" << std::endl;
}

Common Performance Traps and Avoidance Methods

Trap 1: Frequent Middle Insertions in vector

// ❌ Performance trap: Frequent insertions in the middle of vector
void badVectorUsage() {
    std::vector<int> vec;
    
    for (int i = 0; i < 10000; ++i) {
        vec.insert(vec.begin(), i);  // O(n) operation, overall O(n²)
    }
}

// ✅ Solution 1: Use deque
void goodDequeUsage() {
    std::deque<int> deq;
    
    for (int i = 0; i < 10000; ++i) {
        deq.push_front(i);  // O(1) operation
    }
}

// ✅ Solution 2: Insert in reverse and then reverse
void goodVectorUsage() {
    std::vector<int> vec;
    vec.reserve(10000);
    
    for (int i = 0; i < 10000; ++i) {
        vec.push_back(i);  // O(1) operation
    }
    
    std::reverse(vec.begin(), vec.end());  // O(n) reverse
}

Trap 2: Unnecessary map Lookups

// ❌ Performance trap: Repeated lookups
void badMapUsage(std::map<std::string, int>& scoreMap, const std::string& name) {
    if (scoreMap.find(name) != scoreMap.end()) {  // First lookup
        scoreMap[name] += 10;  // Second lookup (operator[])
    }
}

// ✅ Solution: Use find for a single lookup
void goodMapUsage(std::map<std::string, int>& scoreMap, const std::string& name) {
    auto it = scoreMap.find(name);
    if (it != scoreMap.end()) {
        it->second += 10;  // Directly modify via iterator, no repeated lookup
    }
}

// ✅ Or use the return value of insert
void anotherGoodMapUsage(std::map<std::string, int>& scoreMap, const std::string& name) {
    auto result = scoreMap.insert({name, 0});
    result.first->second += 10;  // Can directly access regardless of insertion
}

Trap 3: Using string as Key in unordered_map without Optimizing Hash

// ❌ Default string hash may perform poorly
std::unordered_map<std::string, int> defaultStringMap;

// ✅ Use a faster hash function (if string characteristics are known)
struct FastStringHash {
    std::size_t operator()(const std::string& s) const {
        // Optimized hash for specific string patterns
        std::size_t hash = 0;
        for (char c : s) {
            hash = hash * 31 + c;  // Simple but effective hash
        }
        return hash;
    }
};

std::unordered_map<std::string, int, FastStringHash> optimizedStringMap;

// ✅ Or consider using string_view to reduce memory allocation
#include <string_view>
std::unordered_map<std::string_view, int> stringViewMap;

Practical Project Case Analysis

Case: Web Server Request Routing

#include <unordered_map>
#include <functional>
#include <string>

class WebRouter {
private:
    // Scenario: Need to quickly find handler based on URL path
    // Analysis: Only need exact match, no range queries or ordered traversal
    // Choice: unordered_map for O(1) lookup performance
    std::unordered_map<std::string, std::function<void()>> routes;
    
public:
    void addRoute(const std::string& path, std::function<void()> handler) {
        routes[path] = handler;  // O(1) average insertion
    }
    
    bool handleRequest(const std::string& path) {
        auto it = routes.find(path);  // O(1) average lookup
        if (it != routes.end()) {
            it->second();  // Execute handler function
            return true;
        }
        return false;
    }
    
    void printAllRoutes() {
        // Note: The order of traversal in unordered_map is uncertain
        // If need to display sorted by path, should collect and sort temporarily
        std::vector<std::string> paths;
        for (const auto& route : routes) {
            paths.push_back(route.first);
        }
        std::sort(paths.begin(), paths.end());
        
        for (const std::string& path : paths) {
            std::cout << "Route: " << path << std::endl;
        }
    }
};

Case: Real-time Data Stream Processing

class DataStreamProcessor {
private:
    // Scenario: Process continuously arriving data, need sliding window calculations
    // Analysis: Need frequent insertions and deletions at both ends, no need for random access
    // Choice: deque provides O(1) operations at both ends
    std::deque<double> slidingWindow;
    size_t windowSize;
    double sum;
    
public:
    DataStreamProcessor(size_t size) : windowSize(size), sum(0.0) {}
    
    void addData(double value) {
        slidingWindow.push_back(value);  // O(1) add to the tail
        sum += value;
        
        if (slidingWindow.size() > windowSize) {
            sum -= slidingWindow.front();   // Remove the oldest data
            slidingWindow.pop_front();      // O(1) delete from the front
        }
    }
    
    double getAverage() const {
        return slidingWindow.empty() ? 0.0 : sum / slidingWindow.size();
    }
    
    double getMedian() const {
        if (slidingWindow.empty()) return 0.0;
        
        // Temporarily sort to calculate median (should use other data structures if called frequently)
        std::vector<double> sorted(slidingWindow.begin(), slidingWindow.end());
        std::sort(sorted.begin(), sorted.end());
        
        size_t mid = sorted.size() / 2;
        return sorted.size() % 2 == 0 ? 
               (sorted[mid - 1] + sorted[mid]) / 2.0 : sorted[mid];
    }
};

Case: Game Leaderboard System

#include <set>
#include <unordered_map>

class GameLeaderboard {
private:
    // Dual data structure design:
    // 1. set for sorting by score, used to get ranking
    // 2. unordered_map for fast lookup by player ID
    std::set<std::pair<int, std::string>> scoreRanking;  // {score, player name}
    std::unordered_map<std::string, int> playerScores;   // Player name -> score
    
public:
    void updateScore(const std::string& player, int newScore) {
        // If player already exists, first remove old record from ranking
        auto it = playerScores.find(player);
        if (it != playerScores.end()) {
            scoreRanking.erase({it->second, player});  // O(log n) deletion
        }
        
        // Add new record
        playerScores[player] = newScore;               // O(1) average update
        scoreRanking.insert({newScore, player});       // O(log n) insertion
    }
    
    std::vector<std::string> getTopPlayers(int count) {
        std::vector<std::string> result;
        auto it = scoreRanking.rbegin();  // Start from the highest score
        
        while (it != scoreRanking.rend() && result.size() < count) {
            result.push_back(it->second);
            ++it;
        }
        
        return result;
    }
    
    int getPlayerRank(const std::string& player) {
        auto it = playerScores.find(player);
        if (it == playerScores.end()) {
            return -1;  // Player does not exist
        }
        
        int score = it->second;
        // Calculate how many players have a higher score than this player
        auto upper = scoreRanking.upper_bound({score, player});
        return std::distance(upper, scoreRanking.end()) + 1;
    }
    
    int getPlayerScore(const std::string& player) {
        auto it = playerScores.find(player);  // O(1) average lookup
        return it != playerScores.end() ? it->second : 0;
    }
};

Container Selection Checklist

Performance Requirement Analysis

Step 1: Identify Primary Operations

// Analyze the most frequent operations in the code
enum class Operation {
    INSERT_END,      // Insert at the end
    INSERT_MIDDLE,   // Insert in the middle
    DELETE_END,      // Delete from the end
    DELETE_MIDDLE,   // Delete from the middle
    RANDOM_ACCESS,   // Random access
    SEQUENTIAL_ACCESS, // Sequential access
    SEARCH,          // Lookup
    SORT             // Sort
};

std::string recommendContainer(const std::vector<Operation>& primaryOps) {
    bool needRandomAccess = std::find(primaryOps.begin(), primaryOps.end(), 
                                     Operation::RANDOM_ACCESS) != primaryOps.end();
    bool frequentMiddleInsert = std::find(primaryOps.begin(), primaryOps.end(), 
                                        Operation::INSERT_MIDDLE) != primaryOps.end();
    bool frequentSearch = std::find(primaryOps.begin(), primaryOps.end(), 
                                   Operation::SEARCH) != primaryOps.end();
    
    if (frequentSearch) {
        return "Consider map or unordered_map";
    } else if (needRandomAccess) {
        return "Choose vector or deque";
    } else if (frequentMiddleInsert) {
        return "Choose list";
    } else {
        return "Default choice is vector";
    }
}

Step 2: Assess Data Size

enum class DataSize {
    SMALL,    // < 1000 elements
    MEDIUM,   // 1000 - 100000 elements
    LARGE     // > 100000 elements
};

std::string adjustForSize(const std::string& baseChoice, DataSize size) {
    if (size == DataSize::SMALL) {
        return baseChoice + " (small data, performance differences are not significant)";
    } else if (size == DataSize::LARGE) {
        return baseChoice + " (large data, choice is more important)";
    }
    return baseChoice;
}

Step 3: Memory Usage Considerations

struct MemoryConstraint {
    bool limitedMemory;     // Is memory constrained
    bool needCacheEfficient; // Is cache friendliness needed
    bool allowOverhead;     // Is extra overhead allowed
};

std::string considerMemory(const std::string& baseChoice, 
                          const MemoryConstraint& constraint) {
    std::string advice = baseChoice;
    
    if (constraint.limitedMemory) {
        advice += "\nNote: Avoid using list and map, they have larger memory overhead";
    }
    
    if (constraint.needCacheEfficient) {
        advice += "\nNote: Prefer vector, avoid linked list structures";
    }
    
    if (!constraint.allowOverhead) {
        advice += "\nNote: Avoid high load factors in unordered_map";
    }
    
    return advice;
}

Conclusion

Core Selection Principles

1. Performance Priority Principle

• • In most cases, <span>vector</span> is the best choice
• • When fast lookup is needed, prioritize<span>unordered_map</span>/<span>unordered_set</span>
• • Only consider<span>list</span> when frequent middle insertions and deletions are needed

2. Memory Efficiency Principle

• • <span>vector</span> has the highest memory efficiency and is cache-friendly
• • Avoid unnecessary pointer overhead (<span>list</span>,<span>map</span>, etc.)
• • Use<span>reserve()</span><span> wisely to avoid reallocations</span>

3. Functional Requirement Principle

• • Need ordered traversal: choose<span>map</span>/<span>set</span>
• • Only need uniqueness: choose<span>unordered_set</span>
• • Need random access: choose<span>vector</span>
• • Need operations at both ends: choose<span>deque</span>

Quick Decision Table

Demand Scenario	Recommended Container	Reason
Store list, occasional lookup	<span>vector</span>	Memory is contiguous, cache-friendly
Frequent insertions and deletions of middle elements	<span>list</span>	O(1) insertion and deletion
Fast lookup of key-value pairs	<span>unordered_map</span>	O(1) average lookup
Ordered traversal of key-value pairs	<span>map</span>	Automatically sorted
Deduplication and need for sorting	<span>set</span>	Uniqueness + order
Only need deduplication	<span>unordered_set</span>	Fast deduplication
Queue operations (both ends)	<span>deque</span>	O(1) operations at both ends
Large number of random accesses	<span>vector</span>	O(1) random access
Stack operations (LIFO)	<span>stack<T, deque<T>></span>	Stack based on deque
Queue operations (FIFO)	<span>queue<T, deque<T>></span>	Queue based on deque
Priority queue	<span>priority_queue<T></span>	Heap based on vector

Best Practice Recommendations

1. Default Selection Strategy

// Default selection order
// 1. vector (universal choice)
// 2. unordered_map (when key-value lookup is needed)
// 3. string (text processing)
// 4. Other containers (for special needs)

2. Performance Optimization Techniques

• • Use<span>reserve()</span><span> to preallocate memory</span>
• • Prefer using<span>emplace()</span><span> series of functions to reduce copy construction</span>
• • Use<span>string_view</span><span> to avoid unnecessary string copies</span>
• • Choose appropriate underlying containers to configure adapters
• • For large data volumes, prioritize cache-friendly containers (vector > deque > list)

3. Debugging and Testing

• • Use performance tests to validate container selection
• • Monitor memory usage
• • Test performance under different data sizes

#STL Containers #Performance Optimization #Data Structures #vector #map #list #Container Selection #C++ Optimization

Choosing the right STL container is a fundamental skill in C++ programming.

Remember: There is no perfect container, only containers suitable for specific scenarios. By understanding the characteristics and performance features of each container, combined with modern C++ optimization techniques, you can make the right choices in real projects and write efficient C++ code.

Like it? Follow me!Give it a thumbs up!Click on “Looking” to see the best!