Гарантируются ли элементы std::vector смежными?
Мой вопрос прост: гарантированно ли смежные элементы std:: vector? В порядке слов, могу ли я использовать указатель на первый элемент std:: vector как C-массив?
Если память мне не помешает, стандарт C++ не дает такой гарантии. Однако требования std:: vector были такими, что было бы практически невозможно их удовлетворить, если элементы не были смежными.
Может кто-нибудь уточнить это?
Пример:
std::vector<int> values;
// ... fill up values
if( !values.empty() )
{
int *array = &values[0];
for( int i = 0; i < values.size(); ++i )
{
int v = array[i];
// do something with 'v'
}
}
7 ответов
Это было пропущено в собственно стандарте C++98, но позже добавлено как часть TR. Предстоящий стандарт C++0x, конечно, будет содержать это как требование.
От n2798 (черновик C++0x):
23.2.6 Шаблон класса вектор [вектор]
1 Вектор - это контейнер последовательности, который поддерживает итераторы произвольного доступа. Кроме того, он поддерживает (амортизируется) операции вставки и удаления с постоянным временем в конце; вставить и стереть в середине взять линейное время. Управление хранилищем осуществляется автоматически, хотя могут быть даны подсказки для повышения эффективности. Элементы вектора хранятся непрерывно, а это означает, что если v является вектором, где T - некоторый тип, отличный от bool, то он подчиняется тождеству &v[n] == &v[0] + n для всех 0 <= n
Как указывалось в других ответах, содержимое вектора гарантированно будет непрерывным (исключая странности bool).
Комментарий, который я хотел добавить, заключается в том, что если вы сделаете вставку или удаление в векторе, что может заставить вектор перераспределить его память, то вы сделаете все ваши сохраненные указатели и итераторы недействительными.
Стандарт фактически гарантирует, что vector непрерывен в памяти и что &a[0] может быть передан C функция, которая ожидает массив.
Исключением из этого правила является vector<bool> который использует только один бит на bool таким образом, хотя он имеет непрерывную память, он не может быть использован как bool* (это широко считается ложной оптимизацией и ошибкой).
Кстати, почему вы не используете итераторы? Вот для чего они.
Как уже говорили другие, vector внутренне использует непрерывный массив объектов. Указатели на этот массив должны рассматриваться как недействительные, когда любая неконстантная функция-член называется IIRC.
Тем не менее, есть исключение!
vector<bool> имеет специализированную реализацию, предназначенную для экономии места, так что каждый bool использует только один бит. Базовый массив не является непрерывным массивом арифметики bool и vector<bool> не работает как vector<T> было бы.
(Полагаю, также возможно, что это может быть верно для любой специализации вектора, так как мы всегда можем реализовать новую. Однако, std::vector<bool> является единственной ошибочной стандартной специализацией, при которой простая арифметика указателей не будет работать.)
Я нашел этот поток, потому что у меня есть случай использования, где векторы, использующие непрерывную память, являются преимуществом.
Я учусь использовать объекты буфера вершин в OpenGL. Я создал класс-обертку, который будет содержать буферную логику, поэтому все, что мне нужно сделать, это передать массив с плавающей точкой и несколько значений конфигурации для создания буфера. Я хочу иметь возможность генерировать буфер из функции на основе пользовательского ввода, поэтому длина не известна во время компиляции. Делать что-то вроде этого было бы самым простым решением:
void generate(std::vector<float> v)
{
float f = generate_next_float();
v.push_back(f);
}
Теперь я могу передать плавающие вектора в виде массива в функции буфера OpenGL. Это также устраняет необходимость в sizeof для определения длины массива.
Это гораздо лучше, чем выделять огромный массив для хранения чисел с плавающей точкой и надеяться, что я увеличил его, или создать собственный динамический массив с непрерывным хранилищем.
Векторные контейнеры реализованы в виде динамических массивов; Как и обычные массивы, векторные контейнеры хранят свои элементы в смежных местах хранения, что означает, что к их элементам можно обращаться не только с помощью итераторов, но и с помощью смещений на обычных указателях на элементы.