My vector works sometimes and othertimes it doesn't

Question

I'm trying to make my own vector, but i've got the following problem: When I push_back 100 times there's no problem. When I push_back 1000 the program does not work

#include <iostream>
#include <stdlib.h>
#include <conio.h>

struct Exception {
    static const char* out_of_range;
};

const char* Exception::out_of_range = "[Error]: Out of range";

template < typename T >
struct vector {
    typedef T myType;
public:
    vector() { 
        m_vector = (myType*) malloc ( sizeof( myType ) );
        m_position = 0; 
    }
    template < typename ... Ts >
    vector(myType head, Ts ... tail) {
        m_position = 0;
        m_vector = (myType*) malloc( (sizeof ...( tail ) + 1) * sizeof( myType ) );
        this->push_back(head);
        (this->push_back(tail),...);
    }
    ~vector() { 
        free(m_vector); 
        m_vector = NULL;
    }
    void push_back( myType value ) {
        m_vector[ m_position ] = value;
        ++m_position;
        m_vector = (myType*) realloc(m_vector, m_position * sizeof(myType));
    }
    void pop_back() {
        --m_position;
        m_vector = (myType*)realloc( m_vector, m_position * sizeof (myType) );
    }

    myType at( size_t pos ) {
        try {
            if (pos < m_position) 
                return m_vector[ pos ];
            else throw Exception::out_of_range;
        } catch (const char* e) {
            printf("%s", e);
            return (myType){};
        }
    }

    inline myType& front() { return *m_vector; }
    inline myType& back() { return *(m_vector + size() -1); }
    inline myType* data() { return m_vector; }

    inline myType* begin() { return m_vector; }
    inline myType* end() { return (m_vector + size()); }

    inline myType operator[](size_t pos) { return m_vector[ pos ]; }
    inline size_t size() { return m_position; }
    inline bool empty () { return (begin() == end()? true:false); }

private:
    myType* m_vector;
    size_t m_position;
};

Here is my main that use push_back by 100 times:

int main() {
    vector<int> v;
    for(int i = 0; i < 100; ++i) v.push_back(i);
    for(int i = 0; i < 100; ++i) std::cout << v[i];
}

And here the hunted code ahah:

int main() {
    vector<int> v;
    for(int i = 0; i < 1000; ++i) v.push_back(i);
    for(int i = 0; i < 1000; ++i) std::cout << v[i];
}

With "doesn't work" I'm trying to say that when I have 100 values inserted by push_back the program show me all the values from 0 to 99... but when I've got 1000 values (I don't know why) the program show only a black screen and nothing more

Answer 1

Consider the first call of

void push_back(myType value) {
    m_vector[m_position] = value; // Store into 0
    ++m_position; // set `m_position` to 1
    m_vector = (myType*)realloc(m_vector, m_position * sizeof(myType)); // Allocate more space.
}

How much more space is allocated on that last line? m_position * sizeof(myType). This resolves to 1 * sizeof(myType). Enough space for 1 myType. In other words the same amount of space the program already had. This is not useful.

Let's look at the next push_back

void push_back(myType value) {
    m_vector[m_position] = value; // Store into 1. There is no 1. Program now broken
    ++m_position; // set `m_position` to 2
    m_vector = (myType*)realloc(m_vector, m_position * sizeof(myType)); // Allocate more space.
}

The next push_back writes into invalid storage. Program now officially broken and no further point debugging.

How do we fix this?

Let's ignore the fact that malloc and family don't handle complex data structures and vector does not observe the Rules of Three and Five. Those are best handled in other questions. How do we fix this with realloc?

m_vector = (myType*) realloc(m_vector, (m_position +1) * sizeof(myType));

smooths over the immediate rough spot. But this is inefficient as hell. Every addition triggers a realloc. This really, really hurts performance. Aggregate O(1) goes right out the window replaced by O(n), copy every time, plus a potentially very expensive memory allocation.¹

Worse, what happens when you remove an item? You lose track of how much was in the vector and may find yourself reallocing smaller buffers. Yuck.

To do this right, first add a m_capacity member to track how much data can be stored so that we don't have to reallocate if the amount needed is less than the amount required.

Then we test for amount of space and possibly reallocate before trying to store.

void push_back( myType value ) {
    if (m_position >= m_capacity)
    { // need to reallocate
        m_capacity *= 2;
        myType * temp = (myType*) realloc(m_vector, m_capacity *sizeof(myType));
        // ask for more than is needed. Reduce number of reallocations needed
        // do not overwrite m_vector. realloc can fail to allocate and then where are you?
        if (temp != NULL) 
        { 
            m_vector = temp;
        }
        else
        {
             // handle error. Probably throw exception. Definitely exit function 
             // before trying to add new element
        }
    }
    m_vector[ m_position ] = value; // now guarantied to have space.
    ++m_position;
}

---

¹This isn't strictly true. One of the things you'll find is that memory provided often isn't as granular as what you asked for. When the program asks for X bytes, it might get a convenient block of free memory larger than X bytes. You ever noticed that sometimes you can run off the end of a buffer and the program doesn't notice and immediately crash? This extra space is one of the reasons. Quite often realloc can take advantage of this and keep using the same allocation over and over, allowing the program to legally see more of it. You can't count on this, though.

Answer 2

I assume the idea behind your code is that m_vector should always be able to hold one more value than it currently does. Your push_back funtion is wrong then, it should realloc for m_position + 1.