Гарантированно ли смежность элементов std :: vector?

111

Мой вопрос прост: гарантированно ли элементы 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'
    }
}
Мартин Кот
источник
Я знаю, что у вас проблемы, если вы мутируете valuesвнутри этого ifблока. Однако я не знаю ответа на ваш вопрос, поэтому просто оставляю комментарий. :)
Greg D
@Greg: Что за проблема - не могли бы вы немного уточнить?
Реунанен
Я полагаю, он имел в виду, что добавление новых значений может вызвать «перераспределение», которое приведет к тому, что массив станет недействительным.
Martin Cote,
Вызовы values, которые изменяют, в частности, которые изменяют его размер (например, push_back()), могут вызвать перераспределение базового вектора, что делает недействительным указатель, скопированный в array. Тот же принцип лежит в основе использования vector :: iterator вместо указателя на вектор. :)
Greg D
1
Да, я поставил символы вокруг значений, чтобы прояснить, что я говорю о самом классе, а не о значениях, содержащихся в нем. :) Неудачное название и все такое. Я не думаю, что это действительно проблема в общем случае, когда этот вопрос актуален - зачем кому-то захватывать указатель на память, а затем начинать сбрасывать вектор вместо использования указателя? Глупость.
Грег Д.

Ответы:

118

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

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

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

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

dirkgently
источник
3
Это также указано в ISO 14882, 2-е издание: Раздел 23.2.4 [lib.vector]: «Элементы вектора хранятся непрерывно, что означает, что если v - это вектор <T, Allocator>, где T - это какой-то тип, отличный от bool, то он подчиняется тождеству & v [n] == & v [0] + n для всех 0 <= n <v.size (). "
Майк Кэрон,
4
so s, TR, TC, :) На самом деле C ++ 03 также называется C ++ 98-TC1 (техническое исправление) из того, что я читал
Йоханнес Шауб - litb
2
А как насчет векторов векторов? Внутренние векторы сразу после внутренних векторов последней группы?
хусейн тугрул буюкисик
1
@huseyin tugrul buyukisik вы узнали ответ на этот вопрос? Мне также интересно, как это работает
Дэвид Дориа
1
@huseyin tugrul buyukisik Это, конечно, правда, но последовательные примеры std::vectorявляются смежными. Например .: в std::vector<std::vector<int>> vэлементах v[0], v[1]... сохраняются впоследствии в памяти, но элемент v[0].back()и v[1].front()не гарантируется.
jarzec
27

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

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

Билл Линч
источник
1
Элементы по-прежнему будут храниться в непрерывном блоке памяти, просто он будет в другом месте. Вопрос был конкретно о смежности.
Дима
2
Но существующие указатели и итераторы станут недействительными.
Билл Линч,
Хорошая точка зрения. Вы должны вставить это в свой ответ, чтобы прояснить, что вы имеете в виду.
Дима
самый полезный ответ для меня
CoffeDeveloper
Теперь я знаю, почему в моей программе вчера произошел сбой, когда я перебирал ее в двойном цикле, удаляя определенные элементы :) Спасибо!
user2891462
9

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

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

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

Моти
источник
1
> Кстати, почему вы не используете итераторы? Вот для чего они нужны. Возможно, он читал новую статью Алексанреску по этой теме: boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/…
Неманья Трифунович
Спасибо за ссылку, я перейду к своему списку чтения (я стараюсь не пропускать статьи Александресу)
Мотти,
Мвахаха, кажется, сейчас все говорят об этой презентации. Послушайте, дискуссия по этому поводу все еще горячая: groups.google.com/group/comp.lang.c++.moderated/browse_thread/…
Йоханнес Шауб - litb
Если вы ее внимательно прочитаете, статья Александреску на самом деле не говорит «Не используйте итераторы в C ++», она говорит «Проверьте D». Подход, который он описывает в этой статье, поразительно похож на любые существующие языки и фреймворки, вобравшие в себя функциональное наследие (List, Scheme, Haskell), и я серьезно сомневаюсь, что еще один синтаксис на основе C является идеальной отправной точкой для улучшения обработка списков. Некоторое время назад в прошлом году я кратко пытался убедить его направить свои значительные таланты на улучшение уже устоявшегося языка, такого как C #, но безуспешно! :)
Дэниел Эрвикер
6

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

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

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

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

Wuggy
источник
Пользователь не имеет права специализироваться std::vector, и все другие векторы должны использовать непрерывное хранилище. Следовательно, std::vector<bool>это (к счастью) единственный странный стандартный вектор. (Я твердо придерживаюсь мнения, что эту специализацию следует исключить и заменить, например, a std::dynamic_bitsetс почти такой же функциональностью. Это неплохая структура данных, это просто не вектор.)
Arne Vogel
3

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

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

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

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

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

NobodyImportant
источник
2
эта функция не имеет для меня никакого смысла. вы хотите передать ссылку или указатель на себя, vа не на vсебя? потому что vтолько передача вызовет создание копии внутри функции, которая перестанет существовать после завершения функции. Таким образом, вы нажимаете что-то на вектор только для того, чтобы удалить вектор, когда функция завершится.
johnbakers 05
1

cplusplus.com:

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

Игорь Окс
источник
1

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

Benoît
источник
Правильно. Думаю, я использую их слишком много :)
Бенуа