我正在浏览一些遗留代码,并发现了一些可以改进的地方。
根据设计,向量具有指向类的指针,并且向量中的所有元素都是唯一的。
函数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 指针。