Работа с векторами без использования STL и библиотеки <vector>

@Sigma214 · Регистрация: 01.05.2012

Author24 — интернет-сервис помощи студентам

Здравствуйте Уважаемые формучане. Подскажите пожалуйста, есть ли смысл писать свой собственный класс Vector если из него всё равно будет выходить подобие STL?

В универе препод дал такое задание. Hо, я как не напишу свой класс Vector у меня всё равно выходит подобие STL.

Есть ли смысл тогда его вообще писать если он не будет защищен от внутренних проверок (например, выход элемента за границу вектора) или проще использовать стандартную библиотеку?

C++

<vector>

Помогите пожалуйста советом.

Я в итоге программу написал, но с использованием STL и <vector>.

@Nick Alte · 04.04.2016, 20:29

Смысл писать свой аналог контейнера из STL вижу в двух случаях: а) для обучения, чтобы понять, что у STL "под капотом"; б) когда есть свои довольно-таки специфические потребности, которым STL не соответствует, а надо, и при этом ещё есть достаточно твёрдые знания предмета и уверенность, что получится не хуже. Во втором случае, конечно же, уверенность крайне желательно проверить сравнительными испытаниями и исчерпывающим тестированием.

@Fulcrum_013 · 04.04.2016, 20:37

Сообщение от Sigma214

Помогите пожалуйста советом.

По разному. Зависит от потребностей. У меня к примеру vector в его исходном виде никогда не использовался, как миниму допиливался кое-какой функционал. Ну и еще один ньюанс - вектор кое в чем очень безграмотно спроектирован. Объясню в чем. Если динамический массив имеет функцию добавления элемента, то во избежания проблем с быстродействием и фрагментацией памяти шаг роста при ресайзе должен быть управляемым, а допиливание такого в std::vector тянет на полную его переделку. Опять же возможны разные вариации на тему вектора. Например массивы работающее по типу указателей. т.е. сам массив не хранит данные а только ссылку на буфер данных, который ведет подсчет ссылок. При присваивании массивы не копируются, копируется только указатель на буфер. В результате поведение таких массивов соответствует обычным указателям, только со всеми плюшками динамического массива, что в некоторых случаях позволяет экономить память а так же получить при некоторых задачах гораздо более высокое быстродействие, нежели плодя копии данных как это делает std::vector. Опять же под хранение списков указателей на объекты удобнее сделать специализированный для них контейнер, нежели пользовать std::vector<unique_ptr<>> или std::vector<shared_ptr<>>, а особенно если эти списки должны поддерживать сериализацию/десериализацию полиморфного контента.

Сообщение от Sigma214

Есть ли смысл тогда его вообще писать если он не будет защищен от внутренних проверок (например, выход элемента за границу вектора)

Есть смысл сделать проверку выхода за границы отключаемой в релизе. У std::vector есть доступ как с проверкой так и без проверки границ. Но к сожалению не переключаемый автоматически при смене конфигурации Debug/Release

Добавлено через 3 минуты

Сообщение от Nick Alte

а) для обучения, чтобы понять, что у STL "под капотом";

Вот то то и оно. Потому что когда понадобится пункт б пункт а будет просто необходим.

@Sigma214 · 04.04.2016, 22:21 **[ТС]**

Сообщение от Fulcrum_013

std

по заданию мне запрещено использовать <vector> и STL. Но можно использовать std.

@Fulcrum_013 · 04.04.2016, 22:25

Сообщение от Sigma214

по заданию мне запрещено использовать <vector> и STL. Но можно использовать std.

std это неймспейс STL. Сделать свой класс все равно полезно. Говорю по собственному опыту. Ну правда когда мне такие задания не препады давали, а они вытекали из тех заданий которые давали препады, STL еще и в помине не существовало, поэтому приходилось самостоятельно весь этот набор организовывать. Зато потом сразу видно для чего набор того что есть в stl применим и эффективен, а для чего его лучше не использовать.

@hoggy · 05.04.2016, 21:22

Сообщение от Sigma214

Подскажите пожалуйста, есть ли смысл писать свой собственный класс Vector если из него всё равно будет выходить подобие STL?

это полезно на этапе обучения.

Сообщение от Sigma214

Есть ли смысл тогда его вообще писать если он не будет защищен от внутренних проверок (например, выход элемента за границу вектора) или проще использовать стандартную библиотеку?

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

@obivan · 07.04.2016, 14:38

Sigma214, ТС`у, тут какие то не шуточные споры, но для практики преподаватель тоже давал задание написать свой вектор, если нужно то вот что я делал

Кликните здесь для просмотра всего текста

C++

template <class T> class iterator {
    protected:
        T *ptr;
    public:
        iterator() : ptr(nullptr) {}
        iterator(T* ptr) : ptr(ptr) {}
        virtual ~iterator() { if (ptr != nullptr) delete[] ptr; }
        T& operator*() { return *ptr; }
        T* operator->() { return ptr; }
        bool operator==(const iterator& other) const { return ptr == other.ptr; }
        bool operator!=(const iterator& other) const { return !(*this == other); }
    };
    template <class T> class std_iterator : public iterator<T> {
    public:
        std_iterator() : iterator<T>() {}
        std_iterator(T* ptr) : iterator<T>(ptr) {}
        T* operator++() { return ++ptr; }
        T* operator--() { return --ptr; }
        T* operator+(int i) { return ptr + i; }
        T* operator-(int i) { return ptr - i; }
    };
    template <class T> class reverse_iterator : public iterator<T> {
    public:
        reverse_iterator() : iterator<T>() {}
        reverse_iterator(T* ptr) : iterator<T>(ptr) {}
        virtual T* operator++() override final { return --ptr; }
        virtual T* operator--() override final { return ++ptr; }
        virtual T* operator+(int i) override final { return ptr - i; }
        virtual T* operator-(int i) override final { return ptr + i; }
    };
    template <class T> class const_std_iterator : public std_iterator<T> {
    public:
        const_std_iterator(T* ptr) : std_iterator<T>(ptr) {}
        const T& operator*() { return *ptr; }
        const T* operator->() { return ptr; }
    };
    template <class T> class const_reverse_iterator : public reverse_iterator<T> {
    public:
        const_reverse_iterator(T* ptr) : reverse_iterator<T>(ptr) {}
        const T& operator*() { return *ptr; }
        const T* operator->() { return ptr; }
    };
    template <class T> class myVector {
    private:
        typedef unsigned int uInt;
        T * m_Data;
        uInt m_Size;
    public:
        myVector(void);
        ~myVector(void);
        myVector(const T*, const uInt);
        myVector(const myVector&);
 
        T& operator[](const uInt);
        myVector & operator=(const myVector&);
 
        inline std_iterator<T> begin(void);
        inline std_iterator<T> end(void);
        inline reverse_iterator<T> rbegin(void) const;
        inline reverse_iterator<T> rend(void) const;
        inline const_std_iterator<T> cbegin(void) const;
        inline const_std_iterator<T> cend(void) const;
        inline const_reverse_iterator<T> crbegin(void) const;
        inline const_reverse_iterator<T> crend(void) const;
 
        void resize(const uInt);
        void resize(const uInt, const T);
        inline auto size(void) const;
        inline auto capacity(void) const;
        auto empty(void) const;
 
        void setData(const T*, const uInt);
        inline T* data(void) const;
        inline T& front(void) const;
        inline T& at(const uInt) const;
        inline T& back(void) const;
 
        void clear(void);
        void pop_back(void);
        void push_back(const T);
        void erase(const uInt);
        void erase(const std_iterator<T>);
        void swap(const uInt, const uInt);
        void insert(const T, const uInt);
        void assign(const T, const uInt);
        void assign(const std_iterator<T>, const std_iterator<T>);
    };
    template <class T> class my_unique_ptr {
    private:
        T * ptr;
        my_unique_ptr(my_unique_ptr & elem) {
        }
        my_unique_ptr & operator=(my_unique_ptr & elem) {
        }
    public:
        my_unique_ptr(void) : ptr(nullptr) {
        }
        ~my_unique_ptr(void) {
            delete[] ptr;
        }
 
        T& operator*(void) { return *ptr; }
        T* operator->(void) { return ptr; }
        bool operator==(my_unique_ptr & elem) { return ptr == elem.ptr; }
        bool operator!=(my_unique_ptr & elem) { return ptr != elem.ptr }
 
        T * relise(void) {
            T * tmp = ptr;
            ptr = nullptr;
            return tmp;
        }
        void reset(T * obj) {
            if (ptr != nullptr) delete[] ptr;
            ptr = obj;
        }
        void swap(my_unique_ptr & obj) {
            T * tmp = ptr;
            ptr = obj.ptr;
            obj.ptr = tmp;
        }
 
        T* get(void) { return ptr; }
    };
    template <class T> myVector<T>::myVector(void) : m_Size(0), m_Data(nullptr) {
    }
    template <class T> myVector<T>::~myVector(void) {
        if (m_Data != nullptr) delete[] m_Data;
    }
    template <class T> myVector<T>::myVector(const T * Data, const uInt Size) : m_Data(nullptr), m_Size(0) {
        setData(Data, Size);
    }
    template <class T> myVector<T>::myVector(const myVector & obj) : m_Data(nullptr), m_Size(0) {
        setData(obj.m_Data, obj.m_Size);
    }
 
    template <class T> T& myVector<T>::operator[](const uInt index) {
        return m_Data[index];
    }
    template <class T> myVector<T>& myVector<T>::operator=(const myVector & elem) {
        if (&elem == this) return *this;
        if (m_Data != nullptr) delete[] m_Data;
        setData(elem.m_Data, elem.m_Size);
        return *this;
    }
 
    template <class T> inline std_iterator<T> myVector<T>::begin(void) { return m_Data; }
    template <class T> inline std_iterator<T> myVector<T>::end(void) { return m_Data + m_Size; }
    template <class T> inline const_std_iterator<T> myVector<T>::cbegin(void) const { return m_Data; }
    template <class T> inline const_std_iterator<T> myVector<T>::cend(void) const { return m_Data + m_Size; }
    template <class T> inline reverse_iterator<T> myVector<T>::rbegin(void) const { return m_Data + m_Size - 1; }
    template <class T> inline reverse_iterator<T> myVector<T>::rend(void) const { return m_Data - 1; }
    template <class T> inline const_reverse_iterator<T> myVector<T>::crbegin(void) const { return m_Data + m_Size - 1; }
    template <class T> inline const_reverse_iterator<T> myVector<T>::crend(void) const { return m_Data - 1; }
 
    template <class T> void myVector<T>::resize(const uInt Size) {
        T * tmp = new T[Size];
        for (int i(0); i < m_Size; i++)
            tmp[i] = m_Data[i];
 
        delete[] m_Data;
        m_Data = tmp;
        m_Size = Size;
    }
    template <class T> void myVector<T>::resize(const uInt Size, const T value) {
        T * tmp = new T[Size];
        for (int i(0); i < m_Size; i++)
            tmp[i] = m_Data[i];
        for (int i(m_Size); i < Size; i++)
            tmp[i] = value;
 
        delete[] m_Data;
        m_Data = tmp;
        m_Size = Size;
    }
    template <class T> inline auto myVector<T>::size(void) const { return m_Size; }
    template <class T> inline auto myVector<T>::capacity(void) const { return sizeof(m_Data[0]); }
    template <class T> auto myVector<T>::empty(void) const { return m_Size == 0 ? true : false; }
 
    template <class T> void myVector<T>::setData(const T * Data, const uInt Size) {
        m_Size = Size;
        if (m_Data != nullptr) delete[] m_Data;
        m_Data = new T[m_Size];
        for (int i(0); i < m_Size; i++)
            m_Data[i] = Data[i];
    }
    template <class T> inline T* myVector<T>::data(void) const { return m_Data; }
    template <class T> inline T& myVector<T>::front(void) const { return m_Data[0]; }
    template <class T> inline T& myVector<T>::at(const uInt index) const { return m_Data[index]; }
    template <class T> inline T& myVector<T>::back(void) const { return m_Data[m_Size - 1]; }
 
    template <class T> void myVector<T>::clear(void) {
        m_Size = 0;
        delete[] m_Data;
        m_Data = nullptr;
    }
    template <class T> void myVector<T>::pop_back(void) {
        m_Size--;
        T * tmp = new T[m_Size];
        for (int i(0); i < m_Size; i++)
            tmp[i] = m_Data[i];
 
        delete[] m_Data;
        m_Data = tmp;
    }
    template <class T> void myVector<T>::push_back(const T elem) {
        T * tmp = new T[m_Size + 1];
        for (int i(0); i < m_Size; i++)
            tmp[i] = m_Data[i];
        tmp[m_Size] = elem;
 
        delete[] m_Data;
        m_Data = tmp;
        m_Size++;
    }
    template <class T> void myVector<T>::erase(const uInt index) {
        for (int i(index); i < m_Size - 1; i++)
            m_Data[i] = m_Data[i + 1];
 
        T * tmp = new T[m_Size - 1];
        for (int i(0); i < m_Size - 1; i++)
            tmp[i] = m_Data[i];
 
        delete[] m_Data;
        m_Data = tmp;
        m_Size--;
    }
    template <class T> void myVector<T>::erase(std_iterator<T> iter) {
        int num;
        for (int i(0); i < m_Size; i++)
            if (iter == &m_Data[i]) {
                num = i;
                break;
            }
 
        for (int i(num); i < m_Size - 1; i++)
            m_Data[i] = m_Data[i + 1];
 
        T * tmp = new T[m_Size - 1];
        for (int i(0); i < m_Size - 1; i++)
            tmp[i] = m_Data[i];
 
        delete[] m_Data;
        m_Data = tmp;
        m_Size--;
    }
    template <class T> void myVector<T>::swap(const uInt from, const uInt with) {
        T tmp = m_Data[from];
        m_Data[from] = m_Data[with];
        m_Data[with] = tmp;
    }
    template <class T> void myVector<T>::insert(const T elem, const uInt position) {
        T * tmp = new T[m_Size + 1];
        for (int i(0); i < m_Size; i++)
            tmp[i] = m_Data[i];
 
        for (int i(m_Size); i > position; i--)
            tmp[i] = tmp[i - 1];
 
        tmp[position] = elem;
 
        delete[] m_Data;
        m_Data = tmp;
        m_Size++;
    }
    template <class T> void myVector<T>::assign(T elem, const uInt Size) {
        m_Size = Size;
        if (m_Data != nullptr) delete[] m_Data;
        m_Data = new T[m_Size];
        for (int i(0); i < m_Size; i++)
            m_Data[i] = elem;
    }
    template <class T> void myVector<T>::assign(std_iterator<T> first, std_iterator<T> last)
    {
        int i = 0;
        for (auto it = first; it != last; ++it, i++);
        m_Size = i;
        if (m_Data != nullptr) delete[] m_Data;
        m_Data = new T[m_Size];
        i = 0;
        for (auto it = first; it != last; ++it, i++)
            m_Data[i] = *it;
    }

может что возьмете, не лучшее и не очень оптимизированное исполнение, но вроде работает

P.S помойму тут не финальная версия, и я там накосячил с итераторами немного, ну если нужно будет поправите

@Fulcrum_013 · 08.04.2016, 04:00

Сообщение от obivan

не лучшее и не очень оптимизированное исполнение

первая простейшая оптимизация с очисткой:

C++

1
2
3

    
inline void Pack(){Capacity=Count;};
inline void Clear(bool DoPack=false){Count=0; if (DoPack) Pack();};

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

Сообщение от obivan

и я там накосячил с итераторами немного, ну если нужно будет поправите

Естественно. Зачем итератор в деструкторе удаляет элемент на который укзывает? он только указатель а не владелец элемента, соответственно и удалять ничего не должен. А так вот такой код

C++

void main(){
     myVector<int> a;
     // .....заполнение вектора;
     { 
              auto b=a.begin();
     } // вот здесь удалит буфер данных вектора.
}

@tezaurismosis · 09.04.2016, 19:25

Комментарий модератора

Весь оффтоп о внутренностях стандартной библиотеки вынесен в отдельную тему: О деталях и возможностях реализации <vector>

@Nick Alte 1674 / 1046 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	04.04.2016, 20:29	2
	Смысл писать свой аналог контейнера из STL вижу в двух случаях: а) для обучения, чтобы понять, что у STL "под капотом"; б) когда есть свои довольно-таки специфические потребности, которым STL не соответствует, а надо, и при этом ещё есть достаточно твёрдые знания предмета и уверенность, что получится не хуже. Во втором случае, конечно же, уверенность крайне желательно проверить сравнительными испытаниями и исчерпывающим тестированием. 0

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.04.2016, 20:37	3
	Сообщение от Sigma214 Помогите пожалуйста советом. По разному. Зависит от потребностей. У меня к примеру vector в его исходном виде никогда не использовался, как миниму допиливался кое-какой функционал. Ну и еще один ньюанс - вектор кое в чем очень безграмотно спроектирован. Объясню в чем. Если динамический массив имеет функцию добавления элемента, то во избежания проблем с быстродействием и фрагментацией памяти шаг роста при ресайзе должен быть управляемым, а допиливание такого в std::vector тянет на полную его переделку. Опять же возможны разные вариации на тему вектора. Например массивы работающее по типу указателей. т.е. сам массив не хранит данные а только ссылку на буфер данных, который ведет подсчет ссылок. При присваивании массивы не копируются, копируется только указатель на буфер. В результате поведение таких массивов соответствует обычным указателям, только со всеми плюшками динамического массива, что в некоторых случаях позволяет экономить память а так же получить при некоторых задачах гораздо более высокое быстродействие, нежели плодя копии данных как это делает std::vector. Опять же под хранение списков указателей на объекты удобнее сделать специализированный для них контейнер, нежели пользовать std::vector<unique_ptr<>> или std::vector<shared_ptr<>>, а особенно если эти списки должны поддерживать сериализацию/десериализацию полиморфного контента. Сообщение от Sigma214 Есть ли смысл тогда его вообще писать если он не будет защищен от внутренних проверок (например, выход элемента за границу вектора) Есть смысл сделать проверку выхода за границы отключаемой в релизе. У std::vector есть доступ как с проверкой так и без проверки границ. Но к сожалению не переключаемый автоматически при смене конфигурации Debug/Release Добавлено через 3 минуты Сообщение от Nick Alte а) для обучения, чтобы понять, что у STL "под капотом"; Вот то то и оно. Потому что когда понадобится пункт б пункт а будет просто необходим. 0

@Sigma214 44 / 44 / 24 Регистрация: 01.05.2012 Сообщений: 178
	04.04.2016, 22:21 [ТС]	4
	Сообщение от Fulcrum_013 std по заданию мне запрещено использовать <vector> и STL. Но можно использовать std. 0

@Fulcrum_013 2063 / 1542 / 168 Регистрация: 14.12.2014 Сообщений: 13,402
	04.04.2016, 22:25	5
	Сообщение от Sigma214 по заданию мне запрещено использовать <vector> и STL. Но можно использовать std. std это неймспейс STL. Сделать свой класс все равно полезно. Говорю по собственному опыту. Ну правда когда мне такие задания не препады давали, а они вытекали из тех заданий которые давали препады, STL еще и в помине не существовало, поэтому приходилось самостоятельно весь этот набор организовывать. Зато потом сразу видно для чего набор того что есть в stl применим и эффективен, а для чего его лучше не использовать. 0

@hoggy 8739 / 4317 / 960 Регистрация: 15.11.2014 Сообщений: 9,760
	05.04.2016, 21:22	6
	Сообщение от Sigma214 Подскажите пожалуйста, есть ли смысл писать свой собственный класс Vector если из него всё равно будет выходить подобие STL? это полезно на этапе обучения. Сообщение от Sigma214 Есть ли смысл тогда его вообще писать если он не будет защищен от внутренних проверок (например, выход элемента за границу вектора) или проще использовать стандартную библиотеку? вы, наверное, имели ввиду, если он не будет защищен внутренними проверками. я б такую халтуру вообще бы не принял. 0