Подтвердить что ты не робот

Вставка в вектор по ссылке на элемент того же вектора

Мне было интересно, сможет ли кто-то более опытный выяснить, является ли это ошибкой в ​​работе над вектором:

std::vector<int> v{1, 2, 3, 4, 5};
v.insert(v.begin() + 1, v[0]);

Я прошу, потому что элемент для вставки - это ссылка на 0-й элемент в векторе. Если вставка заставляет вектор изменять размер (поскольку его емкость заполнена), то ссылка на v[0] будет признана недействительной, а код может вставить неправильное значение. Вот какой-то псевдокод, который может продемонстрировать:

template <typename T>
void vector_insert_method(Iterator pos, const T& value) {
    if capacity full:
        reallocate array and copy over element
        // if value was reference to elem in this vector,
        // that reference might be invalidated


    insert element

    ++size
}

Эта проблема может быть более реалистичной в параллельной системе.

Аналогичный и связанный с этим вопрос - это то, что происходит, если вы попытаетесь вставить элемент, который появляется после позиции, которую вы пытаетесь вставить. Например, делая что-то вроде v.insert(v.begin(), v[2]), потому что стандарт указывает, что ссылки на элементы после точки вставки недействительны. Гарантировано ли это?

4b9b3361

ОТВЕТЫ

Ответ 1

Оригинальный вопрос спросил...

[..] будет ли это операция с ошибкой для вектора:

v.insert(v.begin(), v[0]);
//              ^^^ no + 1 here!

Вероятно, да, это может быть поведение undefined. Цитирование N3337 ( "почти С++ 11" AFAIK):

[..] Если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются в силе. [..]

§23.3.6.5/1

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

Таким образом, ссылка на v[0] недействительна вызовом (*) до insert. Даже если перераспределение не происходит, insert должен переместить все элементы в более высокие индексы (поэтому v[0] переставляется на v[1]).

Предполагая, что тип элемента не является тривиально разрушаемым, то независимо от того, как выполняется это повторное позиционирование (либо путем перемещения, либо копирования), после того, как v[1] был назначен/построен из v[0], деструктор v[0] должен быть вызван (и его срок службы закончился), прежде чем новый объект (тот, который вы хотите вставить) можно поместить в ячейку памяти v[0]. Таким образом, здесь ваша ссылка превращается в оборванную ссылку, что приводит к поведению undefined, когда он использовал непосредственно после этого, чтобы построить новый v[0]. Нет, насколько я вижу, эту проблему можно обойти, если std::vector::insert() не построить новый объект, а скорее назначить новый объект "старой". Я не уверен, существует ли требование для std::vector вести себя таким образом, хотя его тип элемента должен быть CopyInsertable дает подсказку, что это может быть так.

ОБНОВЛЕНИЕ: Я играл с кодом, представленным в другом ответе, добавляя отладочную отладку, Это не показало того, чего я ожидал (разрушая один элемент, а затем получая его) , но все еще показывает, что стандартная реализация библиотеки (используемая здесь ideone) делает не соответствие стандарту: Он недействителен для ссылок на элементы до точки вставки, даже если емкость достаточно велика. Таким образом, он обходит выше проблемы (но нарушает стандарт... так).

(*): Можно спорить о том, когда происходит эта недействительность. Лучшим ответом на этот вопрос является IMO, что ссылка действительна непосредственно перед вызовом функции insert и недействительна (верна) после возврата из этой функции. Точная точка недействительности не указана.

Измененный вопрос задал тот же вопрос, но с чрезвычайно важной модификацией:

v.insert(v.begin() + 1, v[0]);
//                ^^^^^

Теперь это совершенно другая ситуация. Ссылка на v[0] не обязательно будет признана недействительной вызовом insert, потому что точка вставки находится "позади" v[0]. Единственная проблема, которая может возникнуть, заключается в том, что std::vector должен перераспределить свой внутренний буфер, но в этом случае следующая последовательность операций должна гарантировать правильное поведение:

  • Выделить новую память большей емкости.
  • Построить новый элемент в правильном индексе в области выделенной области памяти.
  • Копировать/Переместить элементы из старой (слишком маленькой) памяти в вновь выделенную область памяти.
  • Свободная старая память.

Ответ 2

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

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

Есть и другое обсуждение здесь и здесь (# 526 ).

Как и во втором случае, похоже, что стандартная библиотека (clang on MacOS) также учитывает ситуацию, когда вы пытаетесь вставить ссылку на элемент в векторе, который расположен после точки, в которую вы пытаетесь вставить, Чтобы проверить это, я написал класс-оболочку для ints, называемый Integer, который ведет себя точно так же, как int, за исключением того, что деструктор устанавливает его внутреннее значение в -5. Поэтому вместо фактического значения вместо вставки std::vector не следует учитывать значение -5.

#include <vector>
#include <iostream>


using std::cout;    using std::endl;
using std::ostream; using std::vector;


class Integer {

public:
    Integer() {
        x = -1;     // default value
    }

    ~Integer() {
        x = -5;     // destructed value. Not 0 so we can clearly see it
    }

    Integer(int r) {
        x = r;
    }

    Integer(const Integer& other) {
        x = other.x;
    }

    Integer operator=(const Integer& other) {
        x = other.x;
        return *this;
    }

    operator int() const{
        return x;
    }

    friend ostream& operator<<(ostream& os, const Integer& thing) {
        os << thing.x;
        return os;
    }

private:
    int x;
};


ostream& operator<<(ostream& os, const vector<Integer> &v) {
    std::copy(v.begin(), v.end(), std::ostream_iterator<Integer>(os, ", "));
    return os;
}

int main() {
    std::vector<Integer> ret {18, 7, 4, 24,11};
    cout << "Before: " << ret << endl;
    ret.insert(ret.begin(), ret[1]);
    cout << "After: " <<  ret << endl;
    return 0;
}

Это дает нам правильный результат:

Before: 18, 7, 4, 24, 11, 
After: 7, 18, 7, 4, 24, 11,