6

考虑这个假设的实现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)
    {
        ...
    }

    ...
}

问题

我们在这里面临一个微妙的问题：和
有可能引用同一向量中的项目，之后。beginend 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) 减速？

4

3 回答 3

6

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

从标准[comparisons]/8：

对于更大、更少、greater_equal 和less_equal 模板，任何指针类型的特化都会产生一个总顺序，即使内置运算符<、>、<=、>= 没有。

于 2012-08-20T03:31:57.113 回答
0

但是我们该怎么做呢？根据 C++，如果它们不引用同一个数组，那么指针比较将是未定义的！

错误的。指针比较是未指定的，不是未定义的。来自 C++03 §5.9/2 [expr.rel]：

[...] 可以比较指向相同类型的对象或函数的指针（在指针转换之后），其结果定义如下：

[...] -
未指定其他指针比较。

因此，在进行昂贵但正确的复制之前测试是否存在重叠是安全的。

有趣的是，C99 与 C++ 的不同之处在于，不相关对象之间的指针比较是未定义的行为。从 C99 §6.5.8/5 开始：

比较两个指针时，结果取决于所指向对象在地址空间中的相对位置。[...] 在所有其他情况下，行为是未定义的。

于 2012-08-20T03:43:33.513 回答
0

实际上，即使它们是常规迭代器也是如此。没有什么能阻止任何人做

std::vector<int> v; 
// fill v 
v.insert(v.end() - 3, v.begin(), v.end());

确定它们是否别名对于任何迭代器的实现都是一个问题。

但是，您缺少的是实现，您不必使用可移植代码。作为实现，你可以做任何你想做的事情。你可以说“好吧，在我的实现中，我遵循 x86 并且<可以>用于任何指针。”。那很好。

于 2012-08-20T03:57:43.353 回答