gpt4 book ai didi

c++ - 如何正确(但有效地)实现类似 "vector::insert"的东西? (指针别名)

转载 作者:塔克拉玛干 更新时间:2023-11-02 23:32:08 29 4
gpt4 key购买 nike

考虑 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 有可能引用同一 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) 减速的影响?

最佳答案

您可以使用谓词 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.

关于c++ - 如何正确(但有效地)实现类似 "vector::insert"的东西? (指针别名),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12031781/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com