Нужно ли std :: string хранить свой символ в непрерывной части памяти?

Я знаю, что в C ++ 98 ни std::basic_string<>, ни std::vector<> не требовалось использовать непрерывное хранилище. Это было воспринято как недосмотр для std::vector<>, как только на это указали, и, если я правильно помню, было исправлено с помощью C ++ 03.

Я кажется помню, что читал об обсуждениях, требующих std::basic_string<> использования непрерывного хранилища, когда C ++ 11 все еще назывался C ++ 0x, но я не следил внимательно за обсуждением тогда, и все еще ограничен C ++ 03 на работе, поэтому я не уверен, что с этим стало.

Итак, требуется ли std::basic_string<> использовать непрерывное хранилище? (Если да, то какая версия стандарта потребовала этого в первую очередь?)

На случай, если вам интересно: это важно, если у вас есть код, передающий результат &str[0] функции, ожидающей записи в непрерывный кусок памяти. (Я знаю про str.data(), но по очевидным причинам старый код его не использует.)


c++ c++17 c++11 language-lawyer c++14
person sbi    schedule 14.10.2015    source источник
comment
Ну, поскольку str.data() должен быть постоянным временем и должен возвращать непрерывный блок памяти, я бы сказал, что да.   -  person Šimon Tóth    schedule 14.10.2015
comment
См. Аналогичные вопросы stackoverflow.com/questions/1986966/ и stackoverflow.com/questions/2256160/, который отвечает на вопрос, но не так тривиально читать.   -  person slaphappy    schedule 14.10.2015
comment
Каковы те очевидные причины не использовать data()? Эта функция также присутствовала в C ++ 03.   -  person Angew is no longer proud of SO    schedule 14.10.2015
comment
@ Mr.kbok: Я видел их обоих, прочитал ответ и подумал, что лучше бы получить обновленный окончательный ответ.   -  person sbi    schedule 14.10.2015
comment
Я совершенно уверен, что в C ++ 03 ответ отрицательный, хотя практически все реализации использовали непрерывную память. Попробую найти ссылку на это.   -  person sbabbi    schedule 14.10.2015
comment
@Angew: В C ++ 03 str.data() вернул const char*.   -  person sbi    schedule 14.10.2015
comment
@sbi А, верно. Меня смутил тот факт, что C ++ 03 определил [] в терминах data(), даже для неконстантной перегрузки!   -  person Angew is no longer proud of SO    schedule 14.10.2015
comment
FWIW, я никогда не видел и не слышал о несовпадающей std::basic_string реализации; любой, кто интересовался этим, вероятно, добавил бы его как отдельный STL rope двойник. Итак, на практике, если бы я был на вашем месте, я бы просто взглянул на стандартные библиотеки C ++ 03 вашей работы (если параноик), а затем код в предположении, что они всегда будут смежными.   -  person Tony Delroy    schedule 14.10.2015
comment
@sbi Это не меняет того факта, что даже в C ++ 03 он должен быть постоянным и непрерывным.   -  person Šimon Tóth    schedule 14.10.2015
comment
@sbi В C ++ 03 str.data() вернул const char* Изменилось ли это в C ++ 11? Такое чувство, будто я чего-то упускаю ...   -  person atkins    schedule 14.10.2015
comment
@Let_Me_Be C ++ 03 разрешил для реализации использовать два отдельных хранилища, одно для operator[] и одно для c_str (не знаю, зачем кому-либо из разработчиков это делать). Это по-прежнему соответствует требованию постоянного времени c_str. Если вы посмотрите на страницу cppreference, вы увидите, что data() + i не требовалось, чтобы он был равен &operator[](i) в 03.   -  person sbabbi    schedule 14.10.2015

Ответы (3)


arrow_upward
27
arrow_downward

стандарт C ++ 11, basic_string 21.4.1.5,

Объекты типа char в объекте basic_string должны храниться непрерывно. То есть для любого объекта basic_string s идентификатор & * (s.begin () + n) == & * s.begin () + n должен выполняться для всех значений n таких, что 0 ‹= n‹ s.size ().

person Rahul Tripathi    schedule 14.10.2015

arrow_upward
15
arrow_downward

В c ++ 03 не было гарантии, что элементы строки будут храниться постоянно. [basic.string] был

  1. Для char-подобного типа charT шаблон класса basic_string описывает объекты, которые могут хранить последовательность, состоящую из переменного числа произвольных символьных объектов (раздел 21). Первый элемент последовательности находится в нулевой позиции. Такая последовательность также называется «строкой», если данный символьный тип ясен из контекста. В остальной части этого раздела charT обозначает такой заданный char-подобный тип. Хранилище для строки выделяется и освобождается по мере необходимости функциями-членами класса basic_string через класс Allocator, переданный в качестве параметра шаблона. Allocator :: value_type должен быть таким же, как charT.
  2. Шаблон класса basic_string соответствует требованиям Последовательности, как указано в (23.1.1). Кроме того, поскольку итераторы, поддерживаемые basic_string, являются итераторами с произвольным доступом (24.1.5), basic_string соответствует требованиям обратимого контейнера, как указано в (23.1). 389 ISO / IEC 14882: 2003 (E)  Шаблон класса ISO / IEC 21.3 basic_string 21 Библиотека строк
  3. Во всех случаях size () ‹= capacity ().

А потом в C ++ 17 тоже изменили

  1. Шаблон класса basic_string описывает объекты, которые могут хранить последовательность, состоящую из переменного числа произвольных символьных объектов, с первым элементом последовательности в нулевой позиции. Такая последовательность также называется «строкой», если тип char-подобных объектов, которые она содержит, ясен из контекста. В остальной части этого раздела тип char-подобных объектов, содержащихся в объекте basic_string, обозначается charT.
  2. Функции-члены basic_string используют объект класса Allocator, переданный в качестве параметра шаблона, для выделения и освобождения хранилища для содержащихся в нем объектов типа char.
  3. Базовая_строка - это непрерывный контейнер (23.2.1).
  4. Во всех случаях size () ‹= capacity ().

акцент мой

Так что до C ++ 17 это не было гарантировано, но теперь это так.

С ограничениями, которые накладывает std::string::data, это отсутствие гарантии почти спорно, поскольку вызов std::string::data дает вам непрерывный массив символов в строке. Таким образом, если реализация не делает это по запросу и в постоянное время, строка будет непрерывной.

На случай, если вам интересно: это важно, если у вас есть код, передающий результат &str[0] функции, ожидающей записи в непрерывный участок памяти. (Я знаю про str.data(), но по очевидным причинам старый код его не использует.)

Поведение operator[] также изменилось. В C ++ 03 у нас было

Возвращает: Если pos ‹size (), возвращает data () [pos]. В противном случае, если pos == size (), версия const возвращает charT (). В противном случае поведение не определено.

Таким образом, только версия const гарантированно имела определенное поведение, если вы попытались &s[0], когда s пусто. В C ++ 11 они изменили его на:

Возвращает: * (begin () + pos), если pos ‹size (). В противном случае возвращает ссылку на объект типа charT со значением charT (), где изменение объекта приводит к неопределенному поведению.

Итак, теперь версии const и не const имеют определенное поведение, если вы пробовали &s[0], когда s пусто.

person NathanOliver    schedule 14.10.2015
comment
Невозможно сделать string::data() функцией постоянного времени, которая возвращает непрерывную последовательность без непрерывного фактического хранения, даже в C ++ 03. - person Šimon Tóth; 14.10.2015
comment
@Let_Me_Be Да, но если стандарт не налагает требования, вы не можете быть уверены, что это произойдет в 100% случаев. Я представляю себе структуру типа deque. - person NathanOliver; 14.10.2015
comment
Стандарт требует, чтобы string::data() содержал то же содержимое, что и содержимое строки, и налагает требование постоянного времени на string::data(). Невозможно иметь структуру, подобную двухсторонней очереди, и поддерживать постоянное ограничение по времени. - person Šimon Tóth; 14.10.2015
comment
@Let_Me_Be Я добавил в ответ оговорку о string::data(). - person NathanOliver; 14.10.2015
comment
Спасибо, что расширили ответ Рахула. Как случайный посетитель C ++, мне приходится обходить популярные обобщения: одно из них заключается в том, что языки, основанные на указателях, не дают никаких гарантий относительно физического расположения любой нетривиальной структуры данных: все, что вы знаете, это то, что данные в структуре будут прозрачно доступный из его указателя. Прозрачно, а не «последовательно путем выполнения арифметических операций с адресами». Следовательно, более ранняя спецификация «соответствует ... обратимому контейнеру», а не «смежный» - и вы можете быть уверены, что предполагая, что непрерывный блок однажды кого-то укусил. - person Nigel Heffernan; 14.10.2015
comment
@Nathan: В последнее десятилетие я постоянно сталкивался с кодом, в котором люди передавали &s[0] (или &*str.begin()) функциям, требующим указатель на первый элемент записываемого массива символов C. Обычно я оставляю такой код в покое (при условии, конечно, что они убедились, что строка не пуста), поскольку никогда не было известной реализации, в которой строка не имела бы непрерывной памяти, и, как я уже сказал, я казалось, он все равно вспомнил о намерении сделать это требованием. Тем не менее, теперь я хотел узнать, было ли это изменение, наконец, сделано. Спасибо! - person sbi; 14.10.2015
comment
Непрерывный контейнер - это не C ++ 11. Это C ++ 17, добавленный N4284. (Другие требования C ++ 11 действительно требуют непрерывного базового хранилища.) - person T.C.; 05.12.2015

arrow_upward
2
arrow_downward

Согласно проекту стандарта N4527 21.4 / 3 Шаблон класса basic_string [basic.string]:

Basic_string - это непрерывный контейнер (23.2.1).

person 101010    schedule 14.10.2015