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

因此,本质上,这涉及移动元素两次每次插入和擦除,如果您要在向量中间插入和擦除元素。
对于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 指针。

4

3 回答 3

2

你甚至不需要这样做:

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

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

于 2013-04-03T17:14:37.697 回答
0

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

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 回答