c++ - 如何正确(但有效地)实现类似 "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 有可能引用同一 vector 中的项目，after 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) 没有引用 vector 中已经存在的范围。

但是我们该怎么做呢？根据 C++，如果它们不引用同一个数组，那么指针比较将是未定义的!
因此编译器可能会错误地告诉我们这些项目没有别名，而实际上它们确实有，从而给我们带来不必要的 O(n) 减速。

可能的解决方案和注意事项

一种解决方案是每次 复制整个 vector ，以包含新项，然后丢弃旧拷贝。

但在上面的示例中，我们复制 1000 个项目只是为了插入 1 个项目的场景非常慢，即使我们显然已经有足够的容量。

是否有一种通用的方法可以(正确地)有效地解决这个问题，即在没有混叠的情况下不会受到 O(n) 减速的影响？

Answer 1

您可以使用谓词 std::less 等，它们保证给出总顺序，即使原始指针比较没有。

来自标准[comparisons]/8:

For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not.