0

私はいくつかのレガシーコードを調べていて、改善できるものを見つけました。
ベクターにはクラスへのポインターがあり、設計に従って、すべての要素はベクター内で一意です。

関数ReplaceValは、次の方法で、ベクター内の old_value を持つ要素を new_value に置き換えます。 

iterator i, i_e;
i   = vector->begin();
i_e = vector->end ();
for (; i != i_e; ++i)
{
    if ((*i) == old_child)
        break;
}
// Insertion
    vector->insert_call(new_child, i);

// Since, the pointers are invalidated, do another find for erase
    i   = vector->begin();
    i_e = vector->end ();
    for (; i != i_e; ++i)
    {
        if ((*i) == old_child)
            break;
    }
// Finally, erase the old_value
    vector->erase_call(i);

したがって、ベクトルの途中で要素を挿入および消去する場合、本質的に、これには要素の 2 回のシフトが含まれます。 n回の挿入と削除呼び出しの場合、m 個の要素が毎回シフトされる場合、複雑さは平均で です。
O(n*m)

std::replaceここ@ MSDNのドキュメントとstd_replace_exampleで言及されているように、これを使用すれば改善できると思います。

std::replaceの複雑さは、O(n)old_value と new_value & 1 代入操作の比較です。それは次のように簡単です：

replace (vector.begin( ), vector.end( ), old_value , new_value);

私が間違っている場合は、私を修正し、見逃したものについてフィードバックを共有してください。
PS 挿入と消去はカスタム呼び出しであり、特定の要素の left_sibling と right_sibling へのポインターも更新します。

4

3 に答える 3

0

vector erase は、消去された要素に続く要素の位置を指すイテレータを返します。

iter = myvector->erase(i);

次に、そのイテレータを使用して挿入できます。

myvector->inster(iter, new_value);

またはその逆。vector insert は、挿入された要素を指すイテレータを返します

iter = myvector->inster(i, new_value);

myvector->erase(iter);
于 2013-04-03T17:17:35.417 に答える
0

これらのいずれかを使用しないのはなぜですか？

  • std::set
  • std::multiset
  • std::unordered_set
  • std::unordered_multiset

なぜあなたはそのような複雑さを持っているのですか？何か目的はありますか？vectorは他の場所でも使用されている可能性がありますが、ベクトルとともにセットを検索に使用することもできます。

于 2013-04-03T17:18:05.743 に答える