2

Пишу собственный вектор. Нужно адекватно написать функции типа push_back(), а ничего лучше, чем это в голову не лезет:

Vector<T> v(_size+1);

for(int i=0;i<_size;i++) 
{
    v.at(i) = ptr[i];
}
v.at(v._size-1) = value; 

delete[] this->ptr;

ptr = v.ptr;
_size = v._size;

Посоветуйте что-нибудь адекватное, пожалуйста. Желательно идею, а не реализацию.

2 ответа 2

5

Это примерно так и делается. Для вашей реализации могу предложить несколько улучшений.
1) Лучше заказывайте просто сырую память. Мы же не хотим тратить ресурсы на создание объектов по-умолчанию? А вдруг там в конструкторе подключение к БД, или чтение файла с диска. Ресайз вашего вектора может занять кучу времени.
Получить кусок памяти под 10 объектов типа T можно вызовом ::operator new(sizeof(T) * 10);
Заполнить сырую память существующими объектами поможет std::uninitialized_copy

2) Заказывайте память с запасом. Увеличиваете размер в 2-3 раза. Такой ход позволит вам выполнять перезаказ памяти и копирование элементов гораздо реже.

3) Используйте placement new вместо operator=. Если вы последуете первому совету, то этот пункт можете считать не советом, а правилом, так как нельзя вызывать метод operator=() у неинициализированного участка памяти. Да и не обязан пользователь вашего вектора определять operator=().
Таким образом такой код:

template<class T>
class Vector{
    T *items;
    //...
    void push(const T &value){
        //...
        items[size] = value;
        ++size;
    }
};

должен будет стать таким:

template<class T>
class Vector{
    T *items;
    //...
    void push(const T &value){
        //...
        new (items + size)(value);
        ++size;
    }
};

4) Что касается функции pop, не отдавайте уже занятую память. Она вполне может вам еще пригодиться. Для того, чтобы освободить лишнюю память лучше сделайте специальный метод. В std::vector он называется shrink_to_fit

1
  • Возможно, стоит добавить, что реализации shrink_to_fit разрешено вообще ничего не делать. 24 сен 2016 в 20:54
3

Обычно делают экспоненциальный рост внутреннего массива - это обеспечивает константное амортизированное время вставки элемента.

Выглядит это так. Есть внутренний массив, который не обязательно заполнен полностью. При добавлении элемента, если массив заполнен до конца - размер массива умножается на некоторое число. Обычно 2 или 1,5.

PS в вашей текущей реализации есть ошибка - вы сохраняете v.ptr, который должен быть уничтожен в деструкторе v.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.