Задачи минимальной векторной реализации C ++ STL

Question

У меня техническая проблема, и она меня действительно смущает.Я заранее прошу прощения, потому что, возможно, я не даю соответствующие детали;Я пока не понимаю, почему это не так, и было бы излишне включать весь код, с которым я работаю.

Я работаю с большой программой, использующей ST ++ C ++.Я перевожу этот код в очень чувствительную среду без стандартного клиба или внедрения STL;он переопределит malloc / free / new / delete и т. д. Для этого мне нужно заменить std :: parts на мои собственные упрощенные реализации.Я начал с std :: vector.Прямо сейчас он работает в стандартной экосистеме, поэтому это GNU libc и STL.Единственное, что изменилось, - это векторный класс.

Когда я выполняю программу с замененным классом, она вызывает ошибки.Я поместил это через GDB и обнаружил, что программа будет запрашивать объект из вектора, используя оператор индекса.Когда возвращается ссылка на объект, вызывается метод, и программа вызывает ошибки.Кажется, он не может найти этот метод и заканчивается в main_arena () в GDB.Тип объекта - унаследованный класс.

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

Я использую: g ++ (GCC) 4.4.5 20110214 (Red Hat 4.4.5-6) ​​

Буду очень признателен за любые отзывы / советы!

#ifndef _MYSTL_VECTOR_H_
#define _MYSTL_VECTOR_H_

#include <stdlib.h>
#include <assert.h>

typedef unsigned int uint;

namespace mystl
{
    /******************
      VECTOR
    ********************/


    template <typename T>
    class vector 
    {

        private:

            uint _size;
            uint _reserved;
            T *storage;

            void init_vector(uint reserve)
            {
                if (reserve == 0)
                {
                    _reserved = 0;
                    return;
                }

                storage = (T*)malloc(sizeof(T)*reserve);
                assert(storage);

                _reserved = reserve;
            }

        public:
            vector()
            {
                    // std::cerr << "default constructor " << this << std::endl;
                    storage = NULL;
                    _size = 0;
                    _reserved = 0;
            }

            vector(const vector<T> &other)
            {
                // std::cerr << "copy constructor " << this << std::endl;

                storage = NULL;
                _size = 0;
                _reserved = 0;


                init_vector(other.size());
                _size = other.size();

                for (uint i=0; i<other.size(); i++)
                {
                    storage[i] = T(other[i]);
                }
            }

            vector(uint init_num, const T& init_value)
            {
                    // std::cerr << "special constructor1 " << this << std::endl;

                        storage = NULL;
                        _size = 0;
                        _reserved = 0;

                      init_vector(init_num);

                      for (size_t i=0; i<init_num; i++)
                      {
                          push_back(init_value);
                      }
            }

            vector(uint init_num)
            {
                    // std::cerr << "special constructor2 " << this << std::endl;

                        storage = NULL;
                        _size = 0;
                        _reserved = 0;

                      init_vector(init_num);
            }

            void reserve(uint new_size) 
            {   
                if (new_size > _reserved) 
                {

                    storage = (T*)realloc(storage, sizeof(T)*new_size);
                    assert(storage);

                    _reserved = new_size;
                }
            }

            void push_back(const T &item) 
            {
                if (_size >= _reserved) 
                {
                    if (_reserved == 0) _reserved=1;
                    reserve(_reserved*2);
                }

                storage[_size] = T(item);
                _size++;
            }

            uint size() const
            {
                return _size;
            }

            ~vector()
            {
                if (_reserved)
                {
                    free(storage);
                    storage = NULL;
                    _reserved = 0;
                    _size = 0;
                }
            }

            // this is for read only
            const T& operator[] (unsigned i) const
            {
                // do bounds check...
                if (i >= _size || i < 0)
                {
                    assert(false);
                }
                return storage[i];
            }


            T& operator[] (unsigned i)
            {
                // do bounds check...
                if (i >= _size || i < 0)
                {
                    assert(false);
                }
                return storage[i];
            }

            // overload = operator
            const vector<T>& operator= (const vector<T>& x)
            {
                // check for self
                if (this != &x)
                {   
                    _reserved = 0;
                    _size = 0;
                    storage = NULL;

                    init_vector( x.size() );

                    for(uint i=0; i<x.size(); i++)
                    {
                        storage[i] = T(x[i]);
                    }

                    _size = x.size();
                }

                return *this;
            }

            uint begin() const
            {
                return 0;
            }

            void insert(uint pos, const T& value)
            {
                push_back(value);
                if (size() == 1)
                {
                          return;
                }
                for (size_t i=size()-2; i>=pos&& i>=0 ; i--)
                {
                    storage[i+1] = storage[i];
                }
                storage[pos] = value;
            }

            void erase(uint erase_index)
            {
                if (erase_index >= _size) 
                {
                    return;
                }
                //scoot everyone down by one
                for (uint i=erase_index; i<_size; i++)
                {
                    storage[i] = storage[i+1];
                }
                _size--;
            }


            void erase(uint start, uint end)
            {

                if (start > end)
                {
                    assert(false);
                }

                if (end > _size)
                    end = _size;

                for (uint i=start; i<end; i++)
                {
                    erase(start);
                }

                assert(false);
            }

            void clear()
            {
                erase(0,_size);
            }

        bool empty() const
        {
            return _size == 0;
        }

    }; //class vector
}


#endif // _MYSTL_VECTOR_H_

Answer 1

Вау!

1. Ваш оператор присваивания также теряет память.

2. Поскольку вы используете malloc / освобождаете конструктор по вашему типу T,не будет вызван, и поэтому вы не можете использовать свой вектор для чего-либо, кроме самых тривиальных объектов.

Редактировать:

Сегодня утром мне немного скучно: попробуйте это

#include <stdlib.h> // For NULL
#include <new>      // Because you need placement new

// Because you are avoiding std::
// An implementation of swap
template<typename T>
void swap(T& lhs,T& rhs)
{
    T   tmp = lhs;
    lhs = rhs;
    rhs = tmp;
}


template <typename T>
class vector
{
    private:
        unsigned int dataSize;
        unsigned int reserved;
        T*           data;

    public:
        ~vector()
        {
            for(unsigned int loop = 0; loop < dataSize; ++loop)
            {
                // Because we use placement new we must explicitly destroy all members.
                data[loop].~T();
            }
            free(data);
        }
        vector()
            : dataSize(0)
            , reserved(10)
            , data(NULL)
        {
            reserve(reserved);
        }

        vector(const vector<T> &other)
            : dataSize(0)
            , reserved(other.dataSize)
            , data(NULL)
        {
            reserve(reserved);
            dataSize = reserved;
            for(unsigned int loop;loop < dataSize;++loop)
            {
                // Because we are using malloc/free
                // We need to use placement new to add items to the data
                // This way they are constructed in place
                new (&data[loop]) T(other.data[loop]);
            }
        }

        vector(unsigned int init_num)
            : dataSize(0)
            , reserved(init_num)
            , data(NULL)
        {
            reserve(reserved);
            dataSize = reserved;
            for(unsigned int loop;loop < dataSize;++loop)
            {
                // See above
                new (&data[loop]) T();
            }
        }

        const vector<T>& operator= (vector<T> x)
        {
            // use copy and swap idiom.
            // Note the pass by value to initiate the copy
            swap(dataSize, x.dataSize);
            swap(reserved, x.rserved);
            swap(data,     x.data);

            return *this;
        }

        void reserve(unsigned int new_size)
        {
            if (new_size < reserved)
            {    return;
            }

            T*  newData = (T*)malloc(sizeof(T) * new_size);
            if (!newData)
            {    throw int(2);
            }

            for(unsigned int loop = 0; loop < dataSize; ++loop)
            {
                // Use placement new to copy the data
                new (&newData[loop]) T(data[loop]);
            }
            swap(data, newData);
            reserved    = new_size;

            for(unsigned int loop = 0; loop < dataSize; ++loop)
            {
                // Call the destructor on old data before freeing the container.
                // Remember we just did a swap.
                newData[loop].~T();
            }
            free(newData);
        }

        void push_back(const T &item)
        {
            if (dataSize == reserved)
            {
                reserve(reserved * 2);
            }
            // Place the item in the container
            new (&data[dataSize++]) T(item);
        }

        unsigned int  size() const  {return dataSize;}
        bool          empty() const {return dataSize == 0;}

        // Operator[] should NOT check the value of i
        // Add a method called at() that does check i
        const T& operator[] (unsigned i) const      {return data[i];}
        T&       operator[] (unsigned i)            {return data[i];}

        void insert(unsigned int pos, const T& value)
        {
            if (pos >= dataSize)         { throw int(1);}

            if (dataSize == reserved)
            {
                    reserve(reserved * 2);
            }
            // Move the last item (which needs to be constructed correctly)
            if (dataSize != 0)
            {
                new (&data[dataSize])  T(data[dataSize-1]);
            }
            for(unsigned int loop = dataSize - 1; loop > pos; --loop)
            {
                data[loop]  = data[loop-1];
            }
            ++dataSize;

            // All items have been moved up.
            // Put value in its place
            data[pos]   = value;
        }

        void clear()                                        { erase(0, dataSize);}
        void erase(unsigned int erase_index)                { erase(erase_index,erase_index+1);}
        void erase(unsigned int start, unsigned int end)    /* end NOT inclusive so => [start, end) */
        {
            if (end > dataSize)
            {   end     = dataSize;
            }
            if (start > end)
            {   start   = end;
            }
            unsigned int dst    = start;
            unsigned int src    = end;
            for(;(src < dataSize) && (dst < end);++dst, ++src)
            {
                // Move Elements down;
                data[dst] = data[src];
            }
            unsigned int count = start - end;
            for(;count != 0; --count)
            {
                // Remove old Elements
                --dataSize;
                // Remember we need to manually call the destructor
                data[dataSize].~T();
            }
        }
        unsigned int begin() const  {return 0;}


}; //class vector

Answer 2

При текущей обработке памяти этот вектор будет работать только с простыми старыми типами данных.

Для обработки всех типов необходимо убедиться, что объекты

• действительно созданы (mallocне делает этого),
• уничтожено (free не делает этого),
• , и вы не можете перераспределить память с помощью realloc, поскольку сложные объекты не гарантированно остаются действительными, еслипобайтно копируются в другое место.

Answer 3

Похоже, что ответ можно найти в вашем вопросе: «Когда возвращается ссылка на объект, вызывается метод, и программа вызывает ошибки. Кажется, что он не может найти этот метод и заканчивается в main_arena () в GDB. Тип объекта является унаследованным классом. "

Вы, вероятно, храните экземпляр базового класса T в векторе, но делаете push_back для экземпляра класса, унаследованного от T. В push_back {storage [_size] = T (item);} вы приводите (фактически создаете конструктор копирования T: Элемент T (const T &)) для T (это, вероятно, называется 'type cut'), затем получите ссылку на T и вызовите метод класса, унаследованного от T, используя виртуальную таблицу T, где метод еще не определен / абстрактный. Я прав? Для правильной работы вы должны поместить T * в вектор или shared_ptr / unique_ptr в зависимости от условий владения, которые вы применяете к векторным элементам. Обычно в векторе можно хранить только типы POD (Plain Old Data).