Перемещение элемента вектора в вектор во время развертывания: vector.push_back(вектор[0])

ProgramBox

Перемещение элемента вектора в вектор во время развертывания: vector.push_back(вектор[0])

Post author:admin
Запись опубликована:2 мая, 2023
Post category:Вопросы по программированию

#c #vector

#c #вектор

Вопрос:

Я создаю пользовательский векторный класс на C . У меня есть вопрос о таком коде:

     vector<T> vec;
    vec.push_back(one);
    vec.push_back(two);
    vec.push_back(vec[0]);

Определение push_back выглядит следующим образом:

     void push_back(const T amp; v)

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

     if (size == capacity)
    {
        allocate new storage
        copy old values into new storage
        // 2
        delete old storage
        fix pointers and counters
    }
    // 1
    copy v at the end of storage

Проблема возникает, если мы хотим переместить элемент, который уже находится в векторе, А вектор должен расширяться (размер равен его емкости). Если мы сделаем это ( vec.push_back(vec[0]) ), то в // 1 он уже освобожден. Поэтому нам нужно иметь его копию. Другая альтернатива — добавить его во время расширения, где-нибудь в // 2 , но это не кажется привлекательным.

Как бы вы это решили?

1. Я бы просто сделал это по вашему //2 — что в этом плохого? Один путь кода для «обычного» сценария, другой для исключения.

2. Не удаляйте старое хранилище до самого конца функции.

3. Кстати, почему вы не перераспределяете? функция realloc () гарантированно сохранит данные старого блока, поэтому, если вы используете индексы вместо указателей, все должно быть в порядке

4. @drhirsch: realloc можно использовать, только если управление памятью осуществляется с помощью malloc и free , и если объекты ограничены типами POD.

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

Ответ №1:

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

Если это так, позиция индекса (не указатель!) на местоположение данных в векторе найдена. Это не изменится, даже если базовый буфер будет перераспределен. Как только буфер был расширен (независимо от того, связано ли это с фактическим перераспределением или нет), элемент данных может быть безопасно скопирован из позиции индекса.

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

Надеюсь, это поможет.

1. Я думал об этом, и я вижу один недостаток сохранения позиции индекса. Рассмотрим вектор struct foo { int a, b, c, d; } . Foo имеет длину 16 байт. Используя приведения, я могу добавить объект в ((char*)vector_start 8) — with a = v[0].c, b = v[0].d, c = v[1].a, d = v[1].b . Это грубо, но возможно.

2. Да, я думаю, довольно грубо, наверняка. Я не очень хорошо знаю стандарт, но если такое использование контейнера разрешено, я был бы удивлен. Я думаю, вам следует использовать только push_back () подлинные элементы данных, а не только произвольные байты. Приведение в стиле C, подобное этому (кстати, вам также пришлось бы приводить обратно к vector::value_type!), уже приведет к сбоям для общих типов объектов c , даже если это может иметь смысл для специального случая, который вы создали.

Ответ №2:

Еще одна вещь, которую следует учитывать, — это безопасность исключений: что произойдет, если выделение памяти или копирование объекта завершится неудачей? Вы должны попытаться заставить свой класс вести себя как можно лучше в этом случае. Рассмотрим следующие гарантии:

Нет гарантии: если что-то пойдет не так, объект может находиться в недопустимом состоянии
Слабая гарантия: если что-то пойдет не так, объект находится в неопределенном, но допустимом состоянии
Надежная гарантия: если что-то пойдет не так, объект не изменится
Гарантия «Без выброса»: ничто не может пойти не так.

Вы не можете достичь последнего здесь, поскольку у вас нет контроля над распределителем памяти или объектами, которые будут скопированы. Однако «сильная» гарантия возможна при использовании двухэтапного подхода: выполните работу, которая может завершиться неудачей «на стороне», таким образом, чтобы это не повлияло на видимое состояние; как только это будет выполнено успешно, обновите постоянное состояние, используя операции, которые не могут завершиться неудачей (такие как обновление указателей и удаление старой памяти — если удаление дает гарантию «без выброса», что обычно и должно быть).

Таким образом, более безопасная для исключений версия может выглядеть примерно так:

 if (new_size > capacity) {
    allocate new storage, controlled by a local smart pointer
    copy old values
    copy new values
    update state, releasing the smart pointer
    delete old storage
} else {
    copy new values
}

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

Ответ №3:

Я бы отложил удаление старого хранилища:

 if (size == capacity)
    {
        allocate new storage
        copy old values into new storage
        fix pointers and counters, but keep one pointer at the old storage
    }
    copy v at the end of storage
    delete old storage