Гарантируются ли смежные элементы std :: vector?

Question

Мой вопрос прост: гарантированно ли смежные элементы 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'
    }
}

Answer 1

Это было пропущено в собственно стандарте C ++ 98, но позже добавлено как часть TR. Предстоящий стандарт C ++ 0x, разумеется, будет содержать это как требование.

От n2798 (черновик C ++ 0x):

23.2.6 Вектор шаблона класса [вектор]

1 Вектор - это контейнер последовательности, который поддерживает итераторы произвольного доступа. Кроме того, он поддерживает (амортизируется) операции вставки и удаления с постоянным временем в конце; вставить и стереть в середине взять линейное время. Место хранения Управление осуществляется автоматически, хотя могут быть даны подсказки для повышения эффективности. Элементы вектор хранится смежно, это означает, что если v является вектором, где T некоторого типа, другого чем bool, то он подчиняется тождеству & v [n] == & v [0] + n для всех 0 <= n <v.size (). </p>

Answer 2

Как указывалось в других ответах, содержимое вектора гарантированно будет непрерывным (исключая странности bool).

Комментарий, который я хотел добавить, заключается в том, что если вы сделаете вставку или удаление в векторе, что может заставить вектор перераспределить его память, то все ваши сохраненные указатели и итераторы станут недействительными.

Answer 3

Стандарт фактически гарантирует, что vector является непрерывным в памяти и что &a[0] может быть передано функции C, которая ожидает массив.

Исключением из этого правила является vector<bool>, которое использует только один бит на bool, таким образом, хотя оно и имеет непрерывную память, его нельзя использовать как bool* (это широко считается ложной оптимизацией и ошибка).

Кстати, почему вы не используете итераторы? Вот для чего они.

Answer 4

Как уже сказали другие, vector внутренне использует непрерывный массив объектов. Указатели на этот массив должны рассматриваться как недействительные, когда любая неконстантная функция-член называется IIRC.

Однако есть исключение !!

vector<bool> имеет специализированную реализацию, предназначенную для экономии места, так что каждый логический элемент использует только один бит. Базовый массив не является непрерывным массивом bool, а арифметика массива на vector<bool> не работает, как vector<T>.

(Полагаю, также возможно, что это может быть справедливо для любой специализации вектора, поскольку мы всегда можем реализовать новую. Однако std::vector<bool> является единственной ошибочной стандартной специализацией, при которой простая арифметика указателей не работа.)

Answer 5

Я нашел этот поток, потому что у меня есть случай использования, где векторы, использующие непрерывную память, являются преимуществом.

Я учусь использовать объекты буфера вершин в OpenGL. Я создал класс-обертку, который будет содержать буферную логику, поэтому все, что мне нужно сделать, это передать массив с плавающей точкой и несколько значений конфигурации для создания буфера. Я хочу иметь возможность генерировать буфер из функции на основе пользовательского ввода, поэтому длина не известна во время компиляции. Делать что-то подобное было бы самым простым решением:

void generate(std::vector<float> v)
{
  float f = generate_next_float();
  v.push_back(f);
}

Теперь я могу передать плавающие вектора в виде массива в функции буфера OpenGL. Это также устраняет необходимость в sizeof для определения длины массива.

Это гораздо лучше, чем выделять огромный массив для хранения чисел с плавающей точкой и надеяться, что я увеличил его, или создать собственный динамический массив с непрерывным хранилищем.

Answer 6

Да, элементы std :: vector гарантированно будут смежными.

Answer 7

cplusplus.com:

Векторные контейнеры реализованы в виде динамических массивов; Как и обычные массивы, векторные контейнеры хранят свои элементы в смежных местах хранения, что означает, что к их элементам можно обращаться не только с помощью итераторов, но и с помощью смещений на обычных указателях на элементы.