c++ - 更改 std::map 中值的键

Question

我需要更改 std::map 中给定值的键。所以我写了这个方法:

bool alter_key(_Kty oldKey, _Kty newKey)
{
    std::map<_Kty, _Ty>::iterator it = this->find(newKey);
    if(it != end()) //can't replace because newKey is already been used.
        return false;

    it = this->find(oldKey);
    if(it == end()) // empty index.
        return false;

    _Ty value = it->second;
    this->erase(it);
    this->insert(std::pair<_Kty, _Ty>(newKey, value));
    return true;
}

它按预期工作，但是否可以优化此代码？

Answer 1

如果您需要加快特定操作的速度，那么 std::map 可能不是容器的正确选择。话虽这么说，它也可能是正确的选择，所以下一个问题是该功能有什么可以优化的，该功能的较高成本是什么？是查找吗？创建新元素的成本？

如果更高的成本是数据的复制，那么您可能要考虑在算法中避免复制。您可以跳过中间拷贝，而不是从容器复制到局部变量，然后执行额外的拷贝以插入目标:

insert(std::make_pair(new_key,it->value));
erase(it);

如果 value 的复制成本很高但可以移动(右值引用移动，或者默认构造很便宜并且可以交换内容)，您可以利用它:

insert(std::make_pair(new_key,std::move(it->value)));
// alternatively in C++03, for example for large strings or std::vector<> values
value_type& x = *insert(std::make_pair(new_key,ValueType())).first;
swap(x,it->value);

注意事情是如何变得更加复杂和难以理解/维护的。

您可以改进的另一件事是查找。目前，您对容器进行了三次查找:两次确定旧键和新键的存在，第三次插入。你可以减少它。如果您尝试插入并且 key 已经存在，则不会修改它，因此您可以:

using std::swap;
iterator it = find(old_key);
if (it == end()) return false;
std::pair<bool, iterator> ins_res = insert(std::make_pair(new_key,ValueType()));
if (!ins_res.second) return false;
swap(it->second,ins_res.first->second); // swap contents
erase(it);

但是，请考虑 std::map 是否是您数据结构的正确选择...例如，如果查找成本高昂且排序不重要，那么 std::unordered_map 因为它可能具有更好的查找性能。