Что происходит с указателем, указывающим на элемент в векторе, когда я перетасовываю его?

Ответ 1

Указатель будет продолжать указывать на одно и то же место, поэтому при перетасовке он укажет на любой элемент, который был перемещен в указанное вами местоположение.

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

Уменьшение размера вектора будет зависеть именно от того, как вы это делаете. Один из способов - создать временный вектор как копию текущего вектора, поменять местами два, а затем уничтожить временные (обычно неявно, пуская его из области видимости). Если вы это сделаете, указатели будут временными и будут признаны недействительными, когда они будут уничтожены.

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

Ответ 2

Если вектор перетасовывается без изменения размера, указатель все же указывает на то же место, которое, вероятно, будет содержать другой элемент.

Если размер вектора больше размера, то указатель считается "недействительным" и имеет тот же статус, что и неинициализированный указатель, т.е. его оценка или попытка его чтения вызывает поведение undefined.

Ответ 3

Если я теперь перетасовываю вектор, будет ли он по-прежнему указывать на один и тот же элемент (третий) или он укажет новое местоположение, в котором перемещен элемент, используемый для третьего?

Перемешивание элементов - это просто вопрос копирования/замены элементов через различные "ведра" в массиве, в то время как ваш указатель просто указывает на "эту фиксированную позицию в памяти". Таким образом, он будет указывать на то, что остается в третьей позиции в массиве.

Затем мне нравится сделать вопрос немного более общим: как ведут себя указатели и итераторы к элементам в векторе, когда вектор расширяется, уменьшается или перетасовывается?

Развернуть: все итераторы/ссылки/указатели могут быть признаны недействительными.

Уменьшено: насколько они указывают на элементы перед удалением, они сохраняются действительными, если вы не выполните shrink_to_fit. Итераторы/указатели на удаленные элементы явно недействительны.

Перепутано: вы перемещаете вещи, не вызывая перераспределения, поэтому итераторы и ссылки остаются в силе.

Обратите внимание, что все эти материалы обычно сообщаются в большинстве источников документации на С++.

Концептуальное правило для запоминания для векторов состоит в том, что они всего лишь поле вокруг динамического массива, а итераторы и указатели на элементы концептуально одно и то же (на самом деле std::vector<T>::iterator может быть typedef для T *), То же самое верно для ссылок (которые скрывают указатели).

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

Ответ 4

Адрес не изменится, но значение, сохраненное на этом адресе, будет.

#include <iostream>
#include <algorithm>

int main()
{
    std::vector< int > vect{ 1, 2, 3, 4, 5 };

    std::cout << "Before Shuffle: " << std::endl;
    for( int i = 0; i < vect.size();  ++i )
    {
        std::cout << "Value: " << vect.at( i ) << " Address: " <<  &vect.at( i ) << std::endl;
    }

    auto engine = std::default_random_engine{};
    std::shuffle( vect.begin(), vect.end(), engine);

    std::cout << "After Shuffle: " << std::endl;
    for( int i = 0; i < vect.size();  ++i )
    {
        std::cout << "Value: " << vect.at( i ) << " Address: " <<  &vect.at( i ) << std::endl;
    }

    return 0;
}

Вывод:

Before Shuffle: 
Value: 1 Address: 0x16eb320
Value: 2 Address: 0x16eb324
Value: 3 Address: 0x16eb328
Value: 4 Address: 0x16eb32c
Value: 5 Address: 0x16eb330
After Shuffle: 
Value: 3 Address: 0x16eb320
Value: 1 Address: 0x16eb324
Value: 5 Address: 0x16eb328
Value: 4 Address: 0x16eb32c
Value: 2 Address: 0x16eb330

Ответ 5

На практике вектор является непрерывным буфером данных, поддерживаемым кодом. Каждый элемент устанавливается рядом с следующим по типу массива.

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

Однако стандарт С++ более строгий. Если итератор недействителен, то есть ссылки и указатели на это место. Существует ряд операций, которые могут привести к аннулированию итератора, которые не логически изменяют тот факт, что массив фактически будет тем же самым буфером. Например, если вы .erase элемент, он аннулирует каждый итератор в этом месте и впоследствии.

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

std::shuffle не отменяет никаких итераторов. Он просто меняет значения, хранящиеся там. Таким образом, указатель на n-й элемент будет как на практике, так и теоретически по-прежнему указывать на n-й элемент.

Когда вектор расширяется, если вы расширяете его за пределами .capacity(), все итераторы становятся недействительными. На практике он фактически перемещает данные в новое место, а указатели теперь указывают указатели.

Когда вы уменьшаете (через .erase(it) или .erase(a,b)), все итераторы в первом или после первого аргумента становятся недействительными. Это означает, что ссылки и указатели на эти элементы также недействительны. На практике они теперь будут ссылаться на элементы "далее вниз по цепочке" (если такие элементы существуют), поскольку ни .erase не приведет к перераспределению вашего буфера, но это не гарантируется стандартом.

Существуют и другие операции, которые могут привести к недействительности итераторов. .shrink_to_fit() может, как может vector<X>(vec).swap(vec) (версия сжатия С++ 03), и .reserve() и операции, размер которых превышает .capacity().

Операции, которые вызывают изменение .capcity(), на самом деле делают ваши указатели недействительными (или теми, которые делают указатели выводятся за пределы конца) на практике и теоретически.

Ответ 6

Прочитайте документацию для каждой функции, которую вы вызываете. Если вы не знаете, когда и как вы можете это назвать и что он делает, то почему вы используете его?

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

vector::shrink_to_fit аннулирует все итераторы
vector::resize к тому же или меньшему недействительно точно итераторам за пределами нового размера
vector::resize, чтобы сделать больше недействительными все итераторы

Из стандарта С++ 14 [iterator.requirements.general]:

[P] ointers - итераторы. Эффект разыменования итератора, который был недействителен - undefined.

http://en.cppreference.com/w/cpp/container/vector

std::vector - контейнер последовательности, который инкапсулирует массивы динамических размеров.
Элементы хранятся смежно, что означает, что элементы могут быть доступ к ним не только через итераторы, но и использование смещений на регулярных указатели на элементы.

Итератор     RandomAccessIterator

Недействительность Iterator
swap, std::swap   shrink_to_fit     Всегда & resize     Если вектор изменил емкость, все из них. Если нет, то только после точки вставки.

http://en.cppreference.com/w/cpp/container/vector/resize

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

После vector::shuffle итераторы/указатели не изменяются, но разыгрываются новые значения.

Потому что shuffle использует swap, который оставляет итераторы неизменными:

http://en.cppreference.com/w/cpp/algorithm/random_shuffle

template< class RandomIt, class URNG >
void shuffle( RandomIt first, RandomIt last, URNG&& g );

RandomIt должен удовлетворять требованиям ValueSwappable и RandomAccessIterator.

http://en.cppreference.com/w/cpp/concept/Iterator

Итератор - это базовая концепция, используемая другими типами итераторов: InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, и RandomAccessIterator. Итераторы можно рассматривать как абстракция указателей. [...]

`- lvalues ​​типа It, удовлетворяющий Swappable [...]

http://en.cppreference.com/w/cpp/concept/ValueSwappable

Тип T является ValueSwappable, если   1) Тип T удовлетворяет требованиям Iterator
    2) для любого объекта с возможностью desferencable x типа T (то есть любое значение другое чем конечный итератор), * x удовлетворяет требованиям Спасения.

http://en.cppreference.com/w/cpp/concept/Swappable

using std::swap;
swap(u, t);

После вызова значение t является значением, удерживаемым u перед вызовом, и значение u является значением, удерживаемым t перед вызовом.

Ответ 7

Как уже упоминалось, указатель указывает на местоположение в памяти, независимо от содержимого, которое там есть. На самом деле есть действительно интересные материалы, например, наличие массива из 5 элементов, но распечатка значения в позиции 6, хотя он не входит в объем вашего массива. Получив доступ к массиву с чем-то вроде массива [5], когда вы только объявили его длиной в 5 элементов, вы получите поведение undefined, по существу означающее, что может произойти множество вещей, причем каждый прогон потенциально возвращает что-то полностью другой. См. Комментарии к philipxy ниже для некоторых очень полезных ссылок, вникающих в эту концепцию.

Итак, с этой точки зрения, вот немного кода, который вы могли бы проверить, чтобы увидеть этот эффект.

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> values (5);

    for (int i = 0; i < 5; i++)
        values[i] = i;

    for (int i = 0; i < 5; i++)
        cout << values[i] << " ";

    //Initialise the pointer so that it is pointing at the first element in vector
    int* pointer = &values[0];

    //By incrementing, we expect it to be pointing at the second element, which should be 1
    pointer++;

    cout << endl << "Pointer " << *pointer << endl;

    //Reverse the order of the vector
    reverse(values.begin(), values.end());

    for (int i = 0; i < 5; i++)
        cout << values[i] << " ";

    cout << endl << "Pointer " << *pointer << endl; 

    return 0;
}

Результат этого кода:

Итак, мы видим, что указатель фактически не изменился там, где он указывает, но эта ячейка в памяти была изменена, поэтому разыменование указателя даст другой результат.

Ответ 8

Это полностью зависит от того, как реализован "std::vector". Я не уверен, есть ли любые гарантии на это.

EDIT: Я только что узнал, что стандарт С++ действительно намного строже, чем я думал (благодаря philipxy). Он указывает, что вектор должен внутренне вести себя как массив C. См.

http://herbsutter.com/2008/04/07/cringe-not-vectors-are-guaranteed-to-be-contiguous/

Так что забудьте об остальном, по крайней мере, если у вас есть реализация, которая соответствует хотя бы С++ 03.

Если вы, например, реализуете std::vector как связанный список (вряд ли), то перетасовка, уменьшение размера и т.д. ничего не сделает.

Если "std::vector" внутренне использует что-то вроде "int []" для хранения своих элементов (вероятно), то перетасовка элементов, вероятно, означает, что ваш указатель теперь укажет на другое значение, а затем раньше (что пытался Стево вне).
Если вы измените размер вашего вектора в этом случае, то опять же он полностью зависит от внутренней реализации. Размер может выделять новый "int []" и копировать старое содержимое. В этом случае ваш указатель укажет на теперь нераспределенную память, поэтому весь хаос может сломаться.
Если вам повезет (в зависимости от реализации), то сокращение или увеличение вектора по "маленькой" сумме может ничего не делать (ваш указатель все еще действителен).

Сводка: не делайте этого;-) (используя указатели и впоследствии изменяя свой контейнер).