如何正确(但有效地)实现像"vector :: insert"这样的东西？(指针别名)

Question

考虑这个假设的实现vector:

template<class T>  // ignore the allocator
struct vector
{
    typedef T* iterator;
    typedef const T* const_iterator;

    template<class It>
    void insert(iterator where, It begin, It end)
    {
        ...
    }

    ...
}

问题

我们在这里面临一个微妙的问题:
有可能begin并且end在之后 引用同一向量中的项目where.

例如,如果用户说:

vector<int> items;
for (int i = 0; i < 1000; i++)
    items.push_back(i);
items.insert(items.begin(), items.end() - 2, items.end() - 1);

如果It不是指针类型,那我们就没事了.
但是我们不知道,所以我们必须检查它[begin, end)是否指向已经在向量内的范围.

但是我们怎么做呢？根据C++,如果它们不引用相同的数组,那么指针比较将是未定义的!
所以编译器可能会错误地告诉我们这些项不是别名,实际上它们确实是这样,给了我们不必要的O(n)减速.

潜在的解决方案和警告

一种解决方案是每次复制整个矢量,包括新项目,然后丢弃旧副本.

但是在上面的示例中,这种情况非常缓慢,我们要复制1000个项目只是为了插入1个项目,即使我们显然已经有足够的容量了.

有没有一种通用的方法(正确地)有效地解决这个问题,即在没有任何混叠的情况下没有遭受O(n)减速？

Answer 1

您可以使用谓词std::less等,即使原始指针比较没有,也可以保证总顺序.

从标准[comparisons]/8:

对于templates,less,greater_equal和less_equal,任何指针类型的特化都会产生一个总顺序,即使内置运算符<,>,<=,> =也不行.