C++ 向量的稳定迭代器以及为什么你需要它们

• 下载源代码 - 27.8 KB

引言

在 GoingNative'12 的演讲中，Bjarne 告诉我们 基本上应该用 std::vector 替换所有 std::list 的使用，因为由于缓存一致性，std::vector 在现代硬件上（可能违反直觉地）几乎总是比 std::list 快。 好的。唯一的问题是，当涉及插入或删除操作时，std::vector::iterator 的行为与 std::list::iterator 的行为不同，并且不能直接用作替代品。 实际上，在插入操作（包括 push_back()）时，可能会发生“重新分配”事件，导致所有 std::vector 的迭代器失效。 直言不讳地说，当涉及插入或删除操作时，可以谨慎地认为 std::vector::iterator 不是很实用，而更谨慎地认为它非常危险。 如果我们拥有像 std::list::iterator 一样的 std::vector::iterator 就好了。 您可以考虑一个容器，例如 boost::container::stable_vector，但尽管它的名字是这样，但它实际上并不是一个 vector，并且具有明显不同的性能特征，这将在后面讨论。

另一方面，mse::msevector 是一个 vector，它有像 std::list::iterator 一样的迭代器。 mse::msevector 与 std::vector 非常兼容，可以被认为是 std::vector 的增强或扩展版本。 这种兼容性意味着 mse::msevector::iterator 只是一个普通的 vector 迭代器，它的行为不像 std::list::iterator，但 mse::msevector 具有一个额外的迭代器类型，称为 mse::msevector::ipointer，它确实如此。 也就是说，这种类型的迭代器指向容器中的项目（而不是容器中的位置），当从容器中插入或删除其他元素时，它们不会失效，并且可以与对 std::list::iterator 进行操作的算法一起使用。

Using the Code

要使用 mse::msevector，只需将两个文件 mseprimitives.h 和 msemsevector.h 复制到您的项目中（或“include”目录）。 没有任何其他依赖关系。

#include "msemsevector.h"

int main() {
    mse::msevector<int> v = { 1, 2, 3, 4 };
    mse::msevector<int>::ipointer ip1 = v.ibegin();
    ip1 += 2;
    assert(3 == (*ip1));
    auto ip2 = v.ibegin(); /* ibegin() returns an ipointer */
    v.erase(ip2); /* remove the first item */
    assert(3 == (*ip1)); /* ip1 continues to point to the same item, not the same position */
    ip1--;
    assert(2 == (*ip1));
    for (mse::msevector<int>::cipointer cip = v.cibegin(); v.ciend() != cip; cip++) {
        /* You might imagine what would happen if cip were a regular vector iterator. */
        v.insert(v.ibegin(), (*cip));
    }

    /* Btw, ipointers are compatible with stl algorithms, like any other stl iterators. */
    std::sort(v.ibegin(), v.iend());

    /* And just to be clear, mse::msevector also has the (high performance) std::vector iterators and
    can be used as a drop-in substitue for std::vector. */
    std::sort(v.begin(), v.end());
}

技术考量

将 mse::msevector 与 boost::container::stable_vector 进行比较可能最有启发性。 stable_vector 通过在插入和删除操作期间避免任何元素的重新定位来保持迭代器的有效性。 另一方面，msevector 通过让迭代器在它们被重新定位时主动跟踪它们的目标元素来保持迭代器的有效性。 因此，虽然 msevector 通常比 stable_vector 快得多，但您可以想象一个病态的情况，即容器元素相对较少，但有成千上万甚至数百万个迭代器指向它们，这将减慢 msevector 的插入和删除操作。

stable_vector 的原始作者提供了一个 基准测试。 我们将在基准测试中添加几个 msevector 场景。 一个没有任何 ipointer，另一个有三个 ipointer，配置为指向在每次 insert() 和 push_back() 操作时都会被重新定位的元素。（在 push_back() 操作期间，唯一被重新定位的元素是“结束标记”，除非发生“重新分配”事件，在这种情况下，每个元素都会被重新定位。） 原来的基准测试考虑了小元素（int）和大元素。 在这里我没有考虑大元素。 我的理由是，如果 vector 性能受到其元素的大小或复制成本的影响，您始终可以用较小的元素替换那些元素，这些元素仅包含指向大型对象的指针，以及一个搜索/排序键。

下表显示了相对于最快的执行时间。

	std::vector	msevector	带有 3 个 ipointers 的 msevector	boost stable_vector	std::deque
push_back	1.00	1.14	4.65	10.68	2.03
插入	1.00	1.02	1.01	13.77	5.19
operator[]	1.00	1.42	1.38	9.83	16.70

基准测试环境：msvc2015/x64/Window 7/Haswell

基准测试计时略有噪音，但要点很清楚。ipointer 的“跟踪”开销出现在“push_back”计时中。 这并不是因为 ipointer 开销特别高，而是因为 push_back() 本身就是一个快速操作。 当然与 insert() 相比，ipointer 开销可以忽略不计。 “operator[]”中的开销是由于 msevector 内置的边界检查。 该操作中没有 ipointer 参与。

所以，您拥有了所有可以用来用缓存友好的 vector 替换慢速列表的东西。