CODEWITHSUNDEEP
c++algorithmtemplatesc++17memcpy
Jive Dadson
Jive Dadson

Reputation: 17026

How to deduce contiguous memory from iterator

Somehow, the native stl::copy() algorithm on VC++ (Dinkumware) figures out that it can use memcpy() on data that is trivially copy-able. Is it possible for a mere mortal to do that? - assuming each element is_trivially_copyable.

Does random_access_iterator imply contiguous memory? The standard is not clear to me.

So, if all you have in a template is an iterator or two, is it possible to deduce at compile-time that the underlying array can be copied with memcpy(), and if so how?

EDIT - Here's my motivation. I have a routine that moves a block of data rather than copying it. To get speed when the data are memmove-able, I've made it call stl::copy sometimes. I was wondering if that is the only way. (As a kid, I would always try this at home.)

// 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;
}

EDIT: Kudos to zett42 for finding this related question: Contiguous iterator detection I can't explain how I missed it.

EDIT More: After going down many twisty little passages all the same, I discovered that Dinkum uses secret tags for iterators that are in with the in-crowd, e.g. _Really_trivial_ptr_iterator_tag. So prospects look dim.

My $0.02 worth: It was a beginner's mistake to make iterator_category an ad-hoc type rather than busting out the various traits, like "points_into_contiguous_memory," etc... Since random_access_iterator is an ad-hoc type denoted only with a tag, it cannot be subtyped without breaking legacy applications. So the committee is now kind of stuck. Time to start over, I say.

Oh well.

Upvotes: 4

Views: 1833

Answers (2)

Pranay
Pranay

Reputation: 403

A) No. It just means that a valid mapping of the kind F(iterator +/- n) = iterator.next/prev.....n exists. This does not imply contiguous allocation at all. ( bounds do apply)

B) No. It depends on the implementation. For instance, you might not know what kind of data structure might be received if there is a 2 level of indirection.

The good news?, you need not bother at all. Between the cache and the branch prediction that happens, you would not need to optimize it at all. During run time, The cache line will be filled with the block of contiguous memory you intend to copy, thus it is going to be very fast, and memmove or memcpy will not help much.

You do not guarantee much with modern processors that are going to pipeline your instructions at run time, and they would know if it is contiguous or not.

Upvotes: 1

max66
max66

Reputation: 66200

Does random_access_iterator imply contiguous memory?

Short Answer: No.

Long Answer: depends on the type.

Example: for std::vector (with random access iterator) it's granted that the memory is all values are in a contiguous block of memory that can be accessed from data() method.

For std::deque (also with random access iterator) you know that the memory area is divided in chunks (std::deque is designed do make efficient insert/remove of element in middle) so it's improbable that the memory is contiguous.

Upvotes: 2

Related Questions