Skip to content

Instantly share code, notes, and snippets.

@tigercosmos
Created June 22, 2022 14:06
Show Gist options
  • Save tigercosmos/4d939e90a350071424567b8ed4d9a378 to your computer and use it in GitHub Desktop.
Save tigercosmos/4d939e90a350071424567b8ed4d9a378 to your computer and use it in GitHub Desktop.
Small Vector Implementation
#include <array>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <iostream>
#include <initializer_list>
template <typename T, size_t N = 10>
class SmallVec
{
public:
using value_type = T;
using iterator = T *;
using const_iterator = T *const;
SmallVec() = default;
explicit SmallVec(size_t size) : m_size(size)
{
if (size > N)
{
m_capacity = m_size;
m_head = new T[m_capacity];
}
else
{
m_capacity = N;
m_head = m_data.data();
}
}
SmallVec(SmallVec const &other) : m_size(other.m_size)
{
if (other.m_head == other.m_data.data())
{
m_capacity = N;
m_head = m_data.data();
}
else
{
m_capacity = m_size;
m_head = new T[m_capacity];
}
std::copy_n(other.m_head, m_size, m_head);
}
SmallVec(SmallVec &&other) noexcept : m_size(other.m_size)
{
if (m_head == other.m_data.data())
{
m_capacity = other.m_capacity;
m_head = m_data.data();
std::copy_n(other.m_head, m_size, m_head);
}
else
{
m_capacity = m_size;
m_head = other.m_head;
other.m_capacity = N;
other.m_size = 0;
other.m_head = other.m_data.data();
}
std::copy_n(other.m_head, m_size, m_head);
}
SmallVec(std::initializer_list<T> init_list)
{
m_size = init_list.size();
if (m_size > N)
{
m_capacity = m_size;
m_head = new T[m_capacity];
}
else
{
m_capacity = N;
m_head = m_data.data();
}
std::copy_n(init_list.begin(), m_size, m_head);
}
SmallVec &operator=(SmallVec const &other)
{
if (this == &other)
return *this;
if (other.m_head == other.m_data.data())
{
if (m_head != m_data.data())
{
delete[] m_head;
m_head = m_data.data();
}
m_capacity = N;
m_size = other.m_size;
}
else
{
if (m_capacity < other.m_size)
{
delete[] m_head;
m_head = nullptr;
}
if (m_head == nullptr || m_head == m_data.data())
{
m_capacity = other.m_size;
m_head = new T[m_capacity];
}
m_size = other.m_size;
}
std::copy_n(other.m_head, m_size, m_head);
return *this;
}
SmallVec &operator=(SmallVec &&other) noexcept
{
if (this == &other)
return *this;
if (other.m_head == other.m_data.data())
{
if (m_head != m_data.data())
{
delete[] m_head;
m_head = m_data.data();
}
m_capacity = N;
m_size = other.m_size;
std::copy_n(other.m_head, m_size, m_head);
}
else
{
m_head = other.m_head;
m_capacity = other.m_capacity;
m_size = other.m_size;
other.m_head = other.m_data.data();
other.m_capacity = N;
other.size = 0;
}
return *this;
}
void push_back(T const &value)
{
if (m_capacity == m_size)
{
m_capacity *= 2;
T *tmp = new T[m_capacity];
std::copy_n(m_head, m_size, tmp);
if (m_head != m_data.data())
{
delete[] m_head;
}
m_head = tmp;
}
m_head[m_size++] = value;
}
void pop_back()
{
if (m_size == 0)
{
throw std::runtime_error("small vector underflow");
}
back().~T();
m_size--;
}
T const &operator[](size_t it) const { return m_head[it]; }
T &operator[](size_t it) { return m_head[it]; }
size_t size() noexcept { return m_size; }
size_t capacity() noexcept { return m_capacity; }
iterator begin() noexcept { return m_head; }
iterator end() noexcept { return m_head + m_size; }
const_iterator begin() const noexcept { return m_head; }
const_iterator end() const noexcept { return m_head + m_size; }
T const &back() const { return m_head[m_size - 1]; }
T &back() { return m_head[m_size - 1]; }
friend std::ostream &operator<<(std::ostream &os, const SmallVec &sv)
{
os << '[';
for (auto v : sv)
{
os << v << ' ';
}
os << ']';
return os;
}
~SmallVec()
{
if (m_head != m_data.data() && m_head != nullptr)
{
delete[] m_head;
}
}
private:
T *m_head = nullptr;
size_t m_size = 0;
size_t m_capacity = N;
std::array<T, N> m_data;
};
int main()
{
// constructor, stack
{
SmallVec<int> sv1;
SmallVec<int> sv2(sv1);
SmallVec<int> sv3(std::move(sv1));
SmallVec<int> sv4 = sv3;
SmallVec<int> sv5 = std::move(sv4);
}
// constructor, heap
{
SmallVec<int> sv1(20);
SmallVec<int> sv2(sv1);
SmallVec<int> sv3(std::move(sv1));
SmallVec<int> sv4 = sv3;
SmallVec<int> sv5 = std::move(sv4);
}
// push_back
{
SmallVec<int> sv1(3);
std::cout << sv1 << std::endl;
// [X, X, X], where X are arbitrary numbers
for (int i = 0; i < 11; i++)
{
sv1.push_back(1);
}
std::cout << sv1 << std::endl;
// [X X X 1 1 1 1 1 1 1 1 1 1 ]
}
// pop_back
{
SmallVec<int> sv1(20);
std::cout << "size: " << sv1.size() << ", capacity: " << sv1.capacity() << std::endl;
// size: 20, capacity: 20
while (sv1.size())
{
sv1.pop_back();
}
std::cout << "size: " << sv1.size() << ", capacity: " << sv1.capacity() << std::endl;
// size: 0, capacity: 20
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment