C++ STL 容器

概述

STL（Standard Template Library）容器是C++标准库提供的数据结构模板。容器封装了常用的数据结构，提供统一的接口和高效的实现。本章介绍序列容器、关联容器、无序容器的使用方法和性能特点。

📦 序列容器

vector - 动态数组

#include <iostream>
#include <vector>
#include <algorithm>

class VectorDemo {
public:
    static void basicOperations() {
        std::cout << "=== vector基本操作 ===" << std::endl;
        
        // 初始化
        std::vector<int> vec1;                    // 空向量
        std::vector<int> vec2(5, 10);            // 5个10
        std::vector<int> vec3{1, 2, 3, 4, 5};    // 初始化列表
        
        // 添加元素
        vec1.push_back(1);
        vec1.push_back(2);
        vec1.emplace_back(3);  // 就地构造
        
        // 访问元素
        std::cout << "第一个元素: " << vec1[0] << std::endl;
        std::cout << "最后一个元素: " << vec1.back() << std::endl;
        
        // 迭代器
        std::cout << "所有元素: ";
        for (auto it = vec1.begin(); it != vec1.end(); ++it) {
            std::cout << *it << " ";
        }
        std::cout << std::endl;
        
        // 范围for循环
        std::cout << "范围for: ";
        for (const auto& element : vec1) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }
    
    static void capacityManagement() {
        std::cout << "\n=== vector容量管理 ===" << std::endl;
        
        std::vector<int> vec;
        
        std::cout << "初始容量: " << vec.capacity() << std::endl;
        
        for (int i = 0; i < 10; ++i) {
            vec.push_back(i);
            std::cout << "大小: " << vec.size() 
                      << ", 容量: " << vec.capacity() << std::endl;
        }
        
        // 预分配空间
        std::vector<int> vec2;
        vec2.reserve(100);
        std::cout << "预分配后容量: " << vec2.capacity() << std::endl;
        
        // 缩减容量
        vec.shrink_to_fit();
        std::cout << "缩减后容量: " << vec.capacity() << std::endl;
    }
    
    static void modifyOperations() {
        std::cout << "\n=== vector修改操作 ===" << std::endl;
        
        std::vector<int> vec{1, 2, 3, 4, 5};
        
        // 插入
        vec.insert(vec.begin() + 2, 99);  // 在位置2插入99
        
        // 删除
        vec.erase(vec.begin());           // 删除第一个元素
        vec.erase(vec.begin(), vec.begin() + 2);  // 删除范围
        
        // 查找和算法
        auto it = std::find(vec.begin(), vec.end(), 99);
        if (it != vec.end()) {
            std::cout << "找到99在位置: " << std::distance(vec.begin(), it) << std::endl;
        }
        
        // 排序
        std::sort(vec.begin(), vec.end());
        
        std::cout << "最终结果: ";
        for (int n : vec) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    VectorDemo::basicOperations();
    VectorDemo::capacityManagement();
    VectorDemo::modifyOperations();
    
    return 0;
}

deque - 双端队列

#include <iostream>
#include <deque>
#include <algorithm>

class DequeDemo {
public:
    static void demonstrate() {
        std::cout << "=== deque双端队列 ===" << std::endl;
        
        std::deque<int> dq;
        
        // 双端添加
        dq.push_back(1);
        dq.push_back(2);
        dq.push_front(0);
        dq.push_front(-1);
        
        std::cout << "双端添加后: ";
        for (int n : dq) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 随机访问
        std::cout << "第二个元素: " << dq[1] << std::endl;
        std::cout << "第三个元素: " << dq.at(2) << std::endl;
        
        // 双端删除
        dq.pop_front();
        dq.pop_back();
        
        std::cout << "双端删除后: ";
        for (int n : dq) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 中间插入删除
        dq.insert(dq.begin() + 1, 10);
        dq.erase(dq.end() - 1);
        
        std::cout << "中间操作后: ";
        for (int n : dq) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
};

list - 双向链表

#include <iostream>
#include <list>
#include <algorithm>

class ListDemo {
public:
    static void demonstrate() {
        std::cout << "\n=== list双向链表 ===" << std::endl;
        
        std::list<int> lst{3, 1, 4, 1, 5};
        
        // 链表特有操作
        lst.push_front(0);
        lst.push_back(6);
        
        std::cout << "初始链表: ";
        for (int n : lst) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 排序（链表专用）
        lst.sort();
        std::cout << "排序后: ";
        for (int n : lst) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 去重
        lst.unique();
        std::cout << "去重后: ";
        for (int n : lst) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 反转
        lst.reverse();
        std::cout << "反转后: ";
        for (int n : lst) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 合并
        std::list<int> lst2{2, 7, 8};
        lst2.sort();
        lst.merge(lst2);
        
        std::cout << "合并后: ";
        for (int n : lst) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
};

🗂️ 关联容器

set - 有序集合

#include <iostream>
#include <set>
#include <string>

class SetDemo {
public:
    static void demonstrate() {
        std::cout << "\n=== set有序集合 ===" << std::endl;
        
        std::set<int> s{3, 1, 4, 1, 5, 9, 2, 6};  // 自动去重和排序
        
        std::cout << "set内容: ";
        for (int n : s) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 插入
        auto [it, inserted] = s.insert(7);
        std::cout << "插入7: " << (inserted ? "成功" : "失败") << std::endl;
        
        auto [it2, inserted2] = s.insert(3);  // 重复元素
        std::cout << "插入3: " << (inserted2 ? "成功" : "失败") << std::endl;
        
        // 查找
        if (s.find(4) != s.end()) {
            std::cout << "找到元素4" << std::endl;
        }
        
        if (s.count(10) > 0) {
            std::cout << "找到元素10" << std::endl;
        } else {
            std::cout << "未找到元素10" << std::endl;
        }
        
        // 删除
        s.erase(1);
        auto it_range = s.equal_range(5);
        s.erase(it_range.first, it_range.second);
        
        std::cout << "删除后: ";
        for (int n : s) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    }
    
    static void customComparator() {
        std::cout << "\n=== 自定义比较器 ===" << std::endl;
        
        // 降序set
        std::set<int, std::greater<int>> desc_set{3, 1, 4, 1, 5};
        
        std::cout << "降序set: ";
        for (int n : desc_set) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 自定义比较器
        auto cmp = [](const std::string& a, const std::string& b) {
            return a.length() < b.length();
        };
        
        std::set<std::string, decltype(cmp)> str_set(cmp);
        str_set.insert("hello");
        str_set.insert("hi");
        str_set.insert("world");
        str_set.insert("cpp");
        
        std::cout << "按长度排序: ";
        for (const auto& s : str_set) {
            std::cout << s << " ";
        }
        std::cout << std::endl;
    }
};

map - 有序映射

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

class MapDemo {
public:
    static void demonstrate() {
        std::cout << "\n=== map有序映射 ===" << std::endl;
        
        std::map<std::string, int> word_count;
        
        // 插入方式
        word_count["hello"] = 1;
        word_count.insert({"world", 2});
        word_count.emplace("cpp", 3);
        
        // 访问
        std::cout << "hello出现次数: " << word_count["hello"] << std::endl;
        std::cout << "world出现次数: " << word_count.at("world") << std::endl;
        
        // 遍历
        std::cout << "所有单词统计:" << std::endl;
        for (const auto& [word, count] : word_count) {
            std::cout << word << ": " << count << std::endl;
        }
        
        // 查找
        auto it = word_count.find("cpp");
        if (it != word_count.end()) {
            std::cout << "找到 " << it->first << ": " << it->second << std::endl;
        }
        
        // 删除
        word_count.erase("hello");
        
        std::cout << "删除hello后大小: " << word_count.size() << std::endl;
    }
    
    static void multimap_demo() {
        std::cout << "\n=== multimap多重映射 ===" << std::endl;
        
        std::multimap<std::string, int> multi_map;
        
        multi_map.insert({"apple", 100});
        multi_map.insert({"apple", 200});
        multi_map.insert({"banana", 150});
        multi_map.insert({"apple", 300});
        
        std::cout << "multimap内容:" << std::endl;
        for (const auto& [key, value] : multi_map) {
            std::cout << key << ": " << value << std::endl;
        }
        
        // 查找范围
        auto range = multi_map.equal_range("apple");
        std::cout << "apple的所有值: ";
        for (auto it = range.first; it != range.second; ++it) {
            std::cout << it->second << " ";
        }
        std::cout << std::endl;
    }
};

🔗 无序容器

unordered_set - 哈希集合

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <string>

class UnorderedDemo {
public:
    static void unordered_set_demo() {
        std::cout << "\n=== unordered_set哈希集合 ===" << std::endl;
        
        std::unordered_set<int> uset{3, 1, 4, 1, 5, 9, 2, 6};
        
        std::cout << "unordered_set内容: ";
        for (int n : uset) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
        
        // 性能信息
        std::cout << "桶数量: " << uset.bucket_count() << std::endl;
        std::cout << "负载因子: " << uset.load_factor() << std::endl;
        std::cout << "最大负载因子: " << uset.max_load_factor() << std::endl;
        
        // 查找性能：O(1)平均
        auto start = std::chrono::high_resolution_clock::now();
        bool found = uset.find(5) != uset.end();
        auto end = std::chrono::high_resolution_clock::now();
        
        std::cout << "查找结果: " << (found ? "找到" : "未找到") << std::endl;
    }
    
    static void unordered_map_demo() {
        std::cout << "\n=== unordered_map哈希映射 ===" << std::endl;
        
        std::unordered_map<std::string, int> umap;
        
        // 插入
        umap["apple"] = 100;
        umap["banana"] = 200;
        umap["orange"] = 150;
        
        // 遍历（顺序不确定）
        std::cout << "unordered_map内容:" << std::endl;
        for (const auto& [key, value] : umap) {
            std::cout << key << ": " << value << std::endl;
        }
        
        // 查找性能
        auto it = umap.find("apple");
        if (it != umap.end()) {
            std::cout << "快速找到: " << it->first << std::endl;
        }
        
        // 自定义哈希
        struct Point {
            int x, y;
            bool operator==(const Point& other) const {
                return x == other.x && y == other.y;
            }
        };
        
        struct PointHash {
            size_t operator()(const Point& p) const {
                return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
            }
        };
        
        std::unordered_set<Point, PointHash> point_set;
        point_set.insert({1, 2});
        point_set.insert({3, 4});
        
        std::cout << "点集合大小: " << point_set.size() << std::endl;
    }
};

📊 容器性能比较

性能测试

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <unordered_set>
#include <chrono>
#include <random>

class PerformanceTest {
public:
    static void compareInsertion() {
        std::cout << "\n=== 插入性能比较 ===" << std::endl;
        
        const int N = 100000;
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(1, 1000000);
        
        // vector尾部插入
        {
            std::vector<int> vec;
            vec.reserve(N);
            
            auto start = std::chrono::high_resolution_clock::now();
            for (int i = 0; i < N; ++i) {
                vec.push_back(dis(gen));
            }
            auto end = std::chrono::high_resolution_clock::now();
            
            auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
            std::cout << "vector尾部插入: " << duration.count() << "ms" << std::endl;
        }
        
        // list插入
        {
            std::list<int> lst;
            
            auto start = std::chrono::high_resolution_clock::now();
            for (int i = 0; i < N; ++i) {
                lst.push_back(dis(gen));
            }
            auto end = std::chrono::high_resolution_clock::now();
            
            auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
            std::cout << "list插入: " << duration.count() << "ms" << std::endl;
        }
        
        // set插入
        {
            std::set<int> s;
            
            auto start = std::chrono::high_resolution_clock::now();
            for (int i = 0; i < N; ++i) {
                s.insert(dis(gen));
            }
            auto end = std::chrono::high_resolution_clock::now();
            
            auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
            std::cout << "set插入: " << duration.count() << "ms" << std::endl;
        }
        
        // unordered_set插入
        {
            std::unordered_set<int> us;
            
            auto start = std::chrono::high_resolution_clock::now();
            for (int i = 0; i < N; ++i) {
                us.insert(dis(gen));
            }
            auto end = std::chrono::high_resolution_clock::now();
            
            auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
            std::cout << "unordered_set插入: " << duration.count() << "ms" << std::endl;
        }
    }
};

int main() {
    VectorDemo::basicOperations();
    VectorDemo::capacityManagement();
    VectorDemo::modifyOperations();
    
    DequeDemo::demonstrate();
    ListDemo::demonstrate();
    
    SetDemo::demonstrate();
    SetDemo::customComparator();
    
    MapDemo::demonstrate();
    MapDemo::multimap_demo();
    
    UnorderedDemo::unordered_set_demo();
    UnorderedDemo::unordered_map_demo();
    
    PerformanceTest::compareInsertion();
    
    return 0;
}

---

总结

STL容器提供了丰富的数据结构选择，各有特点和适用场景：

容器分类

• 序列容器: vector, deque, list, array
• 关联容器: set, map, multiset, multimap
• 无序容器: unordered_set, unordered_map等

性能特点

容器	随机访问	插入	删除	查找
vector	O(1)	O(1)尾部	O(n)	O(n)
deque	O(1)	O(1)两端	O(n)	O(n)
list	O(n)	O(1)	O(1)	O(n)
set	O(n)	O(log n)	O(log n)	O(log n)
unordered_set	O(n)	O(1)平均	O(1)平均	O(1)平均

选择指南

• 频繁随机访问: vector
• 双端操作: deque
• 频繁中间插入删除: list
• 需要排序去重: set
• 快速查找: unordered_set
• 键值对存储: map/unordered_map

STL容器是C++程序的基础构件，选择合适的容器能显著提升程序性能。