С Вектор++ Клон


Я учусь C++, поэтому я решил сделать проще клон std::vector.

Проблемы:

  • Я видел людей, определение методов вне класса, и только прототипирование их внутри класса. Должна ли я тоже делать это?
  • Я новичок в низкоуровневых языках, которые требуют управления памятью, так что может быть утечка.
  • Есть ли какие способы оптимизации я могу сделать?
  • Мой общий стиль хорошо?

Мой код:

#include <iostream>
#include <algorithm>

template <class element>
class Vector {
  private:
  int len, cap;
  element* arr;

  void allocate_to_len() {
    int new_cap = min(cap, 1); // size-0 vectors wont loop infinitely
    while (len > new_cap) {
      new_cap *= 2;
    }
    resize(new_cap);
  }

  public:
  Vector() : Vector(10) {}

  Vector(int size) {
    len = 0;
    cap = size;
    arr = new element[size];
  }

  Vector(const Vector<element>& v) {
    len = v.length();
    cap = v.capac();
    arr = new element[cap];
    for (int i = 0; i < len; i++) {
      arr[i] = v.get_value(i);
    }
  }

  ~Vector() {
    delete[] arr;
  }

  element& operator[](int index) {
    if (index < 0 || index >= len) {
      throw "Index out of range";
    }
    return arr[index];
  }

  int length() const {
    return len;
  }

  int capac() const {
    return cap;
  }

  element get_value(int index) const {
    if (index < 0 || index >= len) {
      throw "Index out of range";
    }
    return arr[index];
  }

  void resize(int size) {
    cap = size;
    element* newarr = new element[size];
    len = std::min(len, cap);
    for (int i=0; i < len; i++) {
      newarr[i] = arr[i];
    }
    arr = newarr;
  }

  void append(element item) {
    len += 1;
    allocate_to_len();
    arr[len - 1] = item;
  }

  void extend(Vector<element> d) {
    int length = d.length();
    int old_len = len;
    len += length;
    allocate_to_len();
    for (int i=0; i < length; i++) {
      arr[i + old_len] = d[i];
    }
  }
};

int main() {
  // Tests:

  Vector<int> d;

  d.append(1);
  d.append(2);
  d.append(3);

  for (int i=0; i<d.length(); i++) {
    std::cout << d[i] << "\n";
  }
  std::cout << "\n";

  Vector<int> d2;

  d2.append(4);
  d2.append(5);
  d2.append(6);

  d.extend(d2);

  for (int i = 0; i < d.length(); i++) {
    std::cout << d[i] << "\n";
  }
  std::cout << "\n";

  d.resize(4);

  for (int i = 0; i < d.length(); i++) {
    std::cout << d[i] << "\n";
  }
}


Комментарии
5 ответов

В первую очередь, позволяет ответить на вопросы:


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

  2. Да, есть как минимум одна утечка памяти в resize(). Это видно по тому, что вы выделяем память, но не освобождает старой памяти. После того как метод возвращает внутренний указатель указывает на недавно выделенный массив, а старый остался заброшен и недоступен в глубине кучи. Чтобы исправить это, просто delete[] старый массив, прежде чем назначить arr = newarr.

  3. Наверное, но я не хочу вдаваться в такие вот, как


    • вы, кажется, не обнаружил никаких ТТХ код, и пока вы не тест вы не заботитесь о производительности

    • это подразумевает, что вы на самом деле не заботиться слишком много о производительности (если вы это сделали, вы бы измерили его) и

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


  4. Зависит от того, что вы подразумеваете под "общий стиль". Если вы имеете в виду правильные отступы, имена переменных и т. д. Я бы сказал, что да. Если вы имеете в виду использование STL и стандартные алгоритмы, я бы сказал, что есть еще над чем поработать.

Более пристально взглянуть

Вы не спрашивали за такой комментарий, так что если вы не заинтересованы, не стесняйтесь просто игнорируют эту часть ответа.

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


  1. А вы говорите, что ваш контейнер является простым клоном std::vectorего поведение серьезно отличается от стандартного контейнера, когда дело доходит до распределения и управления элементами. Вопрос в том, что ваш контейнер не может зарезервировать память без (по умолчанию) построения элементов. Однако, если вы посмотрите на std::vectorвы увидите, что он предлагает reserve интерфейс, который позволяет выделить память заранее, без построения каких-либо элементов. Такое поведение немного сложнее реализовать в код, хотя, так что вы можете придерживаться вашей версии, если вы еще в процессе получения хорошей владение C++, особенно если вы не чувствуете себя в безопасности, работающие с низким уровнем памяти процедуры.

  2. Хотя я склонен перебирать на этот момент снова и снова, int-это не правильный тип для индекса и итерационных переменных. Во-первых, это знаковый тип, что позволяет принимать отрицательные значения (то, что ваши методы разыменования бандажа против). Во-вторых, на современную архитектуру x86_64 системы (которая, как оказалось, что большинство пользователей настольных управлением), int скорее всего, только 32-битный тип данных, который означает, что вы ограничиваете себя около 4 гигабайт памяти для вектора, и нарваться на опасность переполнения с высокими показателями. Вместо этого, c++ предлагает тип std::size_t, который поддается очень хорошо для размера и индексов переменных, как следует из названия. Он не подписан, и, на обычной 64-битной платформы, обычно размер в 64 бита.

  3. Это плохая практика для принудительного исключения пользователей. Одна из причин этого заключается в том, что исключения очень медленно, когда они происходят. Другая причина заключается в том, что исключения не легко доступны на всех системах, особенно не во встроенном секторе развития. Мое предложение для вас, чтобы следовать std::vector шаблон дизайна: сделать operator[] бесконтрольно и имеют неопределенное поведение вне границ допуска, и предоставить at() метод, который делает проверки границ и бросает на Ауте. Это может также привести к увеличению производительности, так как проверки индекса не может быть избежать, если индекс считается в пределах.

  4. Как я уже упоминал в ответе на вопрос Четыре, есть потенциальная возможность использовать стандартные алгоритмы, в частности std::copy и std::move в местах, где выполняется копирование/перемещение данных из одного массива в другой. В общем, если у вас есть простой цикл for более широкий спектр элементов, которые не слишком сложны в своем теле, его можно заменить на петли с функцией вызова что-то из algorithm или numeric.

  5. Избегайте магических чисел. Например, в Vector() : Vector(10) {}, что означает 10? Почему 10? Каждый раз, когда вы окажетесь писать магическое число, рефакторинг его на константу и присвойте ей имя. В этом случае vector_default_size или что-то вроде бы уместно.

  6. Хотя это может быть частично, потому что это вопрос анализа кода, интерфейс вашего класса предлагает немного скудный. Что я нахожу особенно не хватает поддержки итераторов, т. е. begin() и end(). В случае вашего вектора, тех бы не было трудно реализовать, так как каждый исходный указатель автоматически удовлетворяет требованиям RandomAccessIterator.

  7. Говоря о сырых указателей, путь вашего класса реализуется в настоящее время он поддается очень хорошо для использования std::unique_ptr. Это будет иметь дополнительное преимущество, что вам не нужно беспокоиться о перемещении конструктор и деструктор больше, потому что они будут автоматически по уникальной указатель. В общем, вы должны попробовать, чтобы избежать как можно больше сырых указателей, так как они имеют семантику владения и склонны к мбе по назначению.


Части этого ответа были написаны раньше, чем Мартин-Йорк выложил свой ответ. Таким образом, там могут быть некоторые точки, которые пересекаются. Если вы найдете любой из этих пунктов заманчиво, пожалуйста, дайте кредит, чтобы Мартин-Йорк, так как он был быстрее меня.

14
ответ дан 12 февраля 2018 в 11:02 Источник Поделиться

Вопросы

Ваш вектор предполагает, что тип хранящихся имеет конструктор по умолчанию.

arr = new element[size];

Кроме того, это очень неэффективно для дорогих, чтобы создать классы, где вы не используете все size члены. Вы хотите создать свой класс так, что объекты в векторе только построены, когда элемент, добавленный первым.

Ошибка

Не выполнить правило трех.

По умолчанию компилятор создает три метода для вас. Копия Задания Конструктор/Копировать/Деструктор. Вы не выполнили копирующий оператор присваивания. Это означает, что вы будете иметь ошибку (из-за мелкой проблемы копию), если есть назначение.

Вопрос Дизайна

Возвращение значений по ссылке:

element get_value(int index) const;

Здесь вы возвращает копию элемента. Это может быть очень дорого. Поэтому было бы неплохо, если вы вернетесь по ссылке (в данном случае константной). Таким образом, вы можете читать данные без копирования данных.

Вопрос Дизайна

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

element& operator[](int index) {
if (index < 0 || index >= len) {
throw "Index out of range";
}
return arr[index];
}

Это конструкция используется std::vector.

T& std::vector::operator[](index);   // Does not check index
T& std::vector::at(index); // Does check that index is valid

Поэтому в случае:

for(int loop = 0; loop < v.length(); ++loop) {
std::cout << v[loop];
}

В этом очень стандартная ситуация, я знаю, что петли всегда в рамках. Поэтому делаю проверку на границы не требуется. Именно поэтому std::vector<> имеет два интерфейса для доступа к элементам.

Вопросы Констит

Много интерфейсов сдать объект const reference. Это позволяет сдать объект без копирования его и не давая доступ на запись к объекту (это называется корректность константный).

В результате большое входы интерфейсы тоже имеют константные версии.

T const& std::vector::operator[](index) const;   // Does not check index
T const& std::vector::at(index) const; // Does check that index is valid

Утечка Памяти

  void resize(int size) {
cap = size;
element* newarr = new element[size];
len = std::min(len, cap);
for (int i=0; i < len; i++) {
newarr[i] = arr[i];
}

Исправить Здесь

    // before you can overwrite `arr`
// You need to deallocate the array and all its members.
std::swap(arr, newarr); // So swap the values.
delete [] newarr; // Now you can delete the old array.
}

Примечания

Я написал серию статей о написании вектор.

Вектор - Управление Ресурсами
Вектор - копирования и замены
Вектор - Размер
Вектор - Простая Оптимизация
Вектор - другие вещи

30
ответ дан 12 февраля 2018 в 11:02 Источник Поделиться

Я не видел других ответов говорить достаточно о том, как управлять размерами вектор.

Вопрос Дизайна

Вы объявляете int len, cap; но по крайней мере вы используете int последовательно. Это, как правило, используя size_t. (см. Бен Штефана ответ пункт 2)

Ошибка реализации

allocate_to_len есть ошибка. В частности, если len > INT_MAX / 2вы переполнены cap что приводит к неопределенному поведению int и переливом для size_t. Стандартная реализация vector предложен метод max_size что возвращает наибольшее реализации определенных возможностей. Резервирования или увеличения вектора за того, что размер бросает length_error.

Аналогично, в append возможно переполнение len.

Именования

capac следует назвать capacity. get_value это at. length это size. append называется push_back в языке C++. Это приводит меня к моему последнему замечанию.

Придерживаться концепции контейнер

Если вы хотите, чтобы ваш вектор для повторного использования в других контекстах, следует соблюдать контейнера концепции. Это позволит другим библиотекам, например <algorithm> использовать ваш контейнер.

Часть этого можно было бы поменять void extend(Vector<element> d) (Отметим также, что вы должны принимать этот аргумент на ссылку) в template <class InputIterator> void insert (iterator position, InputIterator first, InputIterator last); а также осуществляет iterator для вашего контейнера.

5
ответ дан 13 февраля 2018 в 11:02 Источник Поделиться

Исключение Безопасности

Ваш контейнер не исключение безопасным.

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

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


  • в конструктор по умолчанию,

  • в конструктор копирования,

  • в копирующий оператор присваивания,

  • в конструктор перемещения,

  • в ход оператор присваивания,

  • в деструкторе...

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

Вы должны решить, как справиться с этим поведением:


  • Не составляя исключения-это не вариант, вы можете увильнуть от пометки ваши методы noexcept1 хотя пользователи могут не оценить,

  • По крайней мере, вы не должны течь (основным исключением гарантии); если вы используете new/delete обработки памяти, вы, скорее всего, не в этом,

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

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

1 Если исключение попыток "оставить" noexcept метод, программа завершается резко. Это лучше, чем развращает памяти, но все равно очень раздражает.


Имея это в виду, пожалуйста, рассмотреть следующие начала:

template <typename T>
class Vector {
public:
Vector() = default;

// WARNING:
// The COPY CONSTRUCTOR, COPY ASSIGNMENT OPERATOR and DESTRUCTOR
// are missing and should be defined. Correctly.

void push_back(T&& e);
void push_back(T const& e);

private:
using Raw = typename std::aligned_storage<sizeof(T), alignof(T)>::type;

void grow_by(std::ptrdiff_t n);

T* raw();

std::ptrdiff_t mCapacity = 0;
std::ptrdiff_t mLength = 0;
std::unique_ptr<Raw[]> mStorage;
};

template <typename T>
void Vector<T>::push_back(T&& e) {
this->grow_by(1);

new (this->raw() + mLength) T{std::move(e)};
++mLength;
}

template <typename T>
void Vector<T>::push_back(T const& e) {
this->grow_by(1);

new (this->raw() + mLength) T{e};
++mLength;
}

template <typename T>
void Vector<T>::grow_by(std::ptrdiff_t n) {
if (mLength + n <= mCapacity) { return; }

// Prepare new storage
auto newCapacity = std::max(mCapacity, 1);
do {
newCapacity *= 2;
} while (mLength + n > newCapacity);

Vector next;
next.mCapacity = newCapacity;
next.mStorage.reset(new Raw[newCapacity]);

// Transfer objects:
// 1. if T's move constructor is noexcept, use it!
// 2. otherwise, if T has a copy constructor, use it!
// 3. otherwise, use T's move constructor.
//
// Cases 1 and 2 offer the Strong Exception Guarantee; case 3
// unfortunately offers only the Basic Exception Guarantee.
for (auto& t : *this) {
next.push_back(std::move_if_noexcept(t));
}

// "Commit" the change.
std::swap(*this, next);
}

template <typename T>
T* Vector<T>::raw() { return reinterpret_cast<T*>(mStorage.get()); }

Есть два std особенности Примечание здесь:


  1. Использование std::aligned_storage<>::type дает нам сырье для хранения подходящего размера и выравнивания: это устраняет необходимость для умолчанию конструкторы T!

  2. Использование std::move_if_noexcept позволяет нам предложить наилучшее исключения с маленьким кодом.

Также, обратите внимание, как оба grow_by и push_back организованы таким образом, чтобы обеспечить сильную гарантию исключения (когда это возможно):


  1. Выполнять операции, которые могут бросить без изменения объекта,

  2. Совершить работу.

В случае push_backвы можете посмотреть длина увеличивается на единицу только в случае, если строительство объекта успешно, например.

В случае grow_byобратите внимание, как он использует ток Vector класс для обработки разрушение уже скопированы/перемещены элементы, если исключение выдается в петле.


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

Включив ряд элементов в середину вектора-это кошмар, когда конструктор перемещения/перемещения оператора присваивания может бросить.

5
ответ дан 13 февраля 2018 в 02:02 Источник Поделиться

Просто хотел обратить внимание на 2 вещи, которые я увидел, что, кажется, не были указаны.

Добавление изменяет вектор каждый раз

Я вижу, что вы разграничиваете способность и длина. Общая идея такова, что вектор всегда будет иметь некоторое свободное пространство для роста в без того, чтобы перераспределить память, элементы копирования, и де-выделить память каждый раз. В append метод, который вы звоните allocate_to_len() независимо от того, или не требуется больше памяти. Вам нужно только позвонить allocate_to_len() когда после увеличения лен len >= cap

т. е.

void append(...) {
len += 1;
if (len >= cap)
allocate_to_len();
...
}

Цикл вычисления емкости ненужно

При вычислении новых мощностей, вы удвоить нынешние мощности пока больше, чем текущая длина. Если вы будете следовать моим предложением выше, то мощность гарантированно быть не менее длины, если не больше. Удвоив его достаточно один раз, так что цикл может быть удален. Кроме того, вы также можете просто вычислить новом качестве двойной длины. Я считаю, что это стандартное распределение поведения std::vector

cap = len*2;

Достаточно, если не гарантируя, что вы не превысили максимальную длину, как отметил другой ответ.

В целом отличная работа! Я просто придирки. Переписывание стандартных контейнеров и алгоритмов является невероятно полезным и то, что я сделал, когда я впервые обучения.

5
ответ дан 13 февраля 2018 в 03:02 Источник Поделиться