Skip to content

Instantly share code, notes, and snippets.

@loskutov
Last active August 15, 2018 15:40
Show Gist options
  • Save loskutov/8c10e34845c71db5177947a0d15ec55f to your computer and use it in GitHub Desktop.
Save loskutov/8c10e34845c71db5177947a0d15ec55f to your computer and use it in GitHub Desktop.
A simple C++ vector implementation for trivially copyable types, significantly outperforming std::vector
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <type_traits>
#include <stdlib.h>
#include <cmath>
#include <malloc.h>
template <class T, typename = typename std::enable_if<std::is_trivially_copyable<T>::value>::type>
class Vector
{
std::size_t capacity_, size_;
T *data_ = nullptr;
void ensureCapacity(std::size_t desiredCapacity)
{
if (desiredCapacity <= capacity_)
return;
capacity_ = std::max(capacity_ * 2, desiredCapacity);
T *newData = static_cast<T*>(reallocarray(data_, capacity_, sizeof(T)));
data_ = newData ?: throw std::bad_alloc();
}
public:
Vector(const Vector<T> &other) = delete;
Vector<T> operator=(const Vector<T> &other) = delete;
Vector(Vector<T> &&other)
{
std::swap(capacity_, other.capacity_);
std::swap(size_, other.size_);
std::swap(data_, other.data_);
}
Vector(std::size_t n = 0)
: capacity_{ std::max(size_t(1), n) } // default capacity is 1
, size_{ n }
, data_{ static_cast<T*>(malloc(sizeof(T) * capacity_)) ?: throw std::bad_alloc() }
{}
T *begin() const
{
return data_;
}
T *end() const
{
return data_ + size_;
}
void pushBack(T elem)
{
ensureCapacity(size_ + 1);
data_[size_++] = elem;
}
T popBack()
{
return data_[--size_];
}
T& operator[](size_t ind) const
{
return data_[ind];
}
T& at(size_t ind) const
{
return (ind < size_) ? data_[ind] : throw std::out_of_range("Vector::at");
}
size_t capacity() const
{
return capacity_;
}
~Vector() noexcept
{
free(data_);
}
};
int main() {
const int ITERATIONS = 10;
std::chrono::time_point<std::chrono::system_clock> start, end;
std::chrono::duration<double> elapsed_seconds;
std::cout << "Testing the STL version." << std::endl;
for (int i = 0; i < ITERATIONS; ++i) {
start = std::chrono::system_clock::now();
std::vector<int> v;
for (int j = 0; j < 1e8; ++j) {
v.push_back(228);
v.push_back(239);
v.push_back(1337);
v.push_back(1488);
}
end = std::chrono::system_clock::now();
elapsed_seconds += end - start;
}
std::cout << "Total time elapsed for " << ITERATIONS << " iterations: " << elapsed_seconds.count() << std::endl;
elapsed_seconds = {};
std::cout << "Testing the innovative version." << std::endl;
for (int i = 0; i < ITERATIONS; ++i) {
start = std::chrono::system_clock::now();
Vector<int> v;
for (int j = 0; j < 1e8; ++j) {
v.pushBack(228);
v.pushBack(239);
v.pushBack(1337);
v.pushBack(1488);
}
end = std::chrono::system_clock::now();
elapsed_seconds += end - start;
}
std::cout << "Total time elapsed for " << ITERATIONS << " iterations: " << elapsed_seconds.count() << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment