c++ - 用 old_value 将元素替换为向量中的 new_value - C++

Question

我正在浏览一些遗留代码，并发现了一些可以改进的地方。
根据设计，向量具有指向类的指针，并且向量中的所有元素都是唯一的。

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

因此，本质上，这涉及移动元素两次，每次插入和擦除，如果您要在向量中间插入和擦除元素。
对于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 insert 和erase 是自定义调用，它们还会更新给定元素的left_sibling 和right_sibling 指针。

Answer 1

你甚至不需要这样做：

iterator position = std::find( vector->begin() vector->end(), old_child );
if ( position == vector->end() ) {
    throw NoSuchElement();
}
*position = new_child;

应该做的伎俩 - 没有擦除和插入。

Answer 2

向量擦除返回一个迭代器，指向被擦除后的元素的位置

iter = myvector->erase(i);

然后您可以使用该迭代器进行插入。

myvector->inster(iter, new_value);

或相反。vector insert 返回一个指向插入元素的迭代器

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

myvector->erase(iter);

Answer 3

为什么不使用其中之一？

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

为什么你有这样的复杂性？有没有什么目的。也可能在vector其他地方使用，但您也可以使用集合和向量进行搜索。