C++ 关联式容器 map 与 set 的原理与实践操作

关联式容器是 C++ STL 中的重要组成部分，它们基于键（key）来存储和组织数据。map 和 set 是最常用的两种关联式容器，本文将深入探讨它们的原理、特性和实践操作。

1. 基本概念与分类

1.1 关联式容器概述

关联式容器根据键来存储元素，允许通过键快速查找、插入和删除元素。C++ 中的关联式容器主要分为两类：

• ​有序关联容器​：基于红黑树实现，元素按键自动排序
  • set、multiset
  • map、multimap
• ​无序关联容器​：基于哈希表实现，元素无序但查找效率高
  • unordered_set、unordered_multiset
  • unordered_map、unordered_multimap

1.2 map 与 set 的区别

特性	set	map
​存储内容​	键（key）本身	键值对（key-value pairs）
​元素唯一性​	键唯一	键唯一
​主要用途​	快速查找键是否存在	通过键快速查找对应值
​访问方式​	只能通过迭代器访问键	可通过键访问值，或迭代器访问键值对

2. 底层实现原理

2.1 红黑树基础

set 和 map 通常基于红黑树​（Red-Black Tree）实现，这是一种自平衡的二叉搜索树：

红黑树的特性：

1. 每个节点要么是红色，要么是黑色
2. 根节点是黑色的
3. 每个叶子节点（NIL节点）是黑色的
4. 红色节点的两个子节点都是黑色的
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

时间复杂度：

• 插入：O(log n)
• 删除：O(log n)
• 查找：O(log n)
• 空间：O(n)

2.2 set 的实现原理

set 本质上是一个只包含键的红黑树，所有操作都基于键的比较：

template<typename Key, typename Compare = less<Key>, typename Allocator = allocator<Key>>
class set {
private:
    typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, allocator_type> rep_type;
    rep_type t;  // 底层红黑树
public:
    // 接口方法...
};

2.3 map 的实现原理

map 是基于键值对的红黑树，键用于排序和查找，值用于存储数据：

template<typename Key, typename T, typename Compare = less<Key>, typename Allocator = allocator<pair<const Key, T>>>
class map {
private:
    typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, allocator_type> rep_type;
    rep_type t;  // 底层红黑树
public:
    // 接口方法...
};

3. 基本操作与使用示例

3.1 set 的基本操作

创建与初始化

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    // 空set
    set<int> s1;
    
    // 初始化列表
    set<int> s2 = {3, 1, 4, 1, 5, 9, 2, 6};  // 重复元素会被忽略
    
    // 从其他容器复制
    vector<int> vec = {5, 3, 8, 1, 9};
    set<int> s3(vec.begin(), vec.end());
    
    // 指定比较函数（降序）
    set<int, greater<int>> s4 = {1, 2, 3, 4, 5};
    
    return 0;
}

插入操作

set<int> s;

// 插入单个元素
s.insert(10);
s.insert(20);
s.insert(10);  // 重复插入无效

// 插入多个元素
vector<int> to_insert = {30, 40, 50};
s.insert(to_insert.begin(), to_insert.end());

// 获取插入结果（pair<iterator, bool>）
auto result = s.insert(60);
if (result.second) {
    cout << "插入成功: " << *result.first << endl;
} else {
    cout << "插入失败，元素已存在" << endl;
}

查找与删除

set<int> s = {1, 3, 5, 7, 9};

// 查找元素
auto it = s.find(5);
if (it != s.end()) {
    cout << "找到元素: " << *it << endl;
} else {
    cout << "元素不存在" << endl;
}

// 检查元素是否存在
if (s.count(3) > 0) {
    cout << "元素3存在" << endl;
}

// 删除元素
s.erase(5);                    // 通过值删除
s.erase(s.find(7));            // 通过迭代器删除
s.erase(s.begin(), s.find(9)); // 删除区间 [begin, 9)

// 清空set
s.clear();

遍历操作

set<int> s = {5, 2, 8, 1, 9};

// 正向遍历
cout << "正向遍历: ";
for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
}
cout << endl;

// 反向遍历
cout << "反向遍历: ";
for (auto it = s.rbegin(); it != s.rend(); ++it) {
    cout << *it << " ";
}
cout << endl;

// 范围for循环
cout << "范围for: ";
for (const auto& elem : s) {
    cout << elem << " ";
}
cout << endl;

3.2 map 的基本操作

创建与初始化

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    // 空map
    map<string, int> m1;
    
    // 初始化列表
    map<string, int> m2 = {
        {"apple", 5}, {"banana", 3}, {"orange", 8}
    };
    
    // 从数组初始化
    const char* fruits[] = {"grape", "melon", "pear"};
    int counts[] = {4, 6, 2};
    map<string, int> m3;
    for (size_t i = 0; i < 3; ++i) {
        m3[fruits[i]] = counts[i];
    }
    
    return 0;
}

插入操作

map<string, int> m;

// 使用insert插入
m.insert(pair<string, int>("apple", 5));
m.insert(make_pair("banana", 3));
m.insert({"orange", 8});  // C++11 统一初始化

// 使用下标操作符插入（如果键不存在则创建）
m["grape"] = 4;  // 插入新元素
m["apple"] = 10; // 更新已存在元素的值

// 获取插入结果
auto result = m.insert({"pear", 6});
if (result.second) {
    cout << "插入成功" << endl;
} else {
    cout << "键已存在，当前值: " << result.first->second << endl;
}

访问与修改

map<string, int> m = {{"apple", 5}, {"banana", 3}};

// 使用下标访问（如果键不存在会创建新元素）
cout << "apple数量: " << m["apple"] << endl;
m["banana"] = 7;  // 修改值

// 使用at()访问（键不存在抛出异常）
try {
    cout << "orange数量: " << m.at("orange") << endl;
} catch (const out_of_range& e) {
    cout << "键不存在: " << e.what() << endl;
}

// 使用find安全访问
auto it = m.find("apple");
if (it != m.end()) {
    cout << "找到元素: " << it->first << " -> " << it->second << endl;
    it->second = 15;  // 修改值
}

删除操作

map<string, int> m = {
    {"apple", 5}, {"banana", 3}, {"orange", 8}, {"grape", 4}
};

// 通过键删除
m.erase("banana");

// 通过迭代器删除
auto it = m.find("orange");
if (it != m.end()) {
    m.erase(it);
}

// 删除区间
auto start = m.find("apple");
auto end = m.find("grape");
if (start != m.end() && end != m.end()) {
    m.erase(start, ++end);  // 注意：需要++end指向要删除的最后一个元素的下一个位置
}

// 清空map
m.clear();

4. 高级特性与技巧

4.1 自定义比较函数

#include <iostream>
#include <set>
#include <string>
using namespace std;

// 自定义结构体作为键
struct Person {
    string name;
    int age;
    
    Person(const string& n, int a) : name(n), age(a) {}
    
    // 重载<运算符用于默认比较
    bool operator<(const Person& other) const {
        return age < other.age;  // 按年龄排序
    }
};

// 自定义比较函数类
struct PersonCompare {
    bool operator()(const Person& a, const Person& b) const {
        if (a.name != b.name) {
            return a.name < b.name;  // 先按姓名排序
        }
        return a.age < b.age;        // 姓名相同按年龄排序
    }
};

int main() {
    // 使用默认比较（按年龄）
    set<Person> people1 = {
        {"Alice", 25}, {"Bob", 30}, {"Charlie", 20}
    };
    
    // 使用自定义比较（按姓名，然后年龄）
    set<Person, PersonCompare> people2 = {
        {"Alice", 25}, {"Bob", 30}, {"Charlie", 20}
    };
    
    // 字符串长度比较
    struct StringLengthCompare {
        bool operator()(const string& a, const string& b) const {
            if (a.length() != b.length()) {
                return a.length() < b.length();
            }
            return a < b;
        }
    };
    
    set<string, StringLengthCompare> words = {"a", "bb", "ccc", "dd", "eee"};
    
    return 0;
}

4.2 multimap 和 multiset（允许重复键）

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

int main() {
    // multiset：允许重复键
    multiset<int> ms = {1, 2, 2, 3, 3, 3};
    
    // 插入重复元素
    ms.insert(2);
    ms.insert(2);
    
    cout << "multiset元素: ";
    for (const auto& elem : ms) {
        cout << elem << " ";
    }
    cout << endl;
    
    // multimap：允许重复键
    multimap<string, int> mm;
    mm.insert({"apple", 5});
    mm.insert({"apple", 8});  // 重复键
    mm.insert({"banana", 3});
    mm.insert({"apple", 10}); // 再次重复键
    
    cout << "multimap中apple的数量: " << mm.count("apple") << endl;
    
    // 遍历所有apple条目
    auto range = mm.equal_range("apple");
    for (auto it = range.first; it != range.second; ++it) {
        cout << it->first << ": " << it->second << endl;
    }
    
    return 0;
}

4.3 性能优化技巧

预分配内存

#include <set>
#include <map>

int main() {
    // 预分配内存减少重分配开销
    set<int> s;
    s.reserve(1000);  // 提示预期大小
    
    map<string, int> m;
    // map没有reserve，但可以用以下方式优化
    m.rehash(1000);   // 对于unordered_map有效
    
    return 0;
}

批量操作优化

#include <set>
#include <vector>
#include <algorithm>

int main() {
    vector<int> data = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    set<int> s;
    
    // 低效：逐个插入
    // for (int x : data) s.insert(x);
    
    // 高效：批量构造
    s.insert(data.begin(), data.end());
    
    // 或者使用排序去重后插入
    vector<int> sorted_data = data;
    sort(sorted_data.begin(), sorted_data.end());
    sorted_data.erase(unique(sorted_data.begin(), sorted_data.end()), sorted_data.end());
    s.insert(sorted_data.begin(), sorted_data.end());
    
    return 0;
}

5. 实际应用场景

5.1 统计词频

#include <iostream>
#include <map>
#include <string>
#include <sstream>
using namespace std;

map<string, int> countWordFrequency(const string& text) {
    map<string, int> freq;
    stringstream ss(text);
    string word;
    
    while (ss >> word) {
        // 转换为小写
        transform(word.begin(), word.end(), word.begin(), ::tolower);
        // 移除标点符号
        word.erase(remove_if(word.begin(), word.end(), ::ispunct), word.end());
        
        if (!word.empty()) {
            freq[word]++;
        }
    }
    
    return freq;
}

int main() {
    string text = "Hello world! Hello C++. C++ is powerful. World says hello.";
    auto freq = countWordFrequency(text);
    
    cout << "词频统计:" << endl;
    for (const auto& pair : freq) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    return 0;
}

5.2 缓存实现（LRU缓存模拟）

#include <iostream>
#include <list>
#include <map>
#include <string>
using namespace std;

template<typename KeyType, typename ValueType>
class LRUCache {
private:
    size_t capacity_;
    list<pair<KeyType, ValueType>> items_list_;  // 按访问时间排序
    map<KeyType, typename list<pair<KeyType, ValueType>>::iterator> items_map_;  // 快速查找
    
public:
    LRUCache(size_t capacity) : capacity_(capacity) {}
    
    void put(const KeyType& key, const ValueType& value) {
        // 如果键已存在，先删除旧条目
        auto it = items_map_.find(key);
        if (it != items_map_.end()) {
            items_list_.erase(it->second);
            items_map_.erase(it);
        }
        
        // 如果达到容量上限，删除最久未使用的条目
        if (items_list_.size() >= capacity_) {
            auto last = items_list_.end();
            last--;
            items_map_.erase(last->first);
            items_list_.pop_back();
        }
        
        // 插入新条目到列表头部
        items_list_.emplace_front(key, value);
        items_map_[key] = items_list_.begin();
    }
    
    ValueType get(const KeyType& key) {
        auto it = items_map_.find(key);
        if (it == items_map_.end()) {
            throw out_of_range("Key not found");
        }
        
        // 将访问的条目移到列表头部
        items_list_.splice(items_list_.begin(), items_list_, it->second);
        return it->second->second;
    }
    
    bool exists(const KeyType& key) const {
        return items_map_.find(key) != items_map_.end();
    }
    
    size_t size() const {
        return items_list_.size();
    }
};

int main() {
    LRUCache<string, int> cache(3);
    
    cache.put("one", 1);
    cache.put("two", 2);
    cache.put("three", 3);
    
    cout << "Get 'two': " << cache.get("two") << endl;  // 输出2，并将"two"移到最近使用
    
    cache.put("four", 4);  // 容量已满，会淘汰"one"（最久未使用）
    
    cout << "Contains 'one': " << cache.exists("one") << endl;  // 输出0(false)
    cout << "Contains 'three': " << cache.exists("three") << endl;  // 输出1(true)
    
    return 0;
}

5.3 区间查询

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    set<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15};
    
    // 查询区间 [5, 12) 内的元素
    auto lower = numbers.lower_bound(5);  // 第一个 >=5 的元素
    auto upper = numbers.upper_bound(12); // 第一个 >12 的元素
    
    cout << "区间 [5, 12) 内的元素: ";
    for (auto it = lower; it != upper; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 另一种写法：使用equal_range
    auto range = numbers.equal_range(8);  // 查找键8的区间（由于8不存在，返回插入位置）
    cout << "等于8的区间: [" << (range.first == range.second ? -1 : *range.first) 
         << ", " << (range.first == range.second ? -1 : *range.second) << ")" << endl;
    
    return 0;
}

6. 注意事项与常见陷阱

6.1 迭代器失效问题

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4, 5};
    
    // 错误：在遍历过程中删除元素会导致迭代器失效
    // for (auto it = s.begin(); it != s.end(); ++it) {
    //     if (*it % 2 == 0) {
    //         s.erase(it);  // 错误！it在此处失效
    //     }
    // }
    
    // 正确方式1：使用后置递增
    for (auto it = s.begin(); it != s.end(); ) {
        if (*it % 2 == 0) {
            it = s.erase(it);  // erase返回下一个有效的迭代器
        } else {
            ++it;
        }
    }
    
    // 正确方式2：先收集要删除的元素，然后统一删除
    vector<int> to_delete;
    for (const auto& elem : s) {
        if (elem % 2 == 0) {  // 这里只是示例，实际上上面的循环已经删除了偶数
            to_delete.push_back(elem);
        }
    }
    for (int elem : to_delete) {
        s.erase(elem);
    }
    
    return 0;
}

6.2 键的要求

• ​必须可比较​：键类型必须支持 < 运算符或提供自定义比较函数
• ​拷贝语义​：键必须是可拷贝的（或移动构造的）
• ​const正确性​：map 的键是 const 的，不能修改

#include <map>
#include <iostream>
using namespace std;

struct NonCopyable {
    int value;
    NonCopyable(int v) : value(v) {}
    NonCopyable(const NonCopyable&) = delete;  // 禁止拷贝
    NonCopyable(NonCopyable&&) = default;      // 允许移动
};

bool operator<(const NonCopyable& a, const NonCopyable& b) {
    return a.value < b.value;
}

int main() {
    // map<NonCopyable, int> m;  // 错误：NonCopyable不可拷贝
    // 但 unordered_map 可能可以，因为它使用哈希而不是比较
    
    return 0;
}

7. 总结

7.1 map 与 set 的选择指南

场景	推荐容器	理由
只需要判断元素是否存在	set	更轻量，只存储键
需要键值对应关系	map	直接通过键访问值
需要重复键	multiset/multimap	允许重复元素
追求极致查找性能	unordered_set/unordered_map	O(1)平均查找时间
需要元素有序	set/map	红黑树自动排序
内存敏感	根据数据量选择	红黑树内存开销较大

7.2 核心要点回顾

1. ​底层实现​：set/map 基于红黑树，保证有序性和对数时间复杂度
2. ​键的唯一性​：set/map 不允许重复键，multiset/multimap 允许
3. ​自定义比较​：可以通过重载 < 运算符或提供比较函数类来自定义排序规则
4. ​性能特点​：插入、删除、查找均为 O(log n)，适合需要有序数据的场景
5. ​使用技巧​：合理使用批量操作、预分配内存、注意迭代器失效问题

关联式容器是 C++ 中处理键值数据的高效工具，掌握它们的原理和使用技巧对于编写高性能、可维护的代码至关重要。在实际开发中，应根据具体需求选择合适的容器类型，避免过度设计或不当使用。