How to check whether iterators form a contiguous memory zone?

Question

I currently have the following function to read an array or a vector of raw data (_readStream is a std::ifstream) :

template<typename IteratorType> 
inline bool MyClass::readRawData(
    const IteratorType& first, 
    const IteratorType& last, 
    typename std::iterator_traits<IteratorType>::iterator_category* = nullptr
    )
{
    _readStream.read(reinterpret_cast<char*>(&*first), (last-first)*sizeof(*first));
    return _readStream.good();
}

First question : does this function seem ok for you ?

As we read directly a block of memory, it will only work if the memory block from first to last is contiguous in memory. How to check that ?

Pilau

Your function makes a lot of assumptions about how it will be used. It would be better if they were explicit, or at least documented. Among these assumptions: 1) That elements can be serialized by their binary representation in memory. 2) That the endianess of the runtime is the same as that of the one that wrote the data. – Logical

Actually, why use iterators at all when the function is completely non-generic? Its sole purpose is to bulk copy elements bitwise into memory. Rename the function to reflect this, and have it take a pointer and a count instead of iterators... The question in your title is still interesting though :-) – Logical

I have another function to swap the data if the endianness was different so your second point is not a problem. – Pilau

Have to agree with Cameron. This design seems forced into an iterator design. It's a bit strange for an algorithm to try to detect whether the container is contiguous through its iterators. It makes a lot more sense to simply require pointers. Any contiguous container can provide pointers in this case, and pointers work as iterators if you need to use generic algorithms as part of the implementation of your algorithm. – Northampton

I find that this has not be solved elegantly yet. Look here for an update: #42852457 – Rejoin

Answer 1

Leaving aside your sample function, you can never be completely sure that iterators will form a contiguous memory without checking the address of every element between the two.

A reasonable sanity test, though, would be to just check if the memory area between the two is the same as the count between the two:

assert(&*last - &*first == last - first &&
    "Iterators must represent a contiguous memory region");

Logical

I'm quite certain that &*last - &*first is undefined behavior unless *first and *last are part of the same array, and that's the very thing we're trying to determine. – Marlinmarline

@BenjaminLindley I don't think it would be undefined -- it's a mere pointer subtraction. We might get some odd results like negative values if the container is not contiguous, but that would be checked against the distance between the two iterators. I think it's fairly safe to assume that the poster will at least be requiring his algorithm to require random-access iterators from the same container whether or not that container is contiguous. Nevertheless, it's a strange thing the poster is trying to do. – Northampton

@stinky472: Yes, I understand that it's pointer subtraction. What I'm saying is that unless the pointers point to objects in the same array, the subtraction operation is undefined, as per the standard, 5.7.6 – Marlinmarline

@BenjaminLindley Oh wow. I'm so used to seeing lower-level C developers treating pointers like they're integral addresses in one flat, contiguous memory space. I didn't realize the behavior was actually undefined. – Northampton

Benjamin is right, my answer technically invokes undefined behaviour when the assertion condition is false. But casting to uintptr_t would yield the number of memory units (generally bytes) between the two pointers, not the number of elements. – Logical

Answer 2

n4183 is a paper that goes over the idea of adding a contiguous iterator trait. It is currently under consideration for C++1z (hopefully C++17).

Under it, you can do std::is_contiguous_iterator<It>::value and get if It is a contiguous iterator or not. (This will require support from the designer of the iterator).

Uhland

Answer 3

typename std::iterator_traits<IteratorType>::iterator_category* = nullptr

This is useless because std::iterator_traits has a primary template with an unconditonally defined member type iterator_category. It is tacitly assumed that the template parameter is an iterator and that it's a precondition violation if it isn't -- as such you won't get SFINAE but a hard error if the above is attempted with an invalid instantiation.

As we read directly a block of memory, it will only work if the memory block from first to last is contiguous in memory. How to check that ?

I don't know what exact requirements you would put on a 'contiguous in memory' concept. Have you however considered the following?

template<typename T>
bool readRawData(T* first, T* last);

with the precondition that [ first, last ) be a valid pointer-as-iterator range into an array.

If you want to put further requirements on T (e.g. trivial copyability since you make use of read) you can express/document those, too.

Ming