更改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是昂贵的复制，但是可以移动（无论是rvalue-参考举动，或者是廉价的默认结构，你可以交换的内容），你可以利用它：

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); 

注意的事情如何变得更加错综复杂，更难理解/维持。

您可以改进的另一件事是查找。目前，您在容器中执行三次查找：两次，以确定旧密钥和新密钥的存在性，以及第三次要插入的密钥。你可以减少这一点。如果您尝试插入关键是已经存在，它不会被修改，所以你可以这样做：

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因为它可能具有更好的查找性能。