Building a Vector class in Arduino

Question

I'm struggling with this issue that I can seem to get around of. When defining a vector class, I'm seeming to get some issues when deleting the allocated pointer.

Oddly enough, this only happens after I "read" the memory. What I mean by this is that if I push back a series of values to the vector, they seem to stay there. But once I read the values, the data pointer seems to become invalid of some sort so I crash when trying to deallocate it.

Code:

#ifndef VECTOR_H
#define VECTOR_H

#include <string.h>     /* memcpy */

#define min(a,b) (a < b) ? a : b

template <typename T>
class vector {
public:
    vector() : __capacity(0), __count(0), __data(0) {} //empty constructor
    vector(T obj, int count = 1) {

        if (this->__data) { // free data ptr if used
            delete this->__data;
        }

        this->__data = new T[count];
        this->__count = count;
        this->__capacity = count;

        for (int i = 0; i < count; i++) //populate array with given object
            this->__data[i] = obj;

    }

    ~vector() {

        if (this->__data) { // free data ptr if used
            delete [] this->__data;
        }

        this->__count = this->__capacity = 0;
    }

    T const & operator[] (unsigned int idx) const {
        if (idx < this->__count) {
            return this->__data[idx];
        }
        else {
            // throw exception or handle error to be implemented
        }
    }

    T& operator[] (unsigned int idx) {
        if (idx < this->__count) {
            return this->__data[idx];
        }
        else {
            // throw exception or handle error to be implemented
        }
    }

    void resize_to_fit() {
        resize(this->__count);
    }

    T& pop_back(){
        return this->__data[--this->__count];
    }

    void push_back(T obj) {

        if (this->__capacity == this->__count) {
            resize(this->__capacity + 1);
        }

        this->__data[this->__count++] = obj;
    }

    bool isempty() {
        return !this->__data ||
            !this->capacity ||
            !this->size;
    }

    void clear() {
        this->~vector();
    }

    T* data() {
        return this->__data;
    }

    int size() {
        return this->__count;
    }

    int capacity() {
        return this->__capacity;
    }
private:
    void resize(int capacity) {
        if (this->__data == nullptr) {
            this->__data = new T[capacity];

            this->__count = 0;
            this->__capacity = capacity;
        }
        else if (capacity != this->__capacity) { //else do nothing

            T* data = new T[capacity];

            this->__count = min(this->__count, capacity);
            this->__capacity = capacity;

            memcpy(data, this->__data, sizeof(T) * this->__count);

            delete this->__data; //program crashes here, but the pointer is already broken...
            this->__data = data;
        }
    }
protected:

        int __capacity;
        int __count;
        T* __data;



};
#endif//VECTOR_H

I was using this code in my Arduino, not sure if it helps

void print_vec(vector<int> v){
  Serial.println("Printing new vec!");
  for( int i = 0; i < v.size(); i++){
    Serial.println(v[i]);
  }
}

void setup() {
  // put your setup code here, to run once:

  Serial.begin(9600); // Open serial connection to report values to host

  while(!Serial); //Waiting for serial to open

  vector<int> i = vector<int>();

  i.push_back(10);
  i.push_back(2);
  print_vec(i); //prints 10 and 2, perfect so far
  i.push_back(3);

  while(true){
    print_vec(i); 
    i.pop_back();
    delay(2000);
  }
}

void loop() {
  // put your main code here, to run repeatedly:

}

This code outputs: Printing new vec! 10 2 Printing new vec! 0 2 3 Printing new vec! 0 2 Printing new vec! 0 (...)

What could be causing this? I'm stonewalled for a while now, any insight on how to solve this is appreciated. Thanks!

Answer 1

You had a lot of problems with your code so it's hard to know where to start. :)

I agree with what John Burger said.

I took your code onto my PC to save mucking around uploading it each time, and also so I could use valgrind on it. Certainly valgrind reported an error after you printed the vector. The reason for that is simple. You passed a copy of the class to print_vec which meant that the destructor got called when print_vec exited, thus deallocating the memory. You should have had a copy constructor. Without it the compiler makes a bitwise copy of the class, which means you now have two objects sharing the same allocated memory.

A quick and dirty fix is to call print_vec by reference:

void print_vec(vector<int> & v){

However that leaves the bug lurking around for the future.

I implemented the copy constructor in my example below, however calling print_vec by reference saves the class having to be copied, reducing the number of new/deletes you are doing, thereby possibly reducing memory fragmentation.

---

As John Burger said: do not call the destructor yourself! You can't do that. If you want to do the same thing in the destructor and the clear function, just get the destructor to call clear().

---

The use of leading double-underscores in variables is contrary to the C++ Standard. Don't do that. Use a trailing underscore if you want to indicate a member variable. Lose all the this-> references. They just clutter things up.

---

Since you allocate an array you should use delete [] - you did that in one place but not the other.

---

Why do this? It's an unnecessary assignment:

  vector<int> i = vector<int>();

Just do:

  vector<int> i;

If you are going to assign the class for some reason you should also implement an operator= or you will have the same problems as you had with the copy constructor. (See my example).

---

Here you are testing functions (capacity and size) without calling them:

bool isempty() {
    return !this->__data ||
        !this->capacity ||
        !this->size;
}

---

You can't really do this:

  T const & operator[] (unsigned int idx) const {
        if (idx < this->__count) {
            return this->__data[idx];
        }
        else {
            // throw exception or handle error to be implemented
        }
    }

If you take the "else" path then the function is returning no value (you get a compiler warning if you turn warnings on).

---

My reworked example, with my suggestions in it. It compiles without warnings or errors and runs without crashing (on a PC):

//      g++ -std=c++11 -g3 test.cpp -o test
// OR:  clang -std=c++11 -g3 -Wall test.cpp -lstdc++ -o test
//
// valgrind --leak-check=yes ./test

#include <stdio.h>      // printf
#include <string.h>     /* memcpy */

#define min(a,b) (a < b) ? a : b

template <typename T>
class vector {
public:
    //empty constructor
    vector() : capacity_(0), count_(0), data_(nullptr) {}

    // copy constructor
    vector (const vector & rhs) : capacity_(0), count_(0), data_(nullptr)
      {
      data_ = new T [rhs.capacity_];
      capacity_ = rhs.capacity_;
      count_ = rhs.count_;
      memcpy (data_, rhs.data_, sizeof (T) * count_);
      }  // end of copy constructor

    // operator=
    vector & operator= (const vector & rhs)
      {
      // gracefully handle self-assignment (eg. a = a;)
      if (this == &rhs )
        return *this;

      data_ = new T [rhs.capacity_];
      capacity_ = rhs.capacity_;
      count_ = rhs.count_;
      memcpy (data_, rhs.data_, sizeof (T) * count_);
      return *this;
      }  // end of operator=

    // destructor
    ~vector()
      {
        clear ();
      }  // end of destructor

    T const & operator[] (unsigned int idx) const {
       return data_[idx];
    }

    T& operator[] (unsigned int idx) {
       return data_[idx];
    }

    void resize_to_fit() {
        resize(count_);
    }

    T& pop_back(){
        return data_[--count_];
    }

    void push_back(T obj) 
        {
        if (capacity_ == count_) {
            resize(capacity_ + 1);
        }

        data_[count_++] = obj;
    }

    bool isempty() {
        return count_ == 0;
    }

    void clear() {
      delete [] data_;
      data_ = nullptr;
      count_ = capacity_ = 0;
    }

    T* data() {
        return data_;
    }

    int size() {
        return count_;
    }

    int capacity() {
        return capacity_;
    }
private:
    void resize(int capacity) {
        if (data_ == nullptr) {
            data_ = new T[capacity];
            count_ = 0;
            capacity_ = capacity;
        }
        else if (capacity > capacity_) { //else do nothing

            // allocate new memory
            T* data = new T[capacity];
            // count can't be higher than capacity
            count_ = min(count_, capacity);
            capacity_ = capacity;
            // copy data across to new pointer
            memcpy(data, data_, sizeof(T) * count_);
            // delete old pointer
            delete [] data_;
            // now remember the new pointer
            data_ = data;
        }
    }
protected:

        int capacity_;
        int count_;
        T* data_;
};



void print_vec(vector<int> v){
  printf("%s\n", "Printing new vec!");
  for( int i = 0; i < v.size(); i++){
    printf("%i\n", v[i]);
  }
}

int main() {

  vector<int> i;

  i.push_back(10);
  i.push_back(2);
  print_vec(i);
  i.push_back(3);

  vector<int> j;

  // test assignment
  j = i;
  print_vec(j);
  print_vec(i);


  while(i.size () > 0){
    print_vec(i);
    i.pop_back();
  }


}

Answer 2

In your second constructor you start with the following code:

if (this->__data) { // free data ptr if used
    delete this->__data;
} // if

This is deadly! You've not initialised __data, so it could hold any value under the Sun. And there is no way that it could possibly be a valid pointer to existing data - it's a brand-new uninitialized object. Returning this garbage pointer to the heap is simply asking for trouble.

Remove those lines - or even better, use an initialiser list like you did with the first constructor:

vector(T obj, int count = 1) :
       __data(new T[count]),
       __count(count),
       __capacity(count)
{
    for (int i = 0; i < count; i++) //populate array with given object
        __data[i] = obj;
} // vector(T, count)

Another problem: In your clear() member you wrote:

void clear() {
    this->~vector();
}

You should never, never, never directly call a destructor like this. The compiler can put all sorts of other code in the destructor code, since it "knows" that it's the only one that will ever call it. For example, some compilers pre-push a flag to say whether to delete the object from the heap after doing the destruction. You haven't done that, so the above can corrupt all sorts of things.

Instead, move the code that is in the destructor into clear(), and then simply call clear() from the destructor.

Another one, this one picked up by @Nick Gammon:

bool isempty() {
    return !this->__data ||
           !this->capacity ||
           !this->size;
}

This is testing whether the __data member is false, and whether the capacity and size functions have been defined. Don't worry: the latter two have been... you missed the prefix __...

[Also, stop it with the this-> everywhere. You've used a __ before all your member variables (which is itself against convention); you don't need to hammer home the fact that they are member variables: the compiler already knows.]

Answer 3

There is something I would like to add.
Others have already pointed out numerous errors in the code. And I could point many more, but that is not the point.
IMO, the biggest mistake is - implementing a Vector class for the Arduino!
Even if it works, it is just a bad idea. Keep in mind, that the Arduino has VERY limited amount of memory. Dynamic memory allocation in such a constrained space just sounds like a bad idea - you are wasting memory, you're fragmenting the heap and you gain almost nothing, except some coding convenience.
I have yet to see a case where one really needs dynamic memory allocation in an Arduino project. And even if you do, there are many other tools you can use (like stack-allocated temp buffers, arena allocators, pool allocators and whatnot). But again, probably the code and memory cost of these "generic" solutions will be unfeasible on the Arduino.
Most of the time it's fine to use vectors, maps and whatever you like on platforms like PC (I work as a PC games programmer, so I often encounter situations where extras like these are big "no-no", but for most applications it's fine).
But, on a "tight" platform like the Arduino, I think you should stay "close to the metal" and be in total control of what is going on (memory and CPU cycles wise). Ideally, you should only afford "luxuries" like these when you know what is going on "underneath" and you know you can get away with it. Which is rarely the case on "tight" platforms like the Arduino.