I have implemented a rudimentary vector using the code from the Weiss C++ textbook on data structures (see below). when i time it with 100,000 push_backs it takes 0.001 seconds.
when i do the exact same experiment using the stl::vector, it takes 0.008 seconds (roughly 8x slower). does anyone know why this is? thanks
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
template<typename Object>
class Vector {
public:
// normal constructor
explicit Vector(int initialSize = 0) :
theSize{ initialSize }, theCapacity{ initialSize + SPARE_CAPACITY },
objects{ new Object[theCapacity] }
{}
// copy constructor
Vector(const Vector& rhs) :
theSize{ rhs.theSize }, theCapacity{ rhs.theCapacity }, objects{ nullptr }
{
objects = new Object[theCapacity];
for (int k = 0; k < theSize; ++k)
objects[k] = rhs.objects[k];
}
// copy assignment operator
Vector& operator=(const Vector& rhs)
{
Vector copy = rhs;
std::swap(*this, copy);
return *this;
}
// destructor
~Vector()
{
delete[] objects;
}
// move constructor
Vector(Vector&& rhs) :
theSize{ rhs.theSize }, theCapacity{ rhs.theCapacity }, objects{ rhs.objects }
{
rhs.objects = nullptr;
rhs.theSize = 0;
rhs.theCapacity = 0;
}
// move assignment operator
Vector& operator=(Vector&& rhs)
{
std::swap(theSize, rhs.theSize);
std::swap(theCapacity, rhs.theCapacity);
std::swap(objects, rhs.objects);
return *this;
}
void resize(int newSize)
{
if (newSize > theCapacity)
reserve(newSize * 2); // talk about amortized time (python book)
theSize = newSize;
}
void reserve(int newCapacity)
{
if (newCapacity < theSize)
return;
Object* newArray = new Object[newCapacity];
for (int k = 0; k < theSize; ++k)
newArray[k] = std::move(objects[k]);
theCapacity = newCapacity;
std::swap(objects, newArray);
delete[] newArray;
}
Object& operator[](int index)
{
return objects[index];
}
const Object& operator[](int index)const
{
return objects[index];
}
bool empty() const
{
return size() == 0;
}
int size() const
{
return theSize;
}
int capacity() const
{
return theCapacity;
}
void push_back(const Object& x)
{
if (theSize == theCapacity)
reserve(2 * theCapacity + 1);
objects[theSize++] = x;
}
void push_back(Object&& x)
{
if (theSize == theCapacity)
reserve(2 * theCapacity + 1);
objects[theSize++] = std::move(x);
}
void pop_back()
{
--theSize;
}
const Object& back() const
{
return objects[theSize - 1];
}
// iterator
typedef Object* iterator;
typedef const Object* const_iterator;
iterator begin()
{
return &objects[0];
}
const_iterator begin() const
{
return &objects[0];
}
iterator end()
{
return &objects[size()];
}
const_iterator end() const
{
return &objects[size()];
}
static const int SPARE_CAPACITY = 16;
private:
int theSize;
int theCapacity;
Object* objects;
};
int main()
{
std::clock_t start;
start = std::clock();
std::vector<int> vec2{ 0 };
for (int i = 0; i < 100000; i++)
vec2.push_back(i);
double duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
std::cout << "printf: " << duration << '\n';
start = std::clock();
Vector<int> vec{ 0 };
for (int i = 0; i < 100000; i++)
vec.push_back(i);
duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
std::cout << "printf: " << duration << '\n';
}
Your vector implementation and std::vector
are fundamentally different.
Your vector default-constructs all values in the vector, up to reserve capacity, and push_back()
merely replaces the next reserved value with the new value, using the assignment operator.
std::vector
is fundamentally different,, and does not default-construct "non-existent" values in the vector, but constructs them "for real-sies". std::vector::push_back
constructs the new value in the vector, your push_back
assigns it.
Depending on the object in the container, its assignment operator and its constructor may have completely different logic, and comparative benchmarks are meaningless.