C ++ Continuous Sequence Concept

Question

The C ++ Standard Library provides many “concepts” that are used to specify an interface for container objects. For example, std::vector implements the concepts of Container , Sequence , RandomAccessContainer and ReversibleContainer .

Is there a concept, either in C ++ 03 or C ++ 11, that describes Sequence , which guarantees continuous 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 if you can use the Container with any function that expects an adjacent memory buffer, such as std::istream::read .

I know that in practice only std::vector (and I think that std::string only in C ++ 11) actually guarantees a basic adjacent buffer - but this guarantee is unique to std::vector or there is a certain "Concept "which indicates a generic Sequence class that provides continuous memory?

Answer 1

An "adjacent container" is specified in C ++ 17. From $ 23.2.1 / 13 General requirements for containers [container.requirements.general] :

The adjacent container is a container that supports random access iterators ([random.access.iterators]), and those whose iterator and const_iterator members are adjacent iterators ([iterator.requirements.general]).

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

Iterators that additionally satisfy the requirement that for integral values ​​of n and dereferenced values ​​of the iterator a and (a + n), * (a + n) is equivalent to * (addressof (* a) + n) are called adjacent iterators.

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

Answer 2

I found that I need to identify the types that perform this function many times. I don’t know whether it is elegant to invent such a special “concept” (imagine that it is a concept that includes memory, which is not very abstract), but I agree that something like this will be useful.

Meanwhile, to be practical and translate this concept / requirement into a pure syntactic requirement, let me go back. If we restrict ourselves to the standard, then what are the classes that guarantee (or almost guarantee) contact? in order of relevance:

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

Of all this, std::vector , std::array , std::string have a member function called .data() . So, if that's enough for you, you can rely on the presence of the .data() -> T* member to indicate continuous memory.

You have two options:

1) Try using the .data() member function to raise a syntax error if the type is not in contact. (It’s not difficult if you replace, for example, t[0] with *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 

In addition, 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() with std::data(...) above.

The conclusion, I think, is a good convention that if the 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> ?) This does not work unless you overload std::data(std::valarray<T>&) . But who uses std::valarray , in any case, this is a pretty abandoned C ++ corner, I think)

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

EDIT: There are currently two suggestions for solving this problem (but at the iterator level) 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 C ++ 03, only std::vector guarantees that (23.2.4.1):

Elements of the vector are stored adjacent, which means that if v is a vector, where T is some type other than bool, then it obeys the identifier & v [n] == & v [0] + n for all 0 <= n <V .SIZE ().

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