C++ Contiguous Sequence Concept

Question

The C++ standard library provides a variety of "Concepts" which are used to specify an interface for container objects. For example, std::vector implements the Container, Sequence, RandomAccessContainer, and ReversibleContainer concepts.

Is there a Concept, specified either in C++03 or C++11, that describes a Sequence which guarantees contiguous memory between elements, so that:

static_cast<void*>(&some_sequence[N]) == static_cast<void*>(&some_sequence[0] + N)>

This would be a useful concept because it tells you whether you can use the Container with any function that expects a contiguous memory buffer, such as std::istream::read.

I know that, in practice, only std::vector (and I think std::string in C++11 only) actually guarantee an underlying contiguous buffer - but is this guarantee unique to std::vector or is there a defined "Concept" that indicates a generic Sequence class that provides contiguous memory?

Answer 1

"Contiguous container" is specifed in C++17. From $23.2.1/13 General container requirements [container.requirements.general]:

A contiguous container is a container that supports random access iterators ([random.access.iterators]) and whose member types iterator and const_iterator are contiguous iterators ([iterator.requirements.general]).

And about "contiguous iterators", $24.2.1/5 In general [iterator.requirements.general]:

Iterators that further satisfy the requirement that, for integral values n and dereferenceable iterator values a and (a + n), *(a + n) is equivalent to *(addressof(*a) + n), are called contiguous iterators.

std::vector (except for std::vector<bool>), std::array and std::basic_string are contiguous containers.

Answer 2

I found my self having to identify types fulfilling this feature many times. I don't know if inventing such a special "concept" is elegant (imagine that it is a concept that involves memory, which is not very abstract) but I agree something like this will be useful.

Meanwhile to be practical and translate this concept/requirement into a pure syntax requirement, let's walk backwards. If we restrict ourselves to the standard, what are the classes that guarantee (or almost guarantee) contiguity? in order of relevance:

std::vector<T>
T[N] // !!
std::array<T, N>
std::string
std::initializer_list<T>
std::valarray<T>

Of all these, std::vector, std::array, std::string have a member function called .data(). So, if this is enough for you, could rely on the presence of member .data() -> T* to indicate contiguous memory.

You have two options:

1) Make the effort to use the member function .data() to raise a syntax error if the type is not contiguous. (Not hard if you replace for example t[0] by *t.data())

2) Use some kind of SFINAE on .data().

template<class ContiguousSequence, typename = decltype(std::declval<ContigiousSequence>().data())>
void fun(ContiguousSequence&& s){...} // this function will only work with contiguous data

Moreover, C++17 has std::data which generalizes it to all types with .data() and additionally overloads for T[N] and std::initializer_list<T>. So, you can replace ....data() by std::data(...) above.

The conclusion, I think it is a good convention is that if a type has a data function (or .data() in C++11) that returns a pointer to the value type then the elements are contiguous.

(Ok, what about std::valarray<T>? It doesn't work, unless you overload std::data(std::valarray<T>&). But who uses std::valarray anyway? it is a pretty abandoned corner of C++, I think)

Finally, note for example that obviously std::map and less obviously std::deque don't have a .data() (or std::data(...)) function. boost::multi_array<..., N> has a .data() member and returns a pointer to the array element, it is not clear if this is contiguous sequence in the sense you want (because the order is not obvious) but in some sense it is also a contiguous allocation of memory.

EDIT: There are two proposals currently addressing this issue (but at the level of the iterators) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3884.pdf http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4284.html

Answer 3

From the C++03, only std::vector guarantees that (23.2.4.1):

The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

C++11 added std::array, which a wrapper around fixed-size arrays and would also have the same properties. I don't think there is a way to know if any container has such property.

Answer 4

While this question asks specifically about C++11, I feel it's at least worth noting that C++20 has introduced an applicable concept for this called std::ranges::contiguous_range, since a container basically is a range. For example:

#include <list>
#include <ranges>
#include <vector>

static_assert(not std::ranges::contiguous_range<std::list<int>>);
static_assert(std::ranges::contiguous_range<std::vector<int>>);