关联容器笔记

关联容器总结

有序关联容器

键值的顺序自动排序，键值必须支持 < 操作符

底层数据结构

• 使用平衡树，比如（红黑树）
• 增删查的平均时间复杂度接近 O(log⁡n)

种类

• std::set：集合，包含唯一的键元素。

• std::multiset：多重集合，允许键重复。

• std::map：映射，键值对（键唯一，值可以重复）。

• std::multimap：多重映射，允许键重复的键值对。

无序关联容器

底层数据结构

• 链式哈希
• 增删查的平均时间复杂度接近O(1)

种类

• std::unordered_set：无序集合，包含唯一的键元素。
• std::unordered_multiset：无序多重集合，允许键重复。
• std::unordered_map：无序映射，键唯一。
• std::unordered_multimap：无序多重映射，允许键重复。

方法

• 插入操作

  • insert()：在容器中插入元素，返回一个迭代器和一个布尔值（表示插入是否成功）。对于无序容器，可以传入 hint 迭代器提升效率。

  • emplace()：在容器中原地构造元素，避免不必要的复制或移动操作。

• 删除操作

  • erase()：根据键或迭代器删除元素。返回已删除元素的数量。

• 查找操作

  • find()：返回一个指向指定键的迭代器，若键不存在则返回 end()。

#include <iostream>
#include <map>
#include <unordered_set>

int main() {
    // std::map 示例
    std::map<int, std::string> m;

    // 插入元素
    m.insert(std::make_pair(1, "one"));
    m.emplace(2, "two");
    m[3] = "three";  // 使用下标操作符插入或更新元素

    // 查找元素
    auto it = m.find(1);
    if (it != m.end()) {
        std::cout << "Key 1 found with value: " << it->second << std::endl;  // 输出 "one"
    }
    else {
        std::cout << "Key 1 not found" << std::endl;
    }

    // 删除元素
    m.erase(2);  // 删除键为 2 的元素
    std::cout << "After erase, size of map: " << m.size() << std::endl;

    // 遍历元素
    std::cout << "Elements in map:" << std::endl;
    for (const auto& kv : m) {
        std::cout << kv.first << " => " << kv.second << std::endl;
    }

    // std::unordered_set 示例
    std::unordered_set<int> uset = { 1, 2, 3 };

    // 插入元素
    uset.insert(4);

    // 查找元素
    if (uset.find(3) != uset.end()) {
        std::cout << "Found 3 in unordered_set" << std::endl;
    }
    else {
        std::cout << "3 not found in unordered_set" << std::endl;
    }

    // 删除元素
    uset.erase(1);  // 删除元素 1
    std::cout << "After erase, size of unordered_set: " << uset.size() << std::endl;

    // 遍历元素
    std::cout << "Elements in unordered_set:" << std::endl;
    for (const auto& elem : uset) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

注：vector中push_back与emplace_back的区别

• push_back会调用拷贝构造函数
• emplace_back会调用构造函数原地构造对象