Вставка члена вектора в вектор при расширении: vector.push_back (vector [0])

Question

Я делаю собственный векторный класс в C ++. У меня вопрос по поводу такого кода:

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

Определение push_back следующее:

    void push_back(const T & 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, но это не выглядит красиво.

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

Answer 1

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

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

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

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

Answer 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" здесь предлагает только "слабую" гарантию: если какой-либо объект не удается скопировать, то некоторые, но не все,из новых данных, возможно, были скопированы.Улучшение этого будет стоить либо с точки зрения сложности (предоставляя способ «раскручивать» изменения при сбое), либо с точки зрения скорости и памяти (используя перераспределяющуюся версию, независимо от того, достаточно ли уже памяти).

Answer 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