Реализация C ++-вектора

Я попытался реализовать базовый векторный тип в C ++, но я не уверен, могу ли я сделать что-либо более эффективно.

template < typename _Ty > class vector
{
public:
    typedef _Ty *iterator;
    typedef _Ty _Value_type;
    typedef vector<_Ty> _Myt;
    vector() 
        : __size(0), __capacity(10), __data((_Value_type *)calloc(10, sizeof(_Value_type)))
    {
    }
    vector(_Myt &_Rhs) 
        : __data((_Value_type *)calloc((__capacity = _Rhs.size() + 10), sizeof(_Value_type)))
    {
        memcpy(__data, _Rhs.__data, (__size = _Rhs.size()) * sizeof(_Value_type));
    }
    ~vector()
    { 
        memset(__data, NULL, 1);
    }
    _Value_type *data() const
    {
        return __data;
    }
    _Myt &push_back(const _Value_type &_Rhs)
    {
        if (++__size > __capacity)
        {
            reserve(__capacity + 10);
        }
        __data[__size - 1] = _Rhs;
        return *this;
    }
    _Myt &operator+=(const _Value_type &_Rhs)
    {
        return push_back(_Rhs);
    }
    UINT size() const
    {
        return __size;
    }
    UINT capacity() const
    {
        return __capacity;
    }
    iterator begin() const
    {
        return &__data[0];
    }
    iterator rbegin()
    {
        return reversed_adaptor().begin();
    }
    iterator end() const
    {
        return &__data[__size];
    }
    iterator rend()
    {
        return reversed_adaptor().end();
    }
    iterator find(const _Value_type &_Search) const
    {
        for (iterator i = begin(); i != end(); ++i)
        {
            if (*i == _Search)
            {
                return i;
            }
        }
        return NULL;
    }
    bool contains(const _Value_type &_Search) const
    {
        return find(_Search) != NULL;
    }
    _Myt &operator=(_Myt &_Rhs)
    {
        reserve((__size = _Rhs.size()) + 10);
        memcpy(__data, _Rhs.__data, _Rhs.size() * sizeof(_Value_type));
        return *this;
    }
    _Value_type pop_back()
    {
        _Value_type temp = __data[__size -= 1];
        resize(__size);
        return temp;
    }
    const _Value_type &at(UINT _Base) const
    {
        if (_Base >= 0 && _Base < size())
        {
            return __data[_Base];
        }
        throw std::out_of_range("vector::at - out of range");
    }
    _Value_type &at(UINT _Base)
    {
        if (_Base >= 0 && _Base < size())
        {
            return __data[_Base];
        }
        throw std::out_of_range("vector::at - out of range");
    }
    _Value_type &operator[](UINT _Base)
    {
        return __data[_Base];
    }
    const _Value_type &operator[](UINT _Base) const
    {
        return __data[_Base];
    }
    _Myt &swap(_Myt &_Rhs)
    {
        std::swap(*this, _Rhs);
        return *this;
    }
    _Myt &reserve(UINT _Capacity)
    {
        __data = (_Value_type *)realloc(__data, (__capacity = _Capacity) * sizeof(_Value_type));
        return *this;
    }
    _Myt &resize(UINT _Size, _Value_type _Value = _Value_type())
    {
        int over = (_Size > __size), temp = __size;
        __data = (_Value_type *)realloc(__data, (__capacity = (__size = _Size)) * sizeof(_Value_type));
        if (over)
        {
            for (iterator i = &__data[temp]; i != end(); ++i)
            {
                *i = _Value;
            }
        }
        return *this;
    }
    _Value_type erase(iterator _Iter)
    {
        if (_Iter == end())
        {
            return pop_back();
        }
        for (iterator i = _Iter; i + 1 != end(); ++i)
        {
            *i = *(i + 1);
        }
        return pop_back();
    }
    template < typename _Ty1 > bool operator==(const vector<_Ty1> &_Rhs)
    {
        if ((typeid(_Value_type) != typeid(_Ty1)) || size() != _Rhs.size())
        {
            return false;
        }
        for (iterator i = begin(), j = _Rhs.begin(); i != end(), j != _Rhs.end(); ++i, ++j)
        {
            if (*i != *j)
            {
                return false;
            }
        }
        return true;
    }
    template < typename _Ty1 > bool operator!=(const vector<_Ty1> &_Rhs)
    {
        return !(*this == _Rhs);
    }
    bool empty()
    {
        return size > 0;
    }
    _Myt &reverse()
    {
        std::reverse(begin(), end());
        return *this;
    }
    _Myt reversed_adaptor()
    {
        _Myt adaptor(*this);
        return adaptor.reverse();
    }
    _Myt insert(iterator _Begin, iterator _End)
    {
        for (iterator i = _Begin; i != _End; ++i)
        {
            push_back(*i);
        }
        return *this;
    }
private:
    _Value_type *__data;
    UINT __size, __capacity;
};
11 голосов | спросил Joseph 20 FebruaryEurope/MoscowbThu, 20 Feb 2014 17:20:47 +0400000000pmThu, 20 Feb 2014 17:20:47 +040014 2014, 17:20:47

2 ответа


8

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

  1. pop_back, pop_front и ---- +: = 2 =: + ---- должен иметь тип возврата erase

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

  2. void бессмысленно, так как вы все равно должны строить объекты.

  3. calloc в reserve(__capacity + 10); является нарушением договора о сложности.

    push_back требуется амортизировать push_back , что означает, что перераспределение должно быть в геометрической последовательности. Обычные значения: O(1) или reserve(__capacity * 2) и минимальная емкость 16 или около того.

  4. Как и код reserve(__capacity + (__capacity+1)/2), уже упомянутый ChrisW, вызов realloc в массиве, содержащем объекты, отличные от POD (и вектор для хранения объектов, отличных от POD), является UndefinedBehaviour ™.

    Компилятор может сделать все, что угодно, просто разбив все форматирование вашего жесткого диска, чтобы заставить демонов вылететь из вашего носа. И современные компиляторы могут быть настоящими суками при наказании UndefinedBehaviour ™. Влияние некоторых оптимизаций на неправильный код почти невозможно понять.

    Вам нужно скопировать элементы один за другим с помощью memcpy или цикла для правильного вызова конструкторов, и вам придется впоследствии вызвать деструкторы.

  5. Назначение неконфигурированной памяти в std::copy и push_back также является UndefinedBehaviour ™.

    Объект не-POD должен быть сконструирован конструктором и разрушен деструктором. Используйте новое место размещения:

    resize
  6. C ++ не имеет никакого типа, называемого new (i) _Value_type(_Rhs); .

    Тип размера всегда должен быть UINT

  7. std::size_t - другое нарушение договора сложности.

    Вектор swap() должен быть O (1). Он должен просто поменять указатели. Это далеко не то, что swap() будет делать в C ++ 03 (в C ++ 11 он мог сделать правильно if вы определили конструкторы перемещения, но вы этого не сделали).

    Далее std::swap должен быть перегружен для вектора, чтобы вызвать std::swap. Да, вам разрешено и иногда требуется перегружать функции /специализировать классы в swap() для типов, которые вы определяете, и это один из таких случаев.

  8. Вы правильно используете std в reserve, но вы не можете сделать то же самое в push_back.

  9. Специальное условие для insert в i == end() является излишним.

    Не разрешается передавать не откладываемый итератор (конечный или недействительный) на erase.

  10. Ваш erase возвращает бесполезный элемент (но см. 1. в любом случае).

    Вы возвращаете значение последнего pop_back, которое возвращает последний элемент. Если вы удалили какой-либо другой элемент, чем последний, это не тот, который был просто удален. Совершенно бесполезно. Вы все равно ничего не должны возвращать.

  11. Неправильные ошибки конфигурации.

    A erase метод должен только возвращать указатели и ссылки на const.

    Стандартные коллекции имеют const иiterator и все методы, возвращающие итераторы (const_iterator, begin(), end() и т. д.) имеют неконстантную перегрузку, возвращающую find() и const перегружать возвращаемый iterator. Если вы используете простые указатели (что является законным, концепция итератора разработана так, что указатели являются итераторами), вы должны определить const_iterator до const_iterator (const относится к части перед ней, поэтому это правильный синтаксис, даже в C).

  12. _Value_type const * и rbegin return bang указатели (если вы исправляете утечку памяти в деструкторе).

    Другой экземпляр UndefinedBehaviour ™. rend возвращает новый экземпляр. По стоимости, которая неэффективна, но легальна. Однако возвращаемое значение является временным, и оно должно иметь только reversed_adaptor /begin, и он будет уничтожен на следующей точке с запятой. Когда вы исправляете утечку памяти и фактически освобождаете память в деструкторе, возвращаемые указатели указывают на нераспределенную память.

  13. end и rbegin t верните действительные итераторы в invocant.

    Обратные итераторы должны указывать на контейнер, not на копию. Поскольку вы не можете использовать простые указатели для обратных операторов, для их определения довольно много работы. Boost имеет общую реализацию

  14. Вам не хватает большинства требуемых typedefs.

    Должно быть rend, value_type, reference, pointer, const_reference, const_pointer, const_iterator, reverse_iterator, const_reverse_iterator (должен быть size_type) и std::size_t (должен быть difference_type). И std::ptrdiff_t, что является следующей точкой.

  15. Вы должны использовать распределитель вместо allocator_type и malloc

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

    Распределитель по умолчанию, free использует глобальные операторы std::allocator и new[] для размещения, но пользователи могут захотеть предоставить специальные распределители.

    Также распределитель будет правильно перебрасывать delete[], как будет std::bad_alloc и new[] (за исключением несоответствующих платформ, таких как Microsoft Windows), если вы используете их напрямую, но при использовании delete[], вы должны проверить NULL и бросить malloc при самоопределении размещения.

Плюс все проблемы, уже упомянутые chrisW, тоже действительны, и я почти уверен, что все еще не нашел.

ответил Jan Hudec 21 FebruaryEurope/MoscowbFri, 21 Feb 2014 01:50:42 +0400000000amFri, 21 Feb 2014 01:50:42 +040014 2014, 01:50:42
7

Я думаю, что ваш деструктор ~vector() делает неправильную вещь:

  • Он должен освободить память, которую вы выделили, используя calloc
  • Он не должен memset над объектами, содержащимися в массиве
  • Я предполагаю, что он должен явно уничтожить объекты в массиве, используя противоположное размещение новый ... возможно, делая что-то вроде:
~vector
{
    for (iterator i = begin(); i != end(); ++i)
        i->~_Ty();
    free(__data);
}

Аналогично, методы, которые создают объект в памяти, должны использовать размещение новых, например, как описано здесь .

В настоящий момент вектор, который у вас есть, работает для типов, которые имеют тривиальный /несуществующий конструктор и деструктор (например, int ), но не для типов, у которых есть конструктор и деструктор не по умолчанию (например, std::string).


Ваш operator== должен быть const (чтобы его можно было использовать, когда *this is const).

Я подозреваю, что он не должен включать выражение typeid(_Value_type) != typeid(_Ty1): вместо этого он не должен определять _Ty1, поэтому его можно использовать только для сравнения векторов, имеющих одинаковый тип.

Это предлагает вам закодировать его как бесплатный оператор (встроенный функции, которые принимают два параметра), а не как метод.


Ваш метод find должен возвращать end(), а не NULL, если он не находит.


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

class A
{
    A* self;
public:
    A() { self = this; }
    A(const A&) { ... to be supplied ... }
    const A& operator=(const A&) { ... to be supplied ... }
    A(A&&) { ... to be supplied ... }
    A& operator=(A&&) { ... to be supplied ... }
}

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

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


Ваши идентификаторы не должны начинаться с подчеркивания _. Эти идентификаторы зарезервированы для компилятора и /или стандартной библиотеки времени выполнения .


Ваш метод insert не имеет большого смысла: его подпись не соответствует ни одному из три стандартных метода вставки .

ответил ChrisW 20 FebruaryEurope/MoscowbThu, 20 Feb 2014 17:39:06 +0400000000pmThu, 20 Feb 2014 17:39:06 +040014 2014, 17:39:06

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132