我有一个保持插入顺序的Map，并将其实现为：(1) std::map，保存实际的键和值；(2) 另外一个独立的 vector，按插入顺序存储键。

std::map<std::string, MyObject* obj> map;
std::vector<std::string> orderVector;

有一个用于从Map中删除任意给定键的实用函数，它会同时从 (1) 的Map和 (2) 的顺序向量中移除该键：

void removeEntry(const std::string& key) {    
    auto iter = map.find(key);
    if (iter != map.end()) {
        value = iter->second;
        // ... Perform additional logic, e.g. "delete value"
        // (1) Remove from main map
        map.erase(key);
        // (2) Remove from order vector
        std::erase_if(orderVector, [key](T t) { return t == key; });
    }
}

我还需要一个 removeAllEntries() 函数来清空所有元素。删除必须严格按相反的顺序进行，这也是我使用有序Map的原因。不幸的是我不能在循环中调用我的单一函数，

for (auto it = orderVector.rbegin(); it != orderVector.rend(); ++it) { // Reverse
    removeEntry(orderVector[i]);
}

因为这个子函数也会从 orderVector 中删除元素，而它在单独形式下必须如此。

我不想将单一的 removeEntry 函数改写为返回迭代器，因为它必须以当前形式存在，作为一个普通的 void。两个函数都必须以简单的签名提供，理想情况下其中一个应能从另一个复用。有哪些好的解决办法吗？

我想我可以有一个单独的 removeEntryInMapOnly()，仅执行Map的删除，这样循环是安全的；然后在此之后再执行一个 orderVector.clear() 来清空Order Vector，但在我看来这并不够简洁或优雅。

解决方案

两个函数 [removeEntry()] 和 [removeAllEntries()] 必须提供简单的签名，理想情况下其中一个应能从另一个复用。

不，那将远非理想。由于 removeEntry() 需要从向量中删除任意元素，它本质上是一个线性、O(n) 的操作。如果这个函数被 removeAllEntries() 对每个条目调用，那么复杂度将变成平方级，O(n^2)（即便考虑了向量收缩；参见冒泡排序）。理想情况下，从一个容器中删除所有条目的复杂度应该与容器大小呈线性关系。因此重复使用 removeEntry() 并非理想，尤其是对于关注效率的人。

(为完整起见，因为引文并未指明哪个是“一个”、哪个是“另一个”：使用 removeAllEntries() 来自 removeEntry() 是不可行的，因为那样会删除太多。)

我的首选建议是让别人处理Map与 Vector的交互。Boost.MultiIndex 提供具有多种访问语义的容器，例如一个按键与指针组成的容器，可以通过键查找（映射）或按插入顺序（向量）访问。模板参数的设置可能比较复杂，但一旦设置好，你就能得到一个健壮且高效的实现。

假设你有不使用Boost的理由，下面给出一些处理删除的其他方法。

简单方法

如果目标是保持修改简单，我会倾向于把真正共享的代码（清理）放在一个辅助函数中，由 removeEntry() 和 removeAllEntries() 调用。也就是说，重复使用代码，但不要尝试复用超过有用的部分。复用的代码通过在Map中的查找是O(log n) 的，这使得删除所有条目变成O(n log n)。并不理想，但比O(n^2) 好。

这给出了删除一个条目和删除所有条目时的实现如下：

// (This function should not be part of the public interface.)
// Returns an iterator to the entry in the map.
auto cleanUpEntry(const std::string& key) {
    auto iter = map.find(key);
    if (iter != map.end()) {
        MyObject* value = iter->second;
        // ... Perform additional logic, e.g. "delete value"
    }
    return iter;
}

void removeEntry(const std::string& key) {
    auto iter = cleanUpEntry(key);
    if (iter != map.end()) {
        // (1) Remove from main map
        map.erase(iter);                // NOTE: Not `key`; no need to search the map again.
        // (2) Remove from order vector
        std::erase(orderVector, key);   // NOTE: Simpler than erase_if
    }
}

void removeAllEntries() {
    for (auto it = orderVector.rbegin(); it != orderVector.rend(); ++it) { // Reverse
        cleanUpEntry(*it);
    }
    map.clear();
    orderVector.clear();
}

如果你真的愿意，你可以在每次迭代中从地图中删除一个条目，这会加速后续迭代中的查找。这样代码会略微复杂一些，但不会改变其渐近行为为O(n log n)。（节省的量级大约是O(n)——参见链接。）节省可能在某个性能瓶颈时值得考虑，但前提是确实有瓶颈。

如果清理操作需要访问地图，那么在每次迭代中从Map删除一个条目可能是必需的。希望这里不需要，因为那样会变得很混乱。

高性能方法

要将复杂度降到线性，需要在删除所有元素时消除对Map的查找。如果可以改变数据结构，这很容易实现。

理想情况下，向量除了用于在Map中定位条目之外，不再需要依赖Map的键。具体来说，如果除了 delete value 之外的所有清理都能移到 MyObject 的析构函数中（或者如果在其他上下文中使用 MyObject，则包装 MyObject 的类的析构函数），会很方便。这样向量就可以保存指向 MyObject 的智能指针，而不是字符串。（Map保留的是指向同一对象的原始指针，且非拥有者。）

#include <memory>

struct MyObject {
    ~MyObject() {
        // ... Perform additional logic
    }
};

std::map<std::string, MyObject*> map;
std::vector<std::unique_ptr<MyObject>> orderVector; // NOTE: smart pointers

void removeEntry(const std::string& key) {
    auto iter = map.find(key);
    if (iter != map.end()) {
        // Save the pointer before `iter` is invalidated.
        MyObject* value = iter->second;
        // (1) Remove from main map
        map.erase(iter);
        // (2) Remove from order vector (triggers cleanup)
        std::erase_if(orderVector, [value](const auto& ptr) {
            return ptr.get() == value;
        });
    }
}

void removeAllEntries() {
    for (auto it = orderVector.rbegin(); it != orderVector.rend(); ++it) { // Reverse
        it->reset(); // Triggers cleanup
    }
    map.clear();
    orderVector.clear();
}

这里有一个显著的功能性变化，即在从Map删除项之后再进行清理 removeEntry()。如果这点重要，可以将删除顺序互换，但同样会很快变得混乱。希望清理不会访问Map。

如果需要键

上述方法的一个潜在问题是向量不再对每个条目访问键。这在清理需要用到键来更新某些内容，或向量被用于除删除所有条目之外的任务时，会成为问题。虽然不太可能，但也并非不合理。在这种情况下，把智能指针放到Map中，让向量的条目指向Map的条目。（Map迭代器和引用只有在相关条目被删除时才会失效。）

在这种情形下，析构函数无法完成清理，因为无法将相关的键传递给它。我们又回到一个清理函数，但这个函数不需要进行Map查找，因此时间复杂度为常数时间O(1)，而不是对数时间。因此删除所有元素的总体复杂度仍然是线性O(n)，符合预期。

#include <memory>

// Aliases for readability:
using MapType = std::map<std::string, std::unique_ptr<MyObject>>;
using MapPair = MapType::value_type;

MapType map;
std::vector<MapPair*> orderVector;

void cleanUpEntry(const MapPair& entry) {
    const std::string& key = entry.first;
    const MyObject& value = *entry.second;
    // ... Perform additional logic
}

void removeEntry(const std::string& key) {
    auto iter = map.find(key);
    if (iter != map.end()) {
        cleanUpEntry(*iter);
        // (1) Remove from order vector
        std::erase(orderVector, &*iter);
        // (2) Remove from main map
        map.erase(iter);
    }
}

void removeAllEntries() {
    for (auto it = orderVector.rbegin(); it != orderVector.rend(); ++it) { // Reverse
        cleanUpEntry(**it);
    }
    map.clear();
    orderVector.clear();
}

这里有一个显著的功能性变化，即 removeEntry() 先从向量移除，再从Map中移除。这是为了避免失效问题，如有需要也可变通。和我其他的功能改动一样，希望这不会带来实质性影响。