1

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

正常に動作しますが、このコードを最適化することは可能ですか?

4

1 に答える 1

3

その特定の操作を高速化する必要がある場合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);

物事がより複雑になり、理解/保守が難しくなることに注意してください。

改善できるもう 1 つの点は、ルックアップです。現在、コンテナーに対して 3 つのルックアップを実行します。2 つは古いキーと新しいキーの存在を判断するため、3 つ目は挿入するためです。それを減らすことができます。挿入を試みたときにキーが既に存在する場合、キーは変更されないため、次のようにすることができます。

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、データ構造にとって a が正しい選択であるかどうかを検討してください。たとえば、ルックアップのコストが高く、順序付けが重要でない場合は、std::unordered_mapルックアップのパフォーマンスが向上する可能性があります。

于 2013-08-22T16:52:07.727 に答える