1. std::map 的基本特点

• 有序关联容器，按 key 排序存储。
• 内部通常为 红黑树（平衡二叉搜索树）。
• key 唯一，value 可修改。
• 查找、插入、删除复杂度均为 O(log n)。

---

2. 删除元素的基本方法

2.1 使用 key 删除

std::map<int, std::string> m = {{1,"a"}, {2,"b"}, {3,"c"}};

// 删除 key=2 的元素
size_t removed = m.erase(2);  // 返回删除元素数量（0 或 1）

• 复杂度：O(log n)
• 注意：如果 key 不存在，返回 0。
• 适用场景：知道要删除的元素 key。

---

2.2 使用迭代器删除单个元素

auto it = m.find(3);
if(it != m.end()) {
    m.erase(it);
}

• 复杂度：O(log n)（查找）+ O(1)（删除节点）
• 优点：可以在迭代过程中安全删除元素（需注意 ++it 避免失效）
• 注意：erase(it) 会使该迭代器失效，但其他迭代器不受影响。

---

2.3 使用迭代器范围删除

// 删除 key 从 1 到 2（不包含 2）
m.erase(m.begin(), m.find(2));

• 复杂度：O(log n + k)，k 为删除元素个数

• 注意：

  • 左闭右开区间 [first, last)。
  • 删除范围过大时，仍是高效操作，因为底层红黑树会做局部重平衡。

---

2.4 清空整个 map

m.clear();  // 删除所有元素

• 复杂度：O(n)
• 效果：调用每个元素的析构函数，释放内存。

---

3. 删除元素的迭代安全写法

在遍历 map 时删除元素，需要小心迭代器失效问题：

3.1 正确写法

for(auto it = m.begin(); it != m.end(); ) {
    if(it->second == "b") {
        it = m.erase(it);  // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

• 核心：erase 返回指向下一个元素的迭代器，避免使用已失效的迭代器。
• 错误示例：

for(auto it = m.begin(); it != m.end(); ++it) {
    if(it->second == "b") {
        m.erase(it);  // 错误！it 失效，下一步 ++it 未定义行为
    }
}

---

4. 删除元素时的复杂度分析

方法	时间复杂度	备注
erase(key)	O(log n)	单元素删除
erase(iterator)	O(1) 删除节点 + O(log n) 重平衡	已知迭代器，删除效率高
erase(iterator_first, iterator_last)	O(k + log n)	k 为删除元素个数
clear()	O(n)	遍历析构每个元素

小结：若要删除大量元素，使用范围删除比单个 key 删除更高效。

---

5. 高级技巧

5.1 条件删除（lambda + erase_if）

C++20 提供 std::erase_if：

#include <map>
#include <algorithm>

std::map<int,std::string> m = {{1,"a"}, {2,"b"}, {3,"c"}};

// 删除 value == "b" 的元素
std::erase_if(m, [](auto &pair){ return pair.second == "b"; });

• 简化遍历删除操作
• 底层安全迭代器处理
• 兼容 STL 容器，包含 vector/map/set

5.2 使用 find + 条件删除

auto it = m.find(2);
if(it != m.end() && it->second == "b") {
    m.erase(it);
}

• 适用于复杂条件判断

---

6. 内存与性能注意点

1. erase 会调用元素的析构函数，复杂对象可能开销大。

2. 如果大量删除后还要插入新元素，map 内部可能会频繁重平衡，考虑：

   • 使用 unordered_map（哈希表）删除复杂度均摊 O(1)
   • 批量删除而不是循环单个删除

3. 对于大数据 SLAM 系统，频繁删除 map 中点云或特征索引时，可以：

   • 使用 内存池 存储 value，避免频繁分配/释放
   • 或使用 std::vector + 索引表 做批量逻辑删除，提高缓存局部性

---

7. std::map 的各种删除元素综合示例

示例1
下面展示 std::map 的各种删除元素方法，包括：按 key 删除、按 iterator 删除、按条件删除（比如满足某个条件的元素），并配合一些遍历操作来看效果。

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

int main() {
    // 创建一个 std::map
    std::map<int, std::string> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"},
        {4, "date"},
        {5, "elderberry"}
    };

    std::cout << "初始 map:" << std::endl;
    for (const auto& [key, value] : myMap) {
        std::cout << key << " -> " << value << std::endl;
    }

    // 方法1：按 key 删除
    std::cout << "\n删除 key=2 的元素" << std::endl;
    myMap.erase(2); // 返回值是删除的元素数量
    for (const auto& [key, value] : myMap) {
        std::cout << key << " -> " << value << std::endl;
    }

    // 方法2：按 iterator 删除
    std::cout << "\n删除第一个元素" << std::endl;
    auto it = myMap.begin();
    myMap.erase(it);
    for (const auto& [key, value] : myMap) {
        std::cout << key << " -> " << value << std::endl;
    }

    // 方法3：按条件删除（删除 key > 3 的元素）
    std::cout << "\n删除 key > 3 的元素" << std::endl;
    for (auto iter = myMap.begin(); iter != myMap.end(); ) {
        if (iter->first > 3) {
            iter = myMap.erase(iter); // erase 返回下一个有效 iterator
        } else {
            ++iter;
        }
    }
    for (const auto& [key, value] : myMap) {
        std::cout << key << " -> " << value << std::endl;
    }

    // 方法4：清空整个 map
    std::cout << "\n清空整个 map" << std::endl;
    myMap.clear();
    std::cout << "map 大小: " << myMap.size() << std::endl;

    return 0;
}

输出示例：

初始 map:
1 -> apple
2 -> banana
3 -> cherry
4 -> date
5 -> elderberry

删除 key=2 的元素
1 -> apple
3 -> cherry
4 -> date
5 -> elderberry

删除第一个元素
3 -> cherry
4 -> date
5 -> elderberry

删除 key > 3 的元素
3 -> cherry
4 -> date

清空整个 map
map 大小: 0

---

示例2
下面一个更高级的示例，演示如何在循环中 安全删除满足复杂条件的多个元素，同时避免 iterator 失效问题。这里用 std::map::erase 返回的新 iterator 来保证安全。

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

int main() {
    std::map<int, std::string> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"},
        {4, "date"},
        {5, "elderberry"},
        {6, "fig"},
        {7, "grape"}
    };

    std::cout << "初始 map:" << std::endl;
    for (const auto& [key, value] : myMap) {
        std::cout << key << " -> " << value << std::endl;
    }

    // 高级删除：删除所有 key 为奇数或者 value 长度 > 5 的元素
    for (auto it = myMap.begin(); it != myMap.end(); ) {
        if (it->first % 2 != 0 || it->second.length() > 5) {
            // erase 返回删除元素后的下一个有效 iterator
            it = myMap.erase(it);
        } else {
            ++it;
        }
    }

    std::cout << "\n删除奇数 key 或 value 长度 > 5 的元素后:" << std::endl;
    for (const auto& [key, value] : myMap) {
        std::cout << key << " -> " << value << std::endl;
    }

    return 0;
}

输出示例：

初始 map:
1 -> apple
2 -> banana
3 -> cherry
4 -> date
5 -> elderberry
6 -> fig
7 -> grape

删除奇数 key 或 value 长度 > 5 的元素后:
4 -> date
6 -> fig

重点说明：

1. 不要在循环中直接用 ++it 和 erase(it) 分开，因为 erase(it) 会使当前 iterator 失效。
2. 正确方式：用 it = myMap.erase(it)，erase 会返回下一个有效 iterator。
3. 这种方法适用于复杂条件删除，非常安全。

---