C ++ Vector Основы

Следуя моим двум предыдущим сообщениям.

Я написал подробный блог о том, как писать минимальный векторный класс. Этот набор статей был вдохновлен несколькими сообщениями на http://codereview.stackexchange.com (см. Источники ).

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

Руководитель:

#ifndef THORSANVIL_CONTAINER_VECTOR
#define THORSANVIL_CONTAINER_VECTOR

#include <type_traits>
#include <memory>
#include <algorithm>
#include <stdexcept>
#include <iterator>
#include <cmath>

namespace ThorsAnvil
{
    namespace Container
    {

Типы:

template<typename T>
class Vector
{
    public:
        using value_type        = T;
        using reference         = T&;
        using const_reference   = T const&;
        using pointer           = T*;
        using const_pointer     = T const*;
        using iterator          = T*;
        using const_iterator    = T const*;
        using difference_type   = std::ptrdiff_t;
        using size_type         = std::size_t;

    private:
        size_type       capacity;
        size_type       length;
        T*              buffer;

        struct Deleter
        {
            void operator()(T* buffer) const
            {
                ::operator delete(buffer);
            }
        };

Конструкторы:

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        template<typename I>
        Vector(I begin, I end)
            : capacity(std::distance(begin, end))
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            for(auto loop = begin;loop != end; ++loop)
            {
                pushBackInternal(*loop);
            }
        }
        Vector(std::initializer_list<T> const& list)
            : Vector(std::begin(list), std::end(list))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            clearElements<T>();
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                clearElements<T>();
                ::operator delete(buffer);

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            copyAssign<T>(copy);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }

Доступ:

        reference           operator[](size_type index)         {return buffer[index];}
        const_reference     operator[](size_type index) const   {return buffer[index];}
        reference           at(size_type index)                 {validateIndex(index);return buffer[index];}
        const_reference     at(size_type index) const           {validateIndex(index);return buffer[index];}
        reference           front()                             {return buffer[0];}
        const_reference     front() const                       {return buffer[0];}
        reference           back()                              {return buffer[length - 1];}
        const_reference     back() const                        {return buffer[length - 1];}

Сравнение:

        bool operator!=(Vector const& rhs) const {return !(*this == rhs);}
        bool operator==(Vector const& rhs) const
        {
            return (size() == rhs.size())
                ?  std::equal(begin(), end(), rhs.begin())
                :  false;
        }

итераторов:

        iterator            begin()                             {return buffer;}
        iterator            rbegin()                            {return std::reverse_iterator<iterator>(end());}
        const_iterator      begin() const                       {return buffer;}
        const_iterator      rbegin() const                      {return std::reverse_iterator<iterator>(end());}

        iterator            end()                               {return buffer + length;}
        iterator            rend()                              {return std::reverse_iterator<iterator>(begin());}
        const_iterator      end() const                         {return buffer + length;}
        const_iterator      rend() const                        {return std::reverse_iterator<iterator>(begin());}

        const_iterator      cbegin() const                      {return begin();}
        const_iterator      crbegin() const                     {return rbegin();}
        const_iterator      cend() const                        {return end();}
        const_iterator      crend() const                       {return rend();}

Немутирующие функции:

        size_type           size() const                        {return length;}
        bool                empty() const                       {return length == 0;}

Мутирующие функции:

        void push_back(T const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void push_back(T&& value)
        {
            resizeIfRequire();
            moveBackInternal(std::forward<T>(value));
        }
        template<typename... Args>
        void emplace_back(Args&&... args)
        {
            resizeIfRequire();
            constructBackInternal(std::forward<T>(args)...);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(size_type capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }

Частный:

    private:
        void validateIndex(size_type index)
        {
            if (index >= length)
            {
                throw std::out_of_range("Out of Range");
            }
        }

        void resizeIfRequire()
        {
            if (length == capacity)
            {
                size_type     newCapacity  = std::max(2.0, capacity * 1.62);
                reserveCapacity(newCapacity);
            }
        }
        void reserveCapacity(size_type newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            simpleCopy<T>(tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::forward<T>(value));
            ++length;
        }
        template<typename... Args>
        void constructBackInternal(Args&&... args)
        {
            new (buffer + length) T(std::forward<Args>(args)...);
            ++length;
        }
        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
        clearElements()
        {
            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
        clearElements()
        {
            // Trivially destructible objects can be re-used without using the destructor.
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                            &&  std::is_nothrow_destructible<X>::value) == true>::type
        copyAssign(Vector<X>& copy)
        {
            if (this == &copy)
            {
                return;
            }

            if (capacity <= copy.length)
            {
                clearElements<T>();
                length = 0;
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    pushBackInternal(copy[loop]);
                }
            }
            else
            {
                // Copy and Swap idiom
                Vector<T>  tmp(copy);
                tmp.swap(*this);
            }
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                             &&  std::is_nothrow_destructible<X>::value) == false>::type
        copyAssign(Vector<X>& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
        }
};

Хвост:

    }
}
#endif
11 голосов | спросил Martin York 20 MarpmSun, 20 Mar 2016 22:23:42 +03002016-03-20T22:23:42+03:0010 2016, 22:23:42

2 ответа


6

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

    bool operator==(Vector const& rhs) const
    {
        return (size() == rhs.size())
            ?  std::equal(begin(), end(), rhs.begin())
            :  false;
    }

Это кажется довольно запутанным, по крайней мере для меня. Я бы предпочел:

bool operator==(Vector const& rhs) const
{
    return (size() == rhs.size()) && std::equal(begin(), end(), rhs.begin());             
}

Я считаю, что это показывает намерение гораздо более прямо, и (благодаря оценке короткого замыкания) по-прежнему избегает оценки std::equal, если размеры не равны.

Некоторые из названий также кажутся несколько вводящими в заблуждение. Например, я бы переименовал resizeIfRequire в нечто вроде reallocIfRequired, так как он может влиять только на емкость, а не на размер.

О, глядя на множитель, который вы использовали: 1.62 - это плохой выбор. Цель использования золотой середины заключается в том, что это самый большой множитель, который вы можете использовать, который гарантирует, что (если они смежны) отброшенные части в конечном итоге будут объединены, чтобы быть достаточно большими, чтобы выполнить следующий больший размер запроса. Обратите внимание, что формулировка осторожно: золотое среднее - это множитель наибольший , который вы можете использовать и все еще получите этот результат. При округлении вверх от золотой середины (1.618 ...) до 1.62 вы в основном уверены, что это не может .

Чтобы получить желаемое поведение, вам нужно использовать множитель, который меньше или равен золотому средству. В большинстве случаев диспетчер памяти добавит немного накладных расходов на размер блока, который вы используете, поэтому, если вы используете именно золотую середину, это тоже не произойдет. Я бы рекомендовал множитель не более 1,6. Во многих случаях проще всего использовать 1.5, что делает целочисленную математику простой и по-прежнему получает примерно одинаковые эффекты (и справедливое количество эмпирических тестов показывает, что в целом хорошо работает).

ответил Jerry Coffin 21 MarpmMon, 21 Mar 2016 18:52:24 +03002016-03-21T18:52:24+03:0006 2016, 18:52:24
2

Мои 5 центов:

Это не кажется законным использовать std::forward, если это не универсальная ссылка.

Измените его на std::move или добавьте template<class UT>.

    void push_back(T&& value)
    {
        resizeIfRequire();
        moveBackInternal(std::forward<T>(value));
    }

Вы сделали это повсюду.

ответил Nick 27 MarpmSun, 27 Mar 2016 23:20:57 +03002016-03-27T23:20:57+03:0011 2016, 23:20:57

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

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

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