Концепция непрерывной последовательности C++

Question

Стандартная библиотека C++ предоставляет множество «концепций», которые используются для указания интерфейса для объектов контейнера. Например, std::vector реализует Container, Sequence, RandomAccessContainer и ReversibleContainer концепции.

Есть концепция, определены либо в C++ 03 или C++ 11, который описывает Sequence, который гарантирует непрерывную память между элементами, так что:

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

Это было бы полезно потому что он говорит вам, можете ли вы использовать Контейнер с любой функцией, которая ожидает непрерывный буфер памяти, такой как std::istream::read.

Я знаю, что на практике, только std::vector (и я думаю, что std::string в C++ 11 только) фактически гарантирует базовый непрерывный буфер - но это гарантия уникальной для std::vector или есть определенная «Концепция», который указует generic Sequence класс, который обеспечивает непрерывную память?

Answer 1

С С ++ 03, только std::vector гарантирует, что (23.2.4.1):

Элементы вектора хранятся смежно, а это означает, что если v является вектор, где Т некоторое тип, отличный от bool, тогда он подчиняется личность & v [n] == & v [0] + n для все 0 < = n < v.size().

C++ 11 добавлен std :: array, который является оберткой вокруг массивов фиксированного размера и также имеет те же свойства. Я не думаю, что есть способ узнать, имеет ли какой-либо контейнер такое свойство.

Answer 2

Я обнаружил, что мне нужно много раз идентифицировать типы, выполняющие эту функцию. Я не знаю, является ли изобретение такой особой «концепции» элегантной (представьте, что это концепция, которая включает в себя память, которая не очень абстрактна), но я согласен, что что-то подобное будет полезно.

Между тем, чтобы быть практичным и перевести эту концепцию/требование в чистое требование синтаксиса, давайте пройдем назад. Если мы ограничимся стандартом, то каковы классы, которые гарантируют (или почти гарантируют) соприкосновение? в порядке значимости:

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

Из всех этих, std::vector, std::array, std::string имеют функцию члена под названием .data(). Итак, если этого достаточно для вас, можно положиться на присутствие члена .data() -> T*, чтобы указать непрерывную память.

У вас есть два варианта:

1) сделать усилия использовать функцию-член .data() поднять синтаксическую ошибку, если тип не является непрерывным. (Не сложно, если вы замените, например, t[0] на *t.data())

2) Используйте какой-то SFINAE на .data().

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

Кроме того, C++ 17 имеет std::data обобщающую его ко всем типам с .data() и дополнительно перегружает для T[N] и std::initializer_list<T>. Итак, вы можете заменить ....data() на std::data(...) выше.

Вывод, я думаю, что это хорошо конвенции является то, что если тип имеет data функцию (или .data() в C++ 11), которая возвращает указатель на тип значения, то элементы являются смежными.

(Хорошо, что о std::valarray<T>? Это не работает, если вы не перегружать std::data(std::valarray<T>&). Но кто использует std::valarray так или иначе? Это довольно заброшенный угол C++, я думаю)

Наконец, обратите внимание на пример, который, очевидно, std::map и менее очевидно std::deque не имеет функции .data() (или std::data(...)). boost::multi_array<..., N> имеет член .data() и возвращает указатель на элемент массива, неясно, является ли это непрерывной последовательностью в том смысле, в котором вы хотите (поскольку порядок не очевиден), но в некотором смысле это также непрерывное распределение памяти.

РЕДАКТИРОВАТЬ: Есть два предложения в настоящее время решения этой проблемы (но на уровне итераторов) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3884.pdfhttp://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4284.html

Answer 3

«прилежащей контейнер» находится в предписанном в технических заданиях С ++ 17. От $23.2.1/13 General container requirements [container.requirements.general]:

Непрерывный контейнер представляет собой контейнер, который поддерживает итераторы произвольного доступа ([random.access.iterators]) и чей член типа итератора и const_iterator являются смежными итераторы ([iterator.requirements.general]).

А про "смежных итераторы", $24.2.1/5 In general [iterator.requirements.general]:

итераторы, что дополнительно удовлетворяет требованию, что, для целочисленных значений п и разыменовываемое итератора значений а и (а + N), * (а + п) эквивалентно * (addressof (* a) + n), называются непрерывными итераторами.

std::vector (за исключением std::vector<bool>), std::array и std::basic_string являются смежными контейнерами.