2
\$\begingroup\$

So, as an exercise I wanted to write a dynamic array, like std::vector. I wanted to know if there are any things that could be done better or anything I did wrong. Thank you!

    template<typename T>
    class myVector {
    using size_type = size_t;
    public:
    void pop(void) {
      changeSize(--m_Used);
    }

    void pop(size_type index) {
      if (!(index < m_Size)) return;
      changeSize(m_Used -= index);
    }

    bool push(const T& obj) {
      if (m_Used == m_Size) {
        bool temp = changeSize(++m_Used);
        m_Buffer[m_Used - 1] = obj;
        return temp;
      }
      m_Buffer[m_Used++] = obj;
      return true;
    }

    inline size_type used(void) const { return m_Used; }
    inline size_type size(void) const { return m_Size; }

    T& operator[](size_type index){
      return m_Buffer[index];
    }

    const T& operator[](size_type index) const{
      return m_Buffer[index];
    }

    inline T* begin(void) { return m_Buffer; }
    inline T* end(void) { return begin() + m_Used; }
    inline const T* const begin(void) const { return m_Buffer; }
    inline const T* const end(void) const { return begin() + m_Used; }

  public:
    bool reserve(size_type _size) {
      if (m_Buffer and !(m_Size < _size)) return 1;
      return changeSize(_size);
    }

    myVector(void) {
      m_Buffer = (T*)malloc(sizeof(T));
      m_Used = 0;
      m_Size = 1;
    }

    myVector(const myVector<T>& other) {
      *this = other;
    }

    myVector<T>& operator=(const myVector<T>& rhs) {
      if(rhs.m_Buffer){
        m_Used = rhs.m_Used;
        m_Size = rhs.m_Size;
        free(m_Buffer);
        m_Buffer = (T*)malloc(sizeof(T) * m_Size);
        memcpy(m_Buffer,rhs.m_Buffer,sizeof(T) * m_Size);
      }
      return *this;
    }

    template<size_type N>
    myVector(const T (&inputArr)[N]) {
      *this = inputArr;
    }

    template<size_type N>
    myVector<T>& operator=(const T (&inputArr)[N]) {
      m_Size = N;
      m_Used = m_Size;
      m_Buffer = (T*)malloc(m_Size * sizeof(T));
      memcpy(m_Buffer,inputArr, N * sizeof(T));
      return *this;
    }

    myVector<T>& operator=(const std::initializer_list<T>& rhs) {
      m_Size = rhs.size();
      m_Used = m_Size;
      m_Buffer = (T*)malloc(m_Size * sizeof(T));
      memcpy(m_Buffer,rhs.begin(),m_Size * sizeof(T));
      return *this;
    }

    myVector(const std::initializer_list<T>& other) {
      *this = other;
    }

    ~myVector() {
      free(m_Buffer);
    }

    bool contains(const T& obj) const {
        return std::find(begin(),end(),obj) != end();
    }

  private:
    T* m_Buffer;
    size_type m_Used;
    size_type m_Size;

    bool changeSize(size_type _size) {
      T* newBuffer = (T*)realloc(m_Buffer, sizeof(T) * _size);
      if (newBuffer) {
        m_Buffer = newBuffer;
        m_Size = _size;
        return true;
      }
      return false;
    }
};

\$\endgroup\$
2
  • \$\begingroup\$ Fundamental concept of most dynamic arrays: They don't (re-)allocate for each element, but more like "double their size each time". Means log(N) allocations, not N. \$\endgroup\$ Jan 19, 2020 at 1:20
  • 2
    \$\begingroup\$ Please have a read of the Vector series I wrote: lokiastari.com/series \$\endgroup\$ Jan 19, 2020 at 5:55

2 Answers 2

4
\$\begingroup\$

Overall

Please fix the formatting.
It's hard to find the public/private sections that way this is formatted.


A fundamental miss of your dynamic array is that objects are not correctly created or destroyed.

You use malloc() and realloc() to allocate memory. But these functions do not call the constructors on class type objects. Thus the memory is not correctly initialized to hold objects of type T, it is undefined behavior to use these objects until they have been correctly initialized (with a constructor).

Conversely you also need to call the destructor when the object is popped or the destructor for your vector is called.

As a result your code is fundamentally broken.


You have not correctly implemented the rule of three.

Please look it up. But basically if your object owns a pointer you need to overide the compiler implementation of several functions correctly.

As a result your code is fundamentally broken.


You have not thought about move semantics.

Since C++11 (9 years ago). C++ has had the concept of move semantics that allow objects to be moved rather than copied. In the worst case this is no worse than a copy but in the best case it is much better than a copy and makes classes a lot more efficient if you start passing them around (eg return values).

This is a nice to have but to be honest expected especially for containers in modern code.


Code Review

This line:

    using size_type = size_t;

means that somewhere (not included) you have the line:

using namespace std;

This is a problem for anything but toy code. Please stop adding this line to your code. Read any other C++ review.

See: Why is “using namespace std;” considered bad practice?


I have no problem you not checking that m_Used is not zero here.

    void pop(void) {
      changeSize(--m_Used);
    }

But it is inconsistent when you do check it here.

    void pop(size_type index) {
      if (!(index < m_Size)) return;
      changeSize(m_Used -= index);
    }

Choose one. Either always check or never check. The std::vector<> does not check. But provides the appropriate functions that allow the user of the vector to validate the state so it can be called safely.


This is not enough:

      changeSize(--m_Used);

If you remove an object from the vector you need to destroy it. This means calling its destructor. Classes of type T may depend on the constructor/destructor being called.

You can call it manually.

      m_Buffer[m_Used].~T();
      changeSize(--m_Used);

Why are you calling changeSize() in the pop?

The whole point of having a m_Used and m_Size members is that you may have unused space in your vector that you can utilize on the next push without having to re-size the vector on every single operation!


Conversely on the push. You can simply call the assignment operator.

        m_Buffer[m_Used - 1] = obj;

Since you allocated the space with malloc() or realloc() this space has not been correctly initialized with the constructor thus calling the assignment operator on this object is not valid.

You can call the constructor by using placement new

        new (m_Buffer + m_Used) T(obj);  // Call the copy constructor
                                         // using placement new
        ++m_Used;

Don't use the inline keyword unless you need to.

    inline size_type used(void) const { return m_Used; }
    inline size_type size(void) const { return m_Size; }

Here you don't need to. It does not force the compiler to actually "inline" the code (it actually does nothing on modern compilers as the compiler engineers realized long ago the programmers are bad and the compiler is much better at making that decision).


Yes perfectly good.

    inline T* begin(void) { return m_Buffer; }
    inline T* end(void) { return begin() + m_Used; }
    inline const T* const begin(void) const { return m_Buffer; }
    inline const T* const end(void) const { return begin() + m_Used; }

Though personally I would have abstracted the iterator.

    using iterator = T*;
    using const_iterator = T const*;

The other thing to think about is that the standard containers contain a couple of additional iterator methods.

    const_iterator cbegin() const;  // Notice the 'c'
    const_iterator cend()   const;

Also reverse iterators are worth using.

    <something>       rbegin();
    <const something> crbeign() const;
    // etc

Using the keyword and seems weird.

      if (m_Buffer and !(m_Size < _size)) return 1;

Yes its valid. But you need to add a special header. Also most engineers are simply used to reading &&.


Constructors at last.

Would be nice to put constructors/destructors/assignment near the top. This the first thing you need to know about a class (also the first thing people in code review want to check).

    // Sure this is fine.
    // But only space for one item?
    // Why not pre-allocate 10 so you don't need to reallocate on each push.
    // You don't need void here.
    myVector(void) {
      m_Buffer = (T*)malloc(sizeof(T));
      m_Used = 0;
      m_Size = 1;
    }

    // Normally the assignment operator is written in terms of the
    // copy constructor. You seem to have done this the complete other
    // way around. But it also mens that you should initialize all the
    // members before you call the assignment operator (it is assuming
    // you are using a fully formed object not one with random values)
    //
    // Go look up the copy and swap idiom.
    myVector(const myVector<T>& other) {
      *this = other;
    }

    // What about self assignment.
    // It is perfectly valid to assign to yourself. Your code
    // needs to work in this situation. If the rhs has a null
    // buffer why does nothing change?
    // 
    // See Copy and swap idiom.
    myVector<T>& operator=(const myVector<T>& rhs) {
      if(rhs.m_Buffer){
        m_Used = rhs.m_Used;
        m_Size = rhs.m_Size;

        // This frees your buffer.
        // But what happens to all the objects of type T.
        // You just leaked them all without calling there destructor.
        free(m_Buffer);


        // What happens if this fails?
        // Well with strong exception safety you would not change the
        // current object and throw an exception. But you have lost
        // all the old state so if you throw you are in a bad state.
        m_Buffer = (T*)malloc(sizeof(T) * m_Size);
        memcpy(m_Buffer,rhs.m_Buffer,sizeof(T) * m_Size);
      }
      return *this;
    }

This is how your constructors should look (approximately).

    // Please not the use of initializer list.
    // I am using malloc here because you did (but you can do better).
    myVector()
        : m_buffer(malloc(sizeof(T) * 10))
        , m_Used(0)
        , m_Size(10)
    {}

    // Copy constructor.
    myVector(myVector const& copy)
        : m_buffer(malloc(sizeof (T) * copy.m_Used)
        , m_Used(0)           // We will update this in the code.
        , m_Size(copy.m_Used)
    {
        for(int loop = 0; loop < m_Used; ++loop) {
            push(copy.buffer[loop]);
        }
    }

    // Copy Assignment
    // Use Copy and Swap Idiom (look it up)
    myVector& operator=(myVector const& rhs)
    {
        myVector copy(rhs);   // safely make a copy.
        swap(copy);           // swap the copy and the current object.
        return *this;
    }                         // Note copy destroyed here.
                              // Thus the old array is deleted.

    // Destructor
    ~myVector()
    {
        clear();             // delete all the objects.
        free(m_buffer);
    }

    // Swapping
    void swap(myVector& other) noexcept
    {
         using std::swap;
         swap(m_buffer,    other.m_buffer);
         swap(m_Used,      other.m_used);
         swap(m_Size,      other.m_size);
    }
    friend void swap(myVector& lhs, myVector& rhs)
    {
         lhs.swap(rhs);
    }
  
    // Move semantics are relatively simple:
    myVector(myVector&& move) noexcept
        : m_buffer(nullptr)
        , m_Used(0)
        , m_Size(0)
    {
        swap(move);
    }
    myVector& operator(myVector&& move) noexcept
    {
        clear();
        swap(move);
        return *this;
    }

    // Now just implement push/clear

Not advisable to do this!!

    template<size_type N>
    myVector(const T (&inputArr)[N]) {
      *this = inputArr;
    }

--

You can't use memcpy() on T if it has a constructor.

      memcpy(m_Buffer,inputArr, N * sizeof(T));

In C++ this is most types. So this is going to fail to correctly construct these objects.


Self Plug

I wrote a couple of articles on how to write a vector. Please have a read. It goes through everything I have said here and then dives into some more detail.

Resource Management Allocation
Resource Management Copy Swap
Resize
Simple Optimizations
The Other Stuff
ReSize Maths

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the feeback! \$\endgroup\$
    – Person Guy
    Jan 19, 2020 at 23:14
  • \$\begingroup\$ "But you need to add a special header." Not according to the C++ standard. MSVC still requires <ciso646> (non-conforming) by default, though, IIRC. \$\endgroup\$
    – L. F.
    Jan 20, 2020 at 11:37
2
\$\begingroup\$

Since you're using malloc, realloc, and free for memory management, your class can only be instantiated with POD classes. Any class with a constructor, destructor, or copy assignment operator may not work with your myVector class because these special functions will not be called.

The copy constructor is wrong. Since it uses copy assignment, and the copy assignment operator assumes that this is a valid object, you will try to free a pointer (free(m_Buffer)) that has not been initialized. The same applies to the other constructors that use assignment to initialize the object.

In addition, your copy assignment operator does not handle assignment to self (a = a;). Although rare, if it happens to occur you will free memory then try to read from it.

pop functions typically remove the last element. Specifying a number to remove is atypical. Calling that parameter index is potentially confusing. Do you pass the index of the one element to remove? Is the index the last element to keep, or the last one to remove? You're using it as a count of elements to remove.

Specifying the inline keyword for used and size is redundant. Since the function definitions are supplied, they are implicitly inline.

reserve has a return 1; but the return type is a bool. While that 1 will be converted to a bool value of true, it would be cleaner to specify return true; directly. And what does the return value mean? There's no documentation for any of your functions.

Resizing

You are nearly always resizing the array, both when you add something and when you remove it via pop. The only time this doesn't happen is if you reserve some memory first then add to it via push. If you remove an element you throw out the extra memory and resize down to the minimum required.

changeSize should, generally, not be called when removing elements. When adding elements, and you need to add more storage space, you should base the new space on the existing size. Doubling is very common, although I have seem implementations that use a 1.5 multiplier.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.