Я реализовал простую векторную структуру. Буду признателен за любую критику в отношении кода. Я также опубликовал код на гитхабе. Вот ссылка на исходный код + модульный тест для большинства функций:
https://github.com/Nethius/mystd
const double_t expansion_ratio = 1.5;
namespace mystd {
template<class T>
class vector {
size_t _size;
size_t _capacity;
char *_data;
typedef T *iterator;
typedef const T *const_iterator;
typedef T &reference;
typedef const T &const_reference;
void reallocate(size_t capacity);
void move_forward(iterator dest, iterator from, size_t count);
void move_backward(iterator dest, iterator from, size_t count);
public:
vector();
explicit vector(size_t size);
vector(size_t size, const T &initial);
vector(const vector<T> &vector);
vector(vector<T> &&vector) noexcept;
vector(std::initializer_list<T> list);
template<class input_iterator, typename = typename std::enable_if_t<std::_Is_iterator<input_iterator>::value>>
vector(input_iterator first, input_iterator last);
~vector();
reference operator[](size_t pos);
const_reference operator[](size_t pos) const;
reference at(size_t pos);
const_reference at(size_t pos) const;
vector<T> &operator=(const vector<T> &vector);
vector<T> &operator=(vector <T> &&vector) noexcept;
void assign(size_t count, const_reference value);
template<class input_iterator, typename = typename std::enable_if_t<std::_Is_iterator<input_iterator>::value>>
void assign(input_iterator first, input_iterator last);
iterator insert(const_iterator pos, const_reference value);
iterator insert(const_iterator pos, T &&value);
iterator insert(const_iterator pos, size_t count, const_reference value);
template<class input_iterator, typename = typename std::enable_if_t<std::_Is_iterator<input_iterator>::value>>
iterator insert(const_iterator pos, input_iterator first, input_iterator last);
iterator insert(const_iterator pos, std::initializer_list<T> list);
template<typename ... Args>
iterator emplace(const_iterator pos, Args &&... args);
iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);
size_t size() const;
size_t max_size() const;
size_t capacity() const;
bool empty() const;
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
iterator rbegin();
const_iterator rbegin() const;
const_iterator rcbegin() const;
iterator end();
const_iterator end() const;
const_iterator cend() const;
iterator rend();
const_iterator rend() const;
const_iterator rcend() const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
iterator data();
const_iterator data() const;
void push_back(const_reference value);
void push_back(T &&value);
void pop_back();
template<typename ... Args>
void emplace_back(Args &&... args);
void reserve(size_t size);
void resize(size_t count);
void resize(size_t count, const_reference value);
void shrink_to_fit();
void clear();
template<class T>
friend void swap(vector<T> &left, vector<T> &right);
template<class T>
friend bool operator==(const vector <T> &left, const vector <T> &right);
template<class T>
friend bool operator!=(const vector <T> &left, const vector <T> &right);
template<class T>
friend bool operator<(const vector <T> &left, const vector <T> &right);
template<class T>
friend bool operator<=(const vector <T> &left, const vector <T> &right);
template<class T>
friend bool operator>(const vector <T> &left, const vector <T> &right);
template<class T>
friend bool operator>=(const vector <T> &left, const vector <T> &right);
};
template<class T>
vector<T>::vector() : _size(0), _capacity(0), _data(nullptr) {
}
template<class T>
vector<T>::vector(size_t size) : _size(size), _capacity(_size), _data(new char[sizeof(T) * size]()) {
}
template<class T>
vector<T>::vector(size_t size, const T &initial) : vector(size) {
for (size_t i = 0; i < _size; i++)
new(_data + sizeof(T) * i) T(initial);
}
template<class T>
vector<T>::vector(const vector <T> &vector) : vector(vector._size) {
for (size_t i = 0; i < _size; i++)
new(_data + sizeof(T) * i) T(vector[i]);
}
template<class T>
vector<T>::vector(vector<T> &&vector) noexcept : vector(vector._size) {
swap(*this, vector);
}
template<class T>
vector<T>::vector(std::initializer_list<T> list) : vector(list.size()) {
for (size_t i = 0; i < _size; i++)
new(_data + sizeof(T) * i) T(*(list.begin() + i));
}
template<class T>
template<class input_iterator, typename>
vector<T>::vector(input_iterator first, input_iterator last) : vector(std::distance(first, last)) {
auto it = first;
for (size_t i = 0; i < _size; i++) {
new(_data + sizeof(T) * i) T(*(it));
it = std::next(it);
}
}
template<class T>
vector<T>::~vector() {
delete[] _data;
}
template<class T>
T &vector<T>::operator[](size_t pos) {
return *(reinterpret_cast<iterator>(_data + sizeof(T) * pos));
}
template<class T>
const T &vector<T>::operator[](size_t pos) const {
return *(reinterpret_cast<iterator>(_data + sizeof(T) * pos));
}
template<class T>
vector<T> &vector<T>::operator=(const vector <T> &vector) {
if (*this != vector) {
swap(*this, mystd::vector<T>(vector));
}
return *this;
}
template<class T>
vector<T> &vector<T>::operator=(vector<T> &&vector) noexcept {
if (*this != vector) {
swap(*this, vector);
}
return *this;
}
template<class T>
typename vector<T>::iterator vector<T>::begin() {
return reinterpret_cast<iterator>(_data);
}
template<class T>
typename vector<T>::const_iterator vector<T>::begin() const {
return reinterpret_cast<iterator>(_data);
}
template<class T>
typename vector<T>::const_iterator vector<T>::cbegin() const {
return begin();
}
template<class T>
typename vector<T>::iterator vector<T>::end() {
return reinterpret_cast<iterator>(_data + sizeof(T) * _size);
}
template<class T>
typename vector<T>::const_iterator vector<T>::end() const {
return reinterpret_cast<iterator>(_data + sizeof(T) * _size);
}
template<class T>
typename vector<T>::const_iterator vector<T>::cend() const {
return end();
}
template<class T>
size_t vector<T>::size() const {
return _size;
}
template<class T>
size_t vector<T>::capacity() const {
return _capacity;
}
template<class T>
bool vector<T>::empty() const {
return _size == 0;
}
template<class T>
typename vector<T>::reference vector<T>::front() {
return *begin();
}
template<class T>
typename vector<T>::const_reference vector<T>::front() const {
return *cbegin();
}
template<class T>
typename vector<T>::reference vector<T>::back() {
return *(end() - 1);
}
template<class T>
typename vector<T>::const_reference vector<T>::back() const {
return *(cend() - 1);
}
template<class T>
void swap(vector<T> &left, vector<T> &right) {
using std::swap; //enable ADL? https://stackoverflow.com/questions/5695548/public-friend-swap-member-function
swap(left._size, right._size);
swap(left._capacity, right._capacity);
swap(left._data, right._data);
}
template<class T>
void vector<T>::push_back(const_reference value) {
if (_size >= _capacity) {
reallocate(_size * expansion_ratio);
}
new(end()) T(value);
_size++;
}
template<class T>
void vector<T>::push_back(T &&value) {
if (_size >= _capacity) {
reallocate(_size * expansion_ratio);
}
*end() = std::move(value);
_size++;
}
template<class T>
void vector<T>::reallocate(size_t capacity) {
_capacity = capacity;
char *new_data = new char[sizeof(T) * _capacity]();
iterator new_begin = reinterpret_cast<iterator>(new_data);
for (auto it = begin(); it != end(); it++)
*new_begin++ = std::move(*it);
delete[] _data;
_data = new_data;
}
template<class T>
void vector<T>::move_forward(vector::iterator dest, vector::iterator from, size_t count) {
if (dest == from)
return;
iterator _dest = dest;
iterator _from = from;
for (size_t i = 0; i < count; i++)
*_dest++ = std::move(*_from++);
}
template<class T>
void vector<T>::move_backward(vector::iterator dest, vector::iterator from, size_t count) {
if (dest == from)
return;
iterator _dest = dest + count - 1;
iterator _from = from + count - 1;
for (size_t i = count; i > 0; i--)
*_dest-- = std::move(*_from--);
}
template<class T>
void vector<T>::assign(size_t count, const_reference value) {
swap(*this, vector<T>(count, value));
}
template<class T>
template<class input_iterator, typename>
void vector<T>::assign(input_iterator first, input_iterator last) {
swap(*this, vector<T>(first, last));
}
template<class T>
template<typename... Args>
typename vector<T>::iterator vector<T>::emplace(vector::const_iterator pos, Args &&... args) {
size_t index = pos - reinterpret_cast<iterator>(_data);
if (_size >= _capacity) {
reallocate(_size * expansion_ratio);
}
iterator it = reinterpret_cast<iterator>(_data + sizeof(T) * index);
move_backward(it + 1, it, _size - index);
*it = T(std::forward<Args>(args) ...);
_size++;
return it;
}
template<class T>
typename vector<T>::iterator vector<T>::insert(vector::const_iterator pos, const_reference value) {
return emplace(pos, value);
}
template<class T>
typename vector<T>::iterator vector<T>::insert(vector::const_iterator pos, T &&value) {
return emplace(pos, std::move(value));
}
template<class T>
typename vector<T>::iterator vector<T>::insert(vector::const_iterator pos, size_t count, const_reference value) {
if (!count)
return const_cast<iterator>(pos);
size_t index = pos - reinterpret_cast<iterator>(_data);
if (_size + count >= _capacity) {
reallocate((_size + count) * expansion_ratio);
}
iterator it = reinterpret_cast<iterator>(_data + sizeof(T) * index);
move_backward(it + count, it, _size - index);
for (size_t i = 0; i < count; i++)
*(it + i) = value;
_size += count;
return it;
}
template<class T>
template<class input_iterator, typename>
typename vector<T>::iterator
vector<T>::insert(vector::const_iterator pos, input_iterator first, input_iterator last) {
size_t n = std::distance(first, last);
if (!n)
return const_cast<iterator>(pos);
size_t index = pos - reinterpret_cast<iterator>(_data);
if (_size + n >= _capacity) {
reallocate((_size + n) * expansion_ratio);
}
iterator dest = reinterpret_cast<iterator>(_data + sizeof(T) * index);
move_backward(dest + n, dest, _size - index);
auto from = first;
for (size_t i = 0; i < n; i++) {
*(dest + i) = *(from);
from = std::next(from);
}
_size += n;
return dest;
}
template<class T>
typename vector<T>::iterator vector<T>::insert(vector::const_iterator pos, std::initializer_list<T> list) {
return insert(pos, list.begin(), list.end());
}
template<class T>
void vector<T>::pop_back() {
erase(end() - 1);
}
template<class T>
typename vector<T>::iterator vector<T>::erase(vector::const_iterator pos) {
size_t index = pos - reinterpret_cast<iterator>(_data);
iterator it = reinterpret_cast<iterator>(_data + sizeof(T) * index);
it->~T();
if (pos != end() - 1)
move_forward(it, it + 1, _size - index);
_size--;
return it;
}
template<class T>
typename vector<T>::iterator vector<T>::erase(vector::const_iterator first, vector::const_iterator last) {
size_t n = 0;
for (auto curr = first; curr <= last; ++curr)
++n;
if (!n)
return const_cast<iterator>(last);
size_t index = first - reinterpret_cast<iterator>(_data);
iterator it = reinterpret_cast<iterator>(_data + sizeof(T) * index);
for (size_t i = 0; i < n; i++)
(it + i)->~T();
move_forward(it, it + n, _size - (index + n));
_size -= n;
return it;
}
template<class T>
typename vector<T>::iterator vector<T>::data() {
return reinterpret_cast<iterator>(_data);
}
template<class T>
typename vector<T>::const_iterator vector<T>::data() const {
return data();
}
template<class T>
template<typename... Args>
void vector<T>::emplace_back(Args &&... args) {
emplace(end(), args ...);
}
template<class T>
void vector<T>::reserve(size_t size) {
if (size > _capacity)
reallocate(size);
}
template<class T>
void vector<T>::shrink_to_fit() {
reallocate(_size);
}
template<class T>
void vector<T>::clear() {
for (auto it = begin(); it != end(); it++)
(it)->~T();
_size = 0;
}
template<class T>
void vector<T>::resize(size_t count) {
if (count > _capacity)
reallocate(count * expansion_ratio);
_size = count;
}
template<class T>
void vector<T>::resize(size_t count, const_reference value) {
iterator it = reinterpret_cast<iterator>(_data);
if (count > _size) {
size_t lastElementIndex = _size;
resize(count);
it = begin();
for (size_t i = lastElementIndex; i < count; i++)
*(it + i) = value;
} else {
for (size_t i = count; i < _size; i++)
(it + i)->~T();
}
_size = count;
}
template<class T>
bool operator==(const vector<T> &left, const vector<T> &right) {
if (left._size != right._size)
return false;
for (size_t i = 0; i < left._size; i++) {
if (*(reinterpret_cast<T *>(left._data + sizeof(T) * i)) !=
*(reinterpret_cast<T *>(right._data + sizeof(T) * i)))
return false;
}
return true;
}
template<class T>
bool operator!=(const vector<T> &left, const vector<T> &right) {
return !(left == right);
}
template<class T>
bool operator<(const vector<T> &left, const vector<T> &right) {
size_t size = left.size() < right.size() ? left.size() : right.size();
for (size_t i = 0; i < size; i++) {
if (*(reinterpret_cast<T *>(left._data + sizeof(T) * i)) <
*(reinterpret_cast<T *>(right._data + sizeof(T) * i)))
return true;
}
return false;
}
template<class T>
bool operator<=(const vector<T> &left, const vector<T> &right) {
return !(left > right);
}
template<class T>
bool operator>(const vector<T> &left, const vector<T> &right) {
size_t size = left.size() < right.size() ? left.size() : right.size();
for (size_t i = 0; i < size; i++) {
if (*(reinterpret_cast<T *>(left._data + sizeof(T) * i)) >
*(reinterpret_cast<T *>(right._data + sizeof(T) * i)))
return true;
}
return false;
}
template<class T>
bool operator>=(const vector<T> &left, const vector<T> &right) {
return !(left < right);
}
}
```
2 ответа
Привет и добро пожаловать в CodeReview!
Здесь есть что разгадать, в основном это касается читабельности и надежного кода.
typedefэто реликт из C, который был полностью вытесненusingобъявления, поэтому ваши псевдонимы должны читать:using iterator = T*; using const_iterator = const T*; using reference = T&; using const_reference = const T&;Обратите внимание, что в этом случае это даже сильно сбивало с толку, так как
*и&где находится прямо по имени псевдонима.Вы выбрали обозначение на основе размера, а не на основе указателя. Это возможно, но требует довольно большого количества вычислений, которых можно избежать, используя обычные
first, last, endуказатели.Ваши элементы данных могут и должны быть инициализированы членами, чтобы не было возможности забыть их инициализировать.
size_t _size{0}; size_t _capacity{0}; char *_data{nullptr};Ваш выбор
char*поскольку базовый буфер неверен и не нужен. Первое наблюдение состоит в том, что толькоunsigned charиbyteразрешено представлять память, поэтому использованиеcharнеправильно. Также выравнивание может быть огромной проблемой, которую трудно устранить. Почему бы не пойти с простымT*. Таким образом, вы также можете избавиться от всех надоедливыхreinterpret_castЯ не вижу пользы в том, чтобы отделять объявления функций-членов от их определения. Они все равно нужны в шапке, так зачем добавлять все эти биопластины?
Обратите внимание, что это также может вызвать проблемы с правильностью, особенно в отношении шаблонных функций друзей. (Бен Сакс рассказывает о том, как завести друзей, которых я бы порекомендовал здесь)
Вы можете использовать конструктор по умолчанию, когда используете инициализатор члена.
Вектор You заметно отличается от реализации std тем, что он не инициализирует значения для членов. Это связано с выбором
charкак базовый тип буфера, что тривиально. Это почти наверняка приведет к появлению ошибок.Вы используете новое место размещения в
size, const referenceконструктор. В этом не было бы необходимости, если бы вы использовалиT*буфер. Также выравнивание наверняка вас укусит.Вы всегда должны использовать скобки вокруг
forиif. Буквально нет причин не использовать фигурные скобки даже для однолинейных тел. Он вводит целый ряд суперсложных для отладки ошибок для невероятной выгоды от одного сохраненного LoC.Ваш конструктор перемещения совершенно неправильный. Вам следует
moveсодержимое ввода в ваш вектор и не меняет местами элементы. Подумайте о разнице в продолжительности жизни, которую это имеет.Используйте доступный простой метод. Вы хотите увеличить итератор. Что лучше
++itили жеit = std::next(it)?Ваше копирование также полностью нарушено. Я действительно не знаю, почему вы называете свои аргументы так же, как класс, учитывая, что это всех запутает. Но это даже не должно компилироваться, так как вы не можете менять местами константную ссылку. В конце концов, это константа. Вам нужно скопировать элементы вокруг.
Все reinterpret_cast можно пойти
Вы используете постинкремент, который предполагает, что вы должны прочитать разницу между
++iиi++. Один из двух делает копию.В настоящее время вы не выполняете проверку границ для своих аксессуаров. Если вы открыты, вы рухнете и сгорит, когда кто-то использует его неправильно, это нормально. Неприятно, но технически правильно. Может быть, здесь и там поможет assert?
Вы открываете кодирование множества распространенных алгоритмов. Как правило, лучше просто использовать std :: copy, чем писать цикл вручную.
Каждый раз, когда вы используете своп, в большинстве случаев это неправильно
Вы полностью пренебрегаете безопасностью исключений. Если это сделано намеренно, вы должны прояснить это.
Пожалуйста, не сверяйте целые числа с 0 через
!Вам следует чаще повторно использовать внутренние методы. Почему везде есть reinterpret_cast, когда у вас есть
beginиendи могли бы просто перебрать итераторы, которые они вам дают?
Примечания:
Есть несколько мест, где вы неправильно начинаете или заканчиваете жизненный цикл объекта. После выделения необработанной памяти вы выделили capacity место для предметов, НО вы не начали время жизни каких-либо объектов в хранилище и, следовательно, ваш size равно нулю.
При добавлении объектов в хранилище они ДОЛЖЕН быть построенным (не закрепленным за). Это означает, что как size увеличивается, вы всегда должны использовать новое размещение (вызывая, таким образом, конструктор) и запускать время жизни объекта. Когда size уменьшается, вам нужно вручную вызвать деструктор и завершить время жизни объекта. Что-нибудь из [size..capacity) is not constructed and thus its lifetime has not started.
There are a couple of places where you assign to objects who’s lifetime has not started (assignment assumes the lifetime has started). There are also a couple of places where you don’t end the lifetime when you decrease the size (which would mean they could leak or accidentally be constructed onto).
See: Default constructor. Move constructor
You need to understand the strong exception guarantee. This basically says that a mutation works correctly or it fails (probably with an exception) BUT if it fails the state remains unchanged (and thus valid).
To make this work usually this means that mutations happen on temporary objects and state is swapped with the temporary using exception safe operations.
see: resize
The calls to resize if very subtly broken (this happened to me as well when I first tried to write vector).
reallocate(_size * expansion_ratio); // does not work if _size is 1.
// if your expansion_ratio is 1.5
// would work for 2 or greater.
Self Plug
I wrote a series of articles on the vector that is worth reading:
https://lokiastari.com/series/
Style
You use a C style when annotating your types for pointers and references by placing the ‘*’ or ‘&’ with the variable rather than with the type.
In C++ we usually place these annotations with the type so that all the type information is placed together. This is because in C++ type information is much more important.
vector& operator=(vector const& copy); // Notice the '&' with the type.
You store the data in char*. This means you have a lot of reinterpret_cast<>() to convert the pointer back to a T* I would simply change the data member in to a T* member and use the reinterpret_cast<>() once.
Code Review:
Prefer to use using over typedef
typedef T *iterator;
typedef const T *const_iterator;
typedef T &reference;
typedef const T &const_reference;
using iterator = T*;
using const_iterator = const T*;
using reference = T&;
using const_reference = const T&;
Your methods are simply a list of methods with an empty line between them.
vector();
explicit vector(size_t size);
vector(size_t size, const T &initial);
vector(const vector<T> &vector);
You should make this easier to read. One way to do this is to group together functions that have similar functionality. Constructors/Assignment Op/Insert/Query etc. Something.
I suppose you can check this.
template<class input_iterator, typename = typename std::enable_if_t<std::_Is_iterator<input_iterator>::value>>
vector(input_iterator first, input_iterator last);
I don’t see the point. If they don’t act like iterators it will fail to compile.
I see why you did this:
void push_back(const_reference value);
void push_back(T &&value);
But I think it is clearer to write like this:
void push_back(T const& value);
void push_back(T&& value);
You don’t need the template part here.
template<class T>
friend void swap(vector<T> &left, vector<T> &right);
or in the following friend declarations.
The reason to make these operations standalone functions is to allow the left value to auto convert into a vector when comparing something to a vector on the right hand side.
template<class T>
friend bool operator==(const vector <T> &left, const vector <T> &right);
Since this conversion can never happen (your only single parameter construcror is explicit). There is not need to make this a friend and it just simpler to make it a member of the class.
This is broken:
Because it is public.
template<class T>
vector<T>::vector(size_t size) : _size(size), _capacity(_size), _data(new char[sizeof(T) * size]()) {}
Вы выделили для себя место size элементы. НО вы не построили элементы типа T это просто сырая неинициализированная память. Вам нужно вызвать конструктор по умолчанию для каждого элемента в векторе.
После прочтения других конструкторов вы, кажется, используете это для выделения пространства, после чего другие конструкторы завершают инициализацию. Но поскольку это публично, оно не работает. Альтернатива — сделать его приватным.
Но пара других конструкторов в любом случае не должна использовать это.
Примечание: вы хотите, чтобы вместимость была равна размеру? Это означает, что следующий добавленный элемент вызовет перезапуск.
Примечание: если вы исправите вышеуказанный конструктор (для инициализации членов), вы не сможете использовать его здесь:
template<class T>
vector<T>::vector(size_t size, const T &initial) : vector(size) {
for (size_t i = 0; i < _size; i++)
new(_data + sizeof(T) * i) T(initial);
}
Это очень дорогой конструктор ходов.
template<class T>
vector<T>::vector(vector<T> &&vector) noexcept : vector(vector._size) {
swap(*this, vector);
}
Вы выделяете базовые данные, а затем меняете их содержимое. Установите текущий указатель на nullptr а потом поменять местами. Это не только дорого (выделение памяти), но и объект назначения находится в недопустимом состоянии. Она имеет size элементы, ни один из которых не инициализирован.
template<class T>
vector<T>::vector(vector<T>&& move) noexcept
: _size{0}
, _capacity{0}
, _data{nulptr}
{
swap(move);
}
Это не правильно.OK. Я вижу строительство временного сейчас.
template<class T>
vector<T> &vector<T>::operator=(const vector <T> &vector) {
if (*this != vector) {
swap(*this, mystd::vector<T>(vector));
}
return *this;
}
Вы пытаетесь изменить входной параметр (который одновременно является константой и ссылкой на что-то еще, что не следует изменять).
Похоже, это искажение идиомы копирования и обмена.
Тест на самостоятельное назначение контрпродуктивен. Это действительно замедлит работу (в среднем). Самостоятельное назначение чрезвычайно редко, поэтому тест на самостоятельное назначение фактически замедляет нормальный случай. Теперь вам действительно нужно правильно обрабатывать самостоятельное назначение, но, поскольку это происходит настолько редко, это действие может быть пезимизировано, чтобы вы могли оптимизировать нормальную ситуацию.
template<class T>
vector<T> &vector<T>::operator=(vector <T> const& input)
{
vector<T> copy(input); // Copy.
swap(copy); // Swap with the current with copy (see below)
return *this;
}
Опять же, проверка самоопределения — это пезимизация нормального случая при попытке оптимизировать очень редкий случай. Оптимизируйте для наиболее распространенной ситуации.
template<class T>
vector<T> &vector<T>::operator=(vector<T> &&vector) noexcept {
if (*this != vector) {
swap(*this, vector);
}
return *this;
}
Я бы упростил:
template<class T>
vector<T> &vector<T>::operator=(vector<T>&& move) noexcept
{
swap(move); // swap is safe for self assignment.
return *this;
}
Эти функции такие маленькие и простые.
template<class T>
size_t vector<T>::size() const {
return _size;
}
template<class T>
size_t vector<T>::capacity() const {
return _capacity;
}
template<class T>
bool vector<T>::empty() const {
return _size == 0;
}
Я бы поместил их в заголовочный файл. Если функция — это просто строка, я обычно просто помещаю ее в объявление класса:
class vector
{
// STUFF
size_t size() const {return _size;}
size_t capacity() const {return _capacity;}
bool empty() const {return _size == 0;}
};
Да. Включение ADL — это стандартный шаблон для свопа.
Да, вам нужен отдельный своп. Но почему нет также есть функция-член подкачки, чтобы упростить задачу?
template<class T>
void swap(vector<T> &left, vector<T> &right) {
using std::swap; //enable ADL? https://stackoverflow.com/questions/5695548/public-friend-swap-member-function
swap(left._size, right._size);
swap(left._capacity, right._capacity);
swap(left._data, right._data);
}
Я бы написал так:
class vector
{
// STUFF
void swap(vector& other) noexcept // swap needs to noexcept so
{ // it can be called from noexcept members
using std::swap; //enable ADL? YES.
swap(_size, other._size);
swap(_capacity, other._capacity);
swap(_data, other._data);
}
friend void swap(vector& lhs, vector& rhs) {lhs.swap(rhs);}
};
Незначительный разрыв: когда размер 1.
template<class T>
void vector<T>::push_back(const_reference value) {
if (_size >= _capacity) {
//
// size = 1;
// size * expansion_ratio => (1 * 1.5) => 1.5
// reallocate accepts (size_t an integer) thus the parameter
// will be truncated.
//
// So the value passed here is 1
reallocate(_size * expansion_ratio);
}
new(end()) T(value);
_size++;
}
Сломано:
template<class T>
void vector<T>::push_back(T &&value) {
if (_size >= _capacity) {
reallocate(_size * expansion_ratio);
}
// This is wrong.
// Using the assignment assumes that the destination is properly
// constructed member. The value at end() has not been constructed.
// So you must use the constructor (preferably move).
*end() = std::move(value);
// To do this correctly you must use the placement new.
// Like you do everywhere else.
new(end()) T(std::move(value));
_size++;
}
Здесь много вопросов:
template<class T>
void vector<T>::reallocate(size_t capacity) {
_capacity = capacity;
char *new_data = new char[sizeof(T) * _capacity]();
iterator new_begin = reinterpret_cast<iterator>(new_data);
// Not all types support move so this can use copy or move
// depending on the type. Which is good.
//
// But not all copy constructors are `noexcept` so this can potentially
// throw. If it throws then you need to make sure you do not leak.
// the pointers.
for (auto it = begin(); it != end(); it++)
// These objects have not been created so you can not use assign.
// So you need to use placement new (with move) to construct in
// in place.
*new_begin++ = std::move(*it);
// Though normally destructors are noexcept so it should not throw.
// you can not make that assumption with all random types (which is T).
// so you have to assume that it can potentially throw. If it throws
// when you call delete here you leave your object in an invalid state
// **AND** you leak the value of `new_data`.
//
// You can solve both of these by swapping first then calling delete.
//
// Another issue is that the destructors of T are not called here.
delete[] _data;
_data = new_data;
}
Используйте идиому копирования и обмена, чтобы решить проблему.
template<class T>
void vector<T>::reallocate(size_t capacity)
{
vector<T> newVersion(*this, capacity); // construct a new version
// with extra capacity
// you will need a new constructor
// for this.
// But any exceptions are self contained.
// and will not affect this object and prevent leaking.
// Now swap the internal data.
// the destructor of newVersion will do the cleanup automatically.
swap(newVersion);
}
Изменение размера означает, что вам нужно либо добавлять, либо удалять элементы.
template<class T>
void vector<T>::resize(size_t count) {
// Why not >=
if (count > _capacity)
reallocate(count * expansion_ratio);
// This changes the size but you may need to construct
// the objects if you are increasing the size.
// or if you reduce size you are going to need to destory
// the items you removed.
_size = count;
}
Вы пытаетесь правильно изменить размер здесь:
template<class T>
void vector<T>::resize(size_t count, const_reference value) {
// STUFF
for (size_t i = lastElementIndex; i < count; i++)
// Can not use assignment here.
// You need to use normal construction here.
*(it + i) = value;
}
template<class T>
bool operator==(const vector<T> &left, const vector<T> &right) {
if (left._size != right._size)
return false;
for (size_t i = 0; i < left._size; i++) {
// why not use the methods you have already defined.
if (left[i] != right[i]) {return false;}
// Very hard to read.
if (*(reinterpret_cast<T *>(left._data + sizeof(T) * i)) !=
*(reinterpret_cast<T *>(right._data + sizeof(T) * i)))
return false;
}
return true;
}
Пока он использует
newвыравнивание никогда не будет проблемой.— Мартин Йорк