# C++关联容器解析：有序与无序容器的实现与应用

## 关联容器概述与分类

C++标准库提供了多种关联容器，根据底层实现和特性可分为两大类：有序容器和哈希容器。有序容器基于红黑树实现，保持元素有序性；哈希容器基于哈希表实现，提供平均常数时间的访问性能。

```cpp

#include <map>

#include <set>

#include <unordered_map>

#include <unordered_set>

#include <iostream>

// 基本使用示例

void container_overview() {

    // 有序容器

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

    std::set<int> ordered_set;

    

    // 无序容器

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

    std::unordered_set<int> unordered_set;

}

```

## 有序关联容器：map与set

### 红黑树基础原理

有序容器底层采用红黑树，一种自平衡二叉搜索树。红黑树通过特定规则保持近似平衡，确保操作时间复杂度为O(log n)。

```cpp

// 红黑树节点简化示意

template<typename T>

struct RBTreeNode {

    T value;

    RBTreeNode* left;

    RBTreeNode* right;

    RBTreeNode* parent;

    bool is_red;  // 颜色标记

    

    // 平衡规则：

    // 1. 每个节点非红即黑

    // 2. 根节点为黑

    // 3. 红节点的子节点必须为黑

    // 4. 从任一节点到叶子的所有路径包含相同数量的黑节点

};

```

### std::map：键值对映射容器

```cpp

// map基本操作

void map_demo() {

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

    

    // 插入元素

    student_scores["Alice"] = 95;

    student_scores["Bob"] = 88;

    student_scores.insert({"Charlie", 92});

    

    // 使用emplace提高效率

    student_scores.emplace("David", 87);

    

    // 查找元素

    auto it = student_scores.find("Alice");

    if (it != student_scores.end()) {

        std::cout << "Alice的分数: " << it->second << std::endl;

    }

    

    // 范围查询（利用有序性）

    auto lower = student_scores.lower_bound("B");

    auto upper = student_scores.upper_bound("C");

    for (auto it = lower; it != upper; ++it) {

        std::cout << it->first << ": " << it->second << std::endl;

    }

    

    // 遍历（按键排序）

    for (const auto& [name, score] : student_scores) {

        std::cout << name << " -> " << score << std::endl;

    }

}

```

### std::set：唯一元素集合

```cpp

// set基本操作

void set_demo() {

    std::set<int> unique_numbers;

    

    // 插入元素

    unique_numbers.insert(5);

    unique_numbers.insert(2);

    unique_numbers.insert(8);

    unique_numbers.insert(2);  // 重复，不会被插入

    

    // 检查元素是否存在

    if (unique_numbers.find(5) != unique_numbers.end()) {

        std::cout << "5存在于集合中" << std::endl;

    }

    

    // 遍历（自动排序）

    for (int num : unique_numbers) {

        std::cout << num << " ";

    }

    std::cout << std::endl;

    

    // 集合运算示例

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

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

    

    // 并集

    std::set<int> union_set;

    std::set_union(set1.begin(), set1.end(),

                  set2.begin(), set2.end(),

                  std::inserter(union_set, union_set.begin()));

    

    // 交集

    std::set<int> intersect_set;

    std::set_intersection(set1.begin(), set1.end(),

                         set2.begin(), set2.end(),

                         std::inserter(intersect_set, intersect_set.begin()));

}

```

### 自定义比较函数

```cpp

// 自定义比较器示例

struct CaseInsensitiveCompare {

    bool operator()(const std::string& a, const std::string& b) const {

        return std::lexicographical_compare(

            a.begin(), a.end(),

            b.begin(), b.end(),

            [](char c1, char c2) {

                return std::tolower(c1) < std::tolower(c2);

            });

    }

};

void custom_comparator_demo() {

    // 使用自定义比较器的map

    std::map<std::string, int, CaseInsensitiveCompare> case_insensitive_map;

    

    case_insensitive_map["Apple"] = 1;

    case_insensitive_map["banana"] = 2;

    case_insensitive_map["APPLE"] = 3;  // 视为重复键

    

    std::cout << "元素数量: " << case_insensitive_map.size() << std::endl;

}

```

## 无序关联容器：unordered_map与unordered_set

### 哈希表原理

无序容器基于哈希表实现，通过哈希函数将键映射到桶（bucket）中：

```cpp

// 哈希表简化示意

template<typename K, typename V>

class HashTable {

private:

    struct Node {

        K key;

        V value;

        Node* next;

    };

    

    std::vector<Node*> buckets;

    size_t bucket_count;

    

    // 哈希函数

    size_t hash_function(const K& key) const {

        std::hash<K> hasher;

        return hasher(key) % bucket_count;

    }

    

public:

    // 平均O(1)时间复杂度的查找

    V* find(const K& key) {

        size_t index = hash_function(key);

        Node* current = buckets[index];

        

        while (current) {

            if (current->key == key) {

                return &current->value;

            }

            current = current->next;

        }

        return nullptr;

    }

};

```

### std::unordered_map应用

```cpp

void unordered_map_demo() {

    // 创建unordered_map

    std::unordered_map<std::string, int> word_count;

<"gk.zhaiLimao.com"><"fp.yunruiwater.cn"><"tv.sxyicheng.cn">

    

    // 统计单词频率

    std::vector<std::string> words = {"apple", "banana", "apple", "orange", "banana", "apple"};

    

    for (const auto& word : words) {

        ++word_count[word];  // 自动插入并计数

    }

    

    // 输出统计结果（顺序不确定）

    for (const auto& [word, count] : word_count) {

        std::cout << word << ": " << count << std::endl;

    }

    

    // 哈希表性能参数

    std::cout << "桶数量: " << word_count.bucket_count() << std::endl;

    std::cout << "负载因子: " << word_count.load_factor() << std::endl;

    

    // 调整性能

    word_count.reserve(100);  // 预分配桶

    word_count.max_load_factor(0.75);  // 设置最大负载因子

}

```

### 自定义哈希函数

```cpp

// 自定义哈希函数示例

struct Person {

    std::string name;

    int age;

    

    bool operator==(const Person& other) const {

        return name == other.name && age == other.age;

    }

};

// 自定义哈希函数

struct PersonHash {

    std::size_t operator()(const Person& p) const {

        std::size_t h1 = std::hash<std::string>{}(p.name);

        std::size_t h2 = std::hash<int>{}(p.age);

        return h1 ^ (h2 << 1);  // 组合哈希值

    }

};

void custom_hash_demo() {

    std::unordered_map<Person, std::string, PersonHash> person_data;

    

    Person alice{"Alice", 25};

    Person bob{"Bob", 30};

    

    person_data[alice] = "Engineer";

    person_data[bob] = "Doctor";

    

    for (const auto& [person, job] : person_data) {

        std::cout << person.name << " (" << person.age << "): " << job << std::endl;

<"sr.jsnjz.cn"><"bm.csxthr.com"><"xl.zhaiLimao.com">

    }

}

```

## 有序与无序容器对比

### 性能特征对比

```cpp

void performance_comparison() {

    const int N = 10000;

    

    // 有序容器插入性能

    std::map<int, int> ordered_map;

    auto start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < N; ++i) {

        ordered_map[i] = i * i;

    }

    auto ordered_insert_time = std::chrono::high_resolution_clock::now() - start;

    

    // 无序容器插入性能

    std::unordered_map<int, int> unordered_map;

    start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < N; ++i) {

        unordered_map[i] = i * i;

    }

    auto unordered_insert_time = std::chrono::high_resolution_clock::now() - start;

    

    std::cout << "插入" << N << "个元素：" << std::endl;

    std::cout << "有序map时间: " 

              << std::chrono::duration_cast<std::chrono::milliseconds>(ordered_insert_time).count()

              << "ms" << std::endl;

    std::cout << "无序map时间: " 

              << std::chrono::duration_cast<std::chrono::milliseconds>(unordered_insert_time).count()

              << "ms" << std::endl;

}

```

### 适用场景分析

```cpp

// 场景1：需要有序遍历时使用有序容器

void ordered_traversal_needed() {

    std::map<std::string, double> stock_prices;

    

    // 记录股票价格

    stock_prices["AAPL"] = 150.25;

    stock_prices["GOOGL"] = 2750.50;

    stock_prices["MSFT"] = 310.75;

    

    // 按键排序输出

    std::cout << "股票价格（按键排序）:" << std::endl;

    for (const auto& [symbol, price] : stock_prices) {

        std::cout << symbol << ": $" << price << std::endl;

    }

    

    // 需要范围查询时，有序容器的优势明显

    auto it_low = stock_prices.lower_bound("G");

    auto it_high = stock_prices.upper_bound("M");

}

// 场景2：需要快速查找且不关心顺序时使用无序容器

void fast_lookup_needed() {

    std::unordered_set<std::string> username_cache;

    

    // 检查用户名是否已存在

    auto check_username = [&](const std::string& username) -> bool {

        return username_cache.find(username) != username_cache.end();

    };

    

    username_cache.insert("user1");

    username_cache.insert("user2");

    

    // 快速查找

    if (check_username("user1")) {

        std::cout << "用户名已存在" << std::endl;

    }

}

// 场景3：需要多级映射时

void multi_level_mapping() {

    // 使用map嵌套

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

    

    student_grades["Math"]["Alice"] = 95;

    student_grades["Math"]["Bob"] = 88;

    student_grades["Science"]["Alice"] = 92;

    

    // 访问示例

    int alice_math_grade = student_grades["Math"]["Alice"];

}

```

## 高级应用技巧

### 内存优化与自定义分配器

```cpp

#include <memory_resource>  // C++17

void custom_allocator_demo() {

    // 使用单调缓存分配器优化小对象分配

    std::byte buffer[1024];

    std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)};

    

    std::pmr::unordered_map<int, std::string> fast_map{&pool};

    

    for (int i = 0; i < 100; ++i) {

        fast_map.emplace(i, "value_" + std::to_string(i));

    }

}

```

### 线程安全包装

```cpp

#include <mutex>

template<typename K, typename V>

class ThreadSafeMap {

private:

    std::unordered_map<K, V> map_;

    mutable std::shared_mutex mutex_;

    

public:

    V get(const K& key) const {

        std::shared_lock lock(mutex_);

        auto it = map_.find(key);

        if (it != map_.end()) {

            return it->second;

        }

        return V{};  // 返回默认值

    }

    

    void set(const K& key, const V& value) {

        std::unique_lock lock(mutex_);

        map_[key] = value;

    }

    

    bool contains(const K& key) const {

        std::shared_lock lock(mutex_);

        return map_.find(key) != map_.end();

    }

};

```

## 选择指南与最佳实践

1. **选择有序容器当**：

   - 需要元素保持排序状态

   - 需要范围查询或有序遍历

   - 键类型没有合适的哈希函数

2. **选择无序容器当**：

   - 需要最大查找性能

   - 不关心元素顺序

   - 能够提供良好的哈希函数

3. **通用建议**：

   ```cpp

   // 根据需求选择合适的容器

   template<typename Key, typename Value>

   using ContainerType = std::conditional_t<

       requires { std::hash<Key>{}; } &&  // 键可哈希

       !requires { std::less<Key>{}; },   // 且不要求有序

       std::unordered_map<Key, Value>,    // 选择无序

       std::map<Key, Value>               // 否则选择有序

   >;

   ```

关联容器的选择对程序性能有重要影响。有序容器提供稳定的对数时间复杂度和有序遍历能力，适用于需要排序或范围查询的场景。无序容器提供平均常数时间的访问性能，适用于需要快速查找且不关心顺序的场景。理解它们的底层原理和特性，能够帮助开发者在不同场景下做出合适的选择，编写出既高效又正确的C++代码。