Piero Marini Piero Marini - 1 month ago 10
C++ Question

C++ Vector implementation allocating new objects

Im almost done with the implementation of a std::vector type of vector (hopefully) but Im having a little bug in the code and I cant seem to find where. Basically when I build Vector and use push_back, the vector automatically allocates new memory for more elements (specifically twice the size of the vector) but when doing so, the "extra space" is initialized to 0's and I dont know why.

Here is my code:

Vector.h



#include <memory>
#include <cstddef>

template <class T>
class Vec{
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef size_t size_type;
typedef T value_type;

Vec(){create();}
Vec(size_type n, const T& val = T()) {create(n, val);}

~Vec() {uncreate();}

//copy constructor
Vec(const Vec& v) {create(v.begin(), v.end());}
//assignment operator
Vec& operator=(const Vec&);

size_type size() const {return limit - data;}

//index operators
T& operator[](size_type i) {return data[i];}
const T& operator[](size_type i) const {return data[i];}

iterator begin() {return data;}
const_iterator begin() const {return data;}

iterator end() {return limit;}
const_iterator end() const {return limit;}

void push_back(const T&);


private:
iterator data; //1st element
iterator avail; //one past last constructed element
iterator limit; //one past last available element

//Memory management
std::allocator<T> alloc;

void create();
void create(size_type, const T&);
void create(const_iterator, const_iterator);

void uncreate();

void grow();
void unchecked_append(const T&);

};

template <class T>
void Vec<T>::push_back(const T& val){
if(avail == limit)
grow();
unchecked_append(val);
}

template <class T>
Vec<T>& Vec<T>::operator=(const Vec& rhs){
//self-assign
if(&rhs != this){
uncreate;
create(rhs.begin(), rhs.end());
}
return *this;
}

// Empty Vector, pointers to 0
template <class T> void Vec<T>::create(){
data = avail = limit = 0;
}

// Allocate memory for (size)
template <class T> void Vec<T>::create(size_type n, const T& val){
data = alloc.allocate(n); // returns pointer to first element
limit = avail = data +n;
std::uninitialized_fill(data, limit, val);
}

template <class T> void Vec<T>::create(const_iterator i, const_iterator j){
data = alloc.allocate(j-i);
limit = avail =std::uninitialized_copy(i, j, data);
}

template <class T> void Vec<T>::uncreate(){
if(data){
iterator it = avail;
while(it != data)
alloc.destroy(--it);

// Free space
alloc.deallocate(data, limit - data);
}
// Empty Vector
data = limit = avail = 0;
}

template <class T> void Vec<T>::grow(){
// Allocate twice the space we had
size_type new_size = std::max(2 * (limit - data), ptrdiff_t(1));

// Allocate new space and copy to new space
iterator new_data = alloc.allocate(new_size);
iterator new_avail = std::uninitialized_copy(data, avail, new_data);

// Return old space used
uncreate();

// Reset pointers to point to new space
data = new_data;
avail = new_avail;
limit = data + new_size;
}

template <class T> void Vec<T>::unchecked_append(const T& val){
alloc.construct(avail++, val);
}


And this is how I created the vector



main.cpp



#include "vector.h"
#incude <iostream>

using namespace std;

int main(){
Vec<int> v1;
v1.push_back(12);
v1.push_back(9);
v1.push_back(74);
v1.push_back(22);
Vec<int> v2 = v1;
v2.push_back(70); //After doing this the vector is (12, 9, 74, 22, 70, 0, 0, 0)
for(auto e: v2) cout << e << " ";
cout << endl;
}


Thanks for any help and also any feedback on the actual code is appreciated. :)

Answer

The problem is (i do not know if it is really problem)

template <class T> void Vec<T>::grow(){
    // Allocate twice the space we had
    size_type new_size = std::max(2 * (limit - data), ptrdiff_t(1));
....
....
}

No need to do any vector copy to reproduce your problem.

The problem can be seen even in first vector after inserting 5th elemnt

    v1.push_back(12);
    v1.push_back(9);
    v1.push_back(74);
    v1.push_back(22);
    v1.push_back(22);  //5th elemnt.

now printing the size;

cout<<v1.size()<<endl; - it says 8.

Even the std vector, after resize(), it is normal behavior to print zeros for the empty elements.

Look at this example: http://en.cppreference.com/w/cpp/container/vector/resize

if you do not want additional zeros, you have to tweak your ":new_size" calculation.