如何从迭代器中推断出连续的内存

Question

不知何故，VC++ (Dinkumware) 上的原生 stl::copy() 算法发现它可以对可简单复制的数据使用 memcpy()。凡人有可能做到吗？ - 假设每个元素 is_trivially_copyable.

random_access_iterator是否意味着内存连续？我不清楚标准。

因此，如果模板中只有一个或两个迭代器，是否可以在编译时推断出底层数组可以用 memcpy()，如果是怎么办？

编辑 - 这是我的动力。我有一个移动数据块而不是复制它的例程。为了在数据可移动时获得速度，我有时会调用 stl::copy 。我想知道这是否是唯一的方法。（小时候，我总是会在家里尝试这个。）

// Move a range of values
template<class Ptr, class Ptr2>
inline Ptr2 move(Ptr src, Ptr end, Ptr2 dest) {
    using value_type = std::iterator_traits<Ptr>::value_type;
    if constexpr (std::is_trivially_copyable_v<value_type>) {
        return std::copy(src, end, dest);
    } else {
        while (src != end) {
            *dest = std::move(*src);
            ++src; ++dest;
        }
    }
    return dest;
}

编辑：感谢 zett42 找到了这个相关问题：我无法解释我是如何错过它的。

编辑更多：在经历了许多曲折的小段落之后，我发现 Dinkum 对人群中的迭代器使用秘密标签，例如_Really_trivial_ptr_iterator_tag。所以前景看起来很暗淡。

我的 0.02 美元价值：将 iterator_category 设为临时类型而不是破坏各种特征是初学者的错误，例如 "points_into_contiguous_memory," 等...因为 random_access_iterator是一种仅用标记表示的临时类型，它不能在不破坏遗留应用程序的情况下进行子类型化。所以委员会现在有点卡住了。是时候重新开始了，我说。

好吧。

Answer 1

Does random_access_iterator imply contiguous memory?

简答：否

长答案：取决于类型。

示例：对于 std::vector（使用随机访问迭代器），内存是所有值都在可以从 data() 方法访问的连续内存块中。

对于std::deque（也有随机访问迭代器）你知道内存区域被分成块（std::deque被设计为使中间的元素高效insert/remove）所以内存是连续的是不可能的。

Answer 2

A) 不。这只是意味着存在 F(iterator +/- n) = iterator.next/prev.....n 类型的有效映射。这根本不意味着连续分配。（界限确实适用）

B) 不。这取决于实现。例如，如果存在 2 级间接寻址，您可能不知道会接收到哪种数据结构。

好消息？，你根本不用担心。在缓存和发生的分支预测之间，您根本不需要对其进行优化。在运行时间内，缓存行将被您打算复制的连续内存块填充，因此速度会非常快，memmove 或 memcpy 将无济于事。

对于将在运行时间流水线处理您的指令的现代处理器，您不能保证太多，并且它们会知道它是否连续。

如何从迭代器中推断出连续的内存

How to deduce contiguous memory from iterator

c++

algorithm

templates

memcpy

c++17