std :: list повторная реализация

Question 1

Я решил переписать список стандартных библиотек в уменьшенной версии. Это похоже на другой мой вопрос, где меня больше всего беспокоит управление памятью. Я выделяю новый массив каждый раз, когда пользователь хочет изменить список. Я хочу знать, есть ли утечки памяти, которые мне нужно устранить. Я либерально использовал delete[], но мне нужно знать, что я покрыл все свои базы.

Как всегда, мы всегда приветствуем и ценим передовой опыт и другие улучшения.

#include <iostream>
#include <initializer_list>

template<class T>
class list {

    private:

        size_t length = 0;
        T* elements = nullptr;

        /**
         * Determines if there will be an out of bound error. If so, handles
         * it nicely and displays the range of acceptable integers allowed.
         * 
         * @param position The index passed by the user.
         * 
         * @return (void).
        **/
        void checkRangeError(const int& position) const {
            if (position < 0 || position >= this->length) {
                std::cout << "error: (position) parameter needs to be in range [0, " << this->length << ")" << std::endl;
                exit(1);
            }
        }

    public:

        list() {}
        list(std::initializer_list<T> args) {
            for (auto arg : args) {
                this->append(arg);
            }
        }
        ~list() { delete[] this->elements; }

        // Capacity Functions //

        /**
         * Determines if the current list is empty.
         * 
         * @return (bool) True if empty, False otherwise.
        **/
        bool empty(void) const { return this->length != 0; }

        /**
         * Returns the current length of the list.
         * 
         * @return (size_t) Length of list.
        **/
        size_t size(void) const { return this->length; }

        // Element Access Functions //

        /**
         * Returns the element at the front of the list. Does not pop, but
         * simply returns the value.
         * 
         * @return (T) First item in the list.
        **/
        T front(void) const { return this->elements[0]; }

        /**
         * Returns the element at the end of the list. Does not pop, but
         * simply returns the value.
         * 
         * @return (T) Last item in the list.
        **/
        T back(void) const { return this->elements[this->length - 1]; }

        // Modifier Functions //

        /**
         * Adds an element to the end of the list. Grows the list size by one.
         * 
         * @param value Element to add to the list.
         * 
         * @return (void).
        **/
        void append(const T& value) {
            if (this->length == 0) {
                this->elements = new T[1];
                this->elements[this->length++] = value;
                return;
            }
            T* previous = new T[this->length];
            for (int i = 0; i < this->length; i++)
                previous[i] = this->elements[i];
            this->elements = new T[++this->length];
            for (int i = 0; i < this->length; i++)
                this->elements[i] = previous[i];
            this->elements[this->length - 1] = value;
            delete[] previous;
        }

        /**
         * Inserts an element at the given position. Shifts every element after down one.
         * 
         * @param position Index to place value.
         * @param value Element to add to list.
         * 
         * @return (void).
        **/
        void insert(const int& position, const T& value) {
            this->checkRangeError(position);
            T* previous = new T[this->length];
            if (position == 0) {
                for (int i = 0; i < this->length; i++)
                    previous[i] = this->elements[i];
                this->elements = new T[++this->length];
                this->elements[0] = value;
                for (int i = 1; i < this->length - 1; i++)
                    this->elements[i] = previous[i];
                delete[] previous;
                return;
            }
            for (int i = 0; i < this->length; i++)
                previous[i] = this->elements[i];
            this->elements = new T[++this->length];
            for (int i = 0; i < position; i++)
                this->elements[i] = previous[i];
            this->elements[position] = value;
            for (int i = position; i < this->length - 1; i++)
                this->elements[i + 1] = previous[i];
            delete[] previous;
        }

        /**
         * Replaces the value at the given position with the new value.
         * 
         * @param position Index to replace value.
         * @param value New element to place in list.
         * 
         * @return (void).
        **/
        void replace(const int& position, const T& value) {
            this->checkRangeError(position);
            this->elements[position] = value;
        }

        /**
         * Erases the value at the given position, shrinking the size of the list by one.
         * 
         * @param position Index to erase value.
         * 
         * @return (void).
        **/
        void erase(const int& position) {
            this->checkRangeError(position);
            T* previous = new T[this->length];
            for (int i = 0; i < this->length; i++)
                previous[i] = this->elements[i];
            this->elements = new T[--this->length];
            for (int i = 0; i < position; i++)
                this->elements[i] = previous[i];
            for (int i = position; i <= this->length - 1; i++)
                this->elements[i] = previous[i + 1];
            delete[] previous;
        }

        /**
         * Shrinks the size of the list, keeping only the elements that fit into the new size.
         * The new size must be less than the current length of the list, or the function will exit.
         * 
         * @param newSize New length of the list.
         * 
         * @return (void).
        **/
        void shrink(const int& newSize) {
            if (newSize >= this->length) {
                std::cout << "error: (newSize) must be less than the current length of the list!" << std::endl;
                exit(1);
            }
            size_t len = this->length - newSize;
            for (int i = 0; i < len; i++)
                this->erase(this->length - 1);
        }

        /**
         * Swaps two elements at their given indexes.
         * 
         * @param indexOne First index to swap.
         * @param indexTwo Second index to swap.
         * 
         * @return (void).
        **/
        void swap(const int& indexOne, const int& indexTwo) {
            T temp = this->elements[indexOne];
            this->elements[indexOne] = this->elements[indexTwo];
            this->elements[indexTwo] = temp;
        }

        /**
         * Performs an in-place bubble sort on the current list.
         * 
         * @return (void).
        **/
        void sort(void) {
            for (int i = 0; i < this->length; i++)
                for (int j = 0; j < this->length - i - 1; j++)
                    if (this->elements[j] > this->elements[j + 1])
                        this->swap(j, j + 1); // Swap using index, not value.
        }

        /**
         * Clears the list of all elements and resetting the length to zero.
         * 
         * @return (void).
        **/
        void clear(void) {
            this->elements = nullptr;
            this->length = 0;
        }

        /**
         * Prints the list to the console, all on one line.
         * 
         * @return (void).
        **/
        void print(void) const {
            for (int i = 0; i < this->length; i++)
                std::cout << this->elements[i] << " ";
            std::cout << std::endl;
        }

        /**
         * Overload operator[] for list.
        **/
        T& operator[](const int& position) const {
            this->checkRangeError(position);
            return this->elements[position];
        }   

        /**
         * Overload operator== for list.
        **/
        bool operator==(list& rhs) const {
            if (this->size() != rhs.size()) return false;
            for (int i = 0; i < this->length; i++)
                if (this->elements[i] != rhs[i]) return false;
            return true;
        }   

};

И вот как я компилирую:

run.sh

g++ program.cpp -std=c++2a -o program
./program
rm program

Question 2

Как уже упоминалось, это повторная реализация std::vector, нет std::list.

Конструктор по умолчанию может быть установлен как default.

Ты не подписываешься правило 0-3-5. Рассмотрим этот фрагмент кода:
```
int main()
{
 list<int> l1 = {1, 2, 3};
 list<int> l2 = l1;
}
```
В настоящее время ваша реализация вызывает неопределенное поведение, потому что оба l1 а также l2 указывают на ту же область памяти. Когда оба уничтожены, они оба пытаются удалить один и тот же указатель, вызывая двойное освобождение.

Ваш front а также back методы должны возвращать ссылку на объект. Кроме того, должно быть две версии, константная и неконстантная, возвращающие константную и неконстантную ссылку соответственно.

Вам не нужно использовать void для обозначения пустого списка параметров. В отличие от C, пустой список параметров означает отсутствие аргументов.

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

Если вы повторно реализуете контейнер / функцию STL, вы должны сохранить тот же интерфейс. Это означает append становится push_back.

То, как вы увеличиваете массив, очень неэффективно. По сути, вы выделяете новый массив и копируете элементы каждый раз, когда добавляете. Это означает, что ваш append имеет временную сложность O (N), где N — количество элементов в массиве.
Типичные реализации выделяют больше памяти, чем необходимо, и отслеживают, сколько памяти выделено и сколько памяти фактически используется. Если они оба равны, только тогда выделяется новая память и элементы копируются.
Сколько новой памяти выделить? Реализации обычно выделяли в 2 или 1,5 раза больше исходной емкости. Это дает вам амортизированное добавление O (1).
Есть и другие оптимизации, которые вы можете сделать в C ++. Вы можете выделить необработанную память и создать объект только при необходимости (используя размещение new). Это позволяет избежать создания объектов по умолчанию при выделении памяти (что может быть дорогостоящим). Вы также можете проверить, есть ли Tконструктор перемещения noexcept (с использованием std::is_nothrow_move_constructible), а затем переместите элементы вместо их копирования.

То, как вы перемещаете элементы, также очень неэффективно. Вот что вы делаете:
1. Выделить временную память (будет создана по умолчанию)
2. Скопируйте все элементы во временную память
3. Выделить новую память списка
4. Скопируйте все элементы из временной памяти в новый список памяти
5. Удалить временную память
тогда как более эффективным способом было бы
1. Выделить временную память (размер старой памяти * 2)
2. Скопируйте все элементы во временную память
3. Поменять местами временную память и перечислить указатели памяти
4. Удалить временную память

Ваш класс не безопасен для исключений. Любой из звонков new может вернуться std::bad_alloc.

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

Вместо предоставления print функция, более идиоматический способ печати объекта в C ++ — перегрузить operator<< метод.

Вместо предоставления sort функции, вы должны предоставить итераторы (которые просто T* в данном случае) в виде begin() а также end() функции, так что можно использовать std::sort.

Использовать std::size_t вместо int для представления индексов или размера. Кроме того, вам не нужно передавать тривиальные типы, такие как int используя константную ссылку; вместо этого передайте их по значению. Они достаточно малы, чтобы поместиться в регистры.

Question 3

В front, back, а методы подкачки не проверяют наличие пустого list.

Вы теряете много памяти. Большинство / все места, где у вас есть this->elements = new вы не освободили предыдущую память, хранящуюся в this->elements, что приведет к утечке. clear не освобождает память.

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

insert в позиции 0 не сдвигает существующие элементы. Вы теряете старый элемент 0 и получаете последний элемент, созданный по умолчанию.

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

operator[] должны иметь константные и неконстантные версии. Ваша текущая версия — это константная функция, которая возвращает неконстантную ссылку на ваши внутренние данные.

Ваш list может хранить только конструктивные объекты по умолчанию.

Question 4

Как уже было сказано, это что-то вроде std::vector, но ничего подобного std::list.

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

моя главная забота — управление памятью

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

void checkRangeError(const int& position) const {

Вы можете просто передавать типы значений по значению, если у вас нет убедительной причины не делать этого. Передача int по ссылке const ничего не оптимизирует, она просто делает код более шумным. И наоборот, в

T front(void) const

вы (как автор библиотеки) заранее не знаете, какой тип T есть, поэтому вы не можете сказать, дорого ли копировать. Этот должен вернуть const ref (и действительно должны быть неконстантные перегрузки этого и других аксессоров).

По аналогии,

T& operator[](const int& position) const

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

T* previous = new T[this->length];

почему новый массив называется предыдущий? Наверняка это должно быть следующий версия массива?

Обратите внимание, что вы собираетесь по умолчанию построить все N элементов и тогда скопировать снова назначить все N элементов. Это расточительно (вы инициализируете все дважды) и накладывает ненужные ограничения на T (он должен быть конструктивным по умолчанию).

this->elements = new T[++this->length];

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

Ты можешь просто написать

T* new_elements = allocate_and_move(elements, length);
delete [] elements;
elements = new_elements;

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

Я либерально использовал delete[], но мне нужно знать, что я покрыл все свои базы.

Не будьте либеральны в использовании удаления — двойное освобождение памяти так же плохо, как и ее утечка. Старайтесь в первую очередь избегать ручного управления памятью, особенно если вам трудно понять, в каком состоянии находятся объекты. Итак, мы могли бы улучшить три приведенные выше строки, чтобы:

std::unique_ptr<T[]> new_elements = allocate_and_move(elements, length);
elements.swap(new_elements);

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

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

std::list имеет вставку O (1), потому что время вставки одного элемента в связанный список не зависит от размера списка.

std::vector имеет амортизированный O (1) insert, потому что, хотя рост массива является дорогостоящим (линейным, хотя и с более низким коэффициентом, чем ваш код), он позволяет избежать увеличения массива при каждой вставке.

В вашем контейнере есть вставка O (N) (с действительно высоким коэффициентом из-за инициализации по умолчанию каждого элемента перед его двойным копированием).

Question 5

T back(void) const

Не использовать (void) для пустых списков параметров. Страуструп называет это «мерзостью». C требовалось, чтобы при добавлении (необязательных) подписей; C ++ никогда не делал.

 if (this->length == 0) {
 this->elements = new T[1];
 this->elements[this->length++] = value;

Не использовать this-> для каждого членского доступа! Просто используйте имя участника.

length == 0 лучше выразить как empty().

Чем эта реализация похожа на std::list? Это больше похоже на vector.

        /**
         * Performs an in-place bubble sort on the current list.
         * 
         * @return (void).
        **/
        void sort(void) {

Почему это необходимо как индивидуальная функция-член? std::sort должен работать над вашим классом коллекции. В самом худшем случае вы сможете позвонить std::sort во внутреннем массиве как реализация этого члена.

       /**
         * Clears the list of all elements and resetting the length to zero.
         * 
         * @return (void).
        **/
        void clear(void) {
            this->elements = nullptr;
            this->length = 0;
        }

Вы, кажется, забыли delete память!

void shrink(const int& newSize) {

Почему вы проходите int по ссылке?

Ваш shrink функция крайне неэффективна. Он перераспределяет (копирует) весь массив для каждого удаленного элемента, а не только один раз.
Конструктор, который принимает initialization_list то же самое: зачем перераспределять / копировать снова для каждого элемента, а не делать это один раз?

Когда вы перераспределяете и копируете свой массив, вам требуется, чтобы T имеет конструктор по умолчанию, и вы используете присваивание, чтобы установить его значение. В std:: коллекции не имеют такого требования. В std::vector инициализирует элементы непосредственно из устанавливаемого элемента, используя конструктор копирования, конструктор перемещения или (при использовании emplace_back) вызывая некоторый указанный конструктор непосредственно на месте.

for (int i = 0; i < this->length; i++)
     this->elements[i] = previous[i];

Просто используйте std::copy алгоритм.
Вы должны знать, что доступно в библиотеке.

            T* previous = new T[this->length];
            for (int i = 0; i < this->length; i++)
                previous[i] = this->elements[i];
            this->elements = new T[++this->length];
            for (int i = 0; i < this->length; i++)
                this->elements[i] = previous[i];

Боже, вы копируете текущий массив, а затем копируете его снова! И вы совсем забываете удалить elements перед перезаписью этого указателя.

«Обычный» способ сделать это — скопировать в более длинный массив, а затем просто присвоить этот указатель обратно elements член; вам не нужно копировать его снова. Я думаю, ты этого не понимаешь elements это указатель не какой-то встроенный сборник. Ваш лайк this->element= new... не перераспределяет существующий массив, а выделяет другой массив и назначает указатель на первый элемент для elements, теряя значение старого указателя (бросая его на пол, не удаляя).

Похожие записи:

Добавить комментарий Отменить ответ