Took a shot at implementing std::deque in C++. I aimed for amortized O(1) push_front and push_back, O(1) pop_front and pop_back, and O(1) random access.
I do this by maintaining two vectors of pointers to fixed-size blocks of size 16, called front_blocks and back_blocks. Initially, push_front operations add to the blocks in front_blocks, and push_back operations add to the blocks in back_blocks. However, I also keep track of the front_block_idx and the back_block_idx, to denote which block the current front and current back are in.
These indices can either be 0 or positive, meaning that the current front/back is in back_blocks, or they can be negative, meaning the current front/back is in front_blocks. This was the cleanest way I could think of to get the desired complexities while keeping with the fixed-size block concept from the STL and keeping iterators valid when possible.
I did not aim for this to be a 100% copy of the STL, however, so please let me know if I am missing any crucial functionality, but I did not attempt to get the exact same typedefs as the STL, or all of the possible overloads for all the methods, etc.
The Deque class is below:
template <typename T>
class Deque {
public:
using iterator = Iterator<T, T>;
using const_iterator = Iterator<T, const T>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
constexpr Deque()
: front_blocks{}, back_blocks{}, front_block_idx{0},
front_idx_in_block{0}, back_block_idx{0},
back_idx_in_block{0}, m_size{0} {
back_blocks.push_back(new T[BLOCK_SIZE]);
}
~Deque() {
clear();
for (T* block : front_blocks) {
delete[] block;
}
for (T* block : back_blocks) {
delete[] block;
}
}
constexpr Deque(std::initializer_list<T> items) : Deque() {
assign(items.begin(), items.end());
}
constexpr Deque(const Deque& other) : Deque() {
// with this implementation, the underlying representation
// of values in the deque may be different, but the values
// themselves and the order remain the same
assign(other.cbegin(), other.cend());
}
constexpr Deque& operator=(const Deque& other) {
Deque temp{other};
swap(temp);
return *this;
}
constexpr Deque(Deque&& other) noexcept : Deque() {
swap(other);
}
constexpr Deque& operator=(Deque&& other) noexcept {
swap(other);
return *this;
}
constexpr bool operator==(const Deque& other) {
if (size() != other.size())
return false;
for (std::size_t idx = 0; idx < size(); ++idx) {
if ((*this)[idx] != other[idx])
return false;
}
return true;
}
T& front() {
return (*this)[0];
}
T& back() {
return (*this)[m_size - 1];
}
template <typename... Args>
constexpr void emplace_front(Args&&... args) {
decrement(front_idx_in_block, front_block_idx);
expand_front_if_needed();
T* block = get_block(front_block_idx, front_blocks, back_blocks);
new (std::addressof(block[front_idx_in_block]))
T(std::forward<Args>(args)...);
++m_size;
}
constexpr void push_front(const T& value) {
emplace_front(value);
}
constexpr void push_front(T&& value) {
emplace_front(std::move(value));
}
constexpr void pop_front() {
T* block = get_block(front_block_idx, front_blocks, back_blocks);
std::destroy_at(std::addressof(block[front_idx_in_block]));
increment(front_idx_in_block, front_block_idx);
m_size--;
}
template <typename... Args>
constexpr void emplace_back(Args&&... args) {
T* block = get_block(back_block_idx, front_blocks, back_blocks);
new (std::addressof(block[back_idx_in_block]))
T(std::forward<Args>(args)...);
increment(back_idx_in_block, back_block_idx);
expand_back_if_needed();
++m_size;
}
constexpr void push_back(const T& value) {
emplace_back(value);
}
constexpr void push_back(T&& value) {
emplace_back(std::move(value));
}
constexpr void pop_back() {
decrement(back_idx_in_block, back_block_idx);
T* block = get_block(back_block_idx, front_blocks, back_blocks);
std::destroy_at(std::addressof(block[back_idx_in_block]));
--m_size;
}
constexpr T& operator[](std::size_t idx) const {
auto [cur_block, idx_within_cur_block] = idx_to_block_position(idx);
return get_block(cur_block, front_blocks,
back_blocks)[idx_within_cur_block];
}
constexpr T& operator[](std::size_t idx) {
auto [cur_block, idx_within_cur_block] = idx_to_block_position(idx);
return get_block(cur_block, front_blocks,
back_blocks)[idx_within_cur_block];
}
constexpr std::size_t size() const noexcept {
return m_size;
}
constexpr bool empty() const noexcept {
return m_size == 0;
}
constexpr void swap(Deque& other) noexcept {
using std::swap;
swap(front_blocks, other.front_blocks);
swap(back_blocks, other.back_blocks);
swap(front_block_idx, other.front_block_idx);
swap(front_idx_in_block, other.front_idx_in_block);
swap(back_block_idx, other.back_block_idx);
swap(back_idx_in_block, other.back_idx_in_block);
swap(m_size, other.m_size);
}
/* Iterator support */
iterator begin() {
return iterator(front_blocks, back_blocks, front_block_idx,
front_idx_in_block, 0);
}
iterator end() {
return iterator(front_blocks, back_blocks, back_block_idx,
back_idx_in_block, size());
}
const_iterator cbegin() const {
return const_iterator(front_blocks, back_blocks, front_block_idx,
front_idx_in_block, 0);
}
const_iterator cend() const {
return const_iterator(front_blocks, back_blocks, back_block_idx,
back_idx_in_block, size());
}
reverse_iterator rbegin() {
return reverse_iterator(end());
}
reverse_iterator rend() {
return reverse_iterator(begin());
}
const_reverse_iterator crbegin() const {
return const_reverse_iterator(cend());
}
const_reverse_iterator crend() const {
return const_reverse_iterator(cbegin());
}
template <typename InputIt>
void assign(InputIt begin, InputIt end) {
for (auto&& it = begin; it != end; ++it) {
push_back(*it);
}
}
iterator insert(iterator pos, const T& value) {
return insert(pos, 1, value);
}
iterator insert(iterator pos, std::size_t count, const T& value) {
if (count == 0)
return pos;
int pos_idx = std::distance(begin(), pos);
int new_size = m_size + count;
// Ensure there is enough space for the new elements
while (idx_to_block_position(new_size - 1).first >=
back_blocks.size()) {
back_blocks.push_back(new T[BLOCK_SIZE]);
}
// Move existing elements to make space for the new elements
for (int i = int(m_size) - 1; i >= pos_idx; --i) {
move_deque_element(i, i + count);
}
// Construct new elements in place
for (std::size_t i = 0; i < count; ++i) {
new (std::addressof((*this)[pos_idx + i])) T(value);
}
m_size = new_size;
return iterator(front_blocks, back_blocks,
idx_to_block_position(pos_idx).first,
idx_to_block_position(pos_idx).second, pos_idx);
}
iterator erase(iterator pos) {
return erase(pos, 1);
}
iterator erase(iterator pos, int count) {
if (count == 0)
return pos;
int pos_idx = std::distance(begin(), pos);
int new_size = m_size - count;
// destroy elements being erased
for (int i = pos_idx; i < pos_idx + count; ++i) {
auto [block_idx, idx_in_block] = idx_to_block_position(i);
T* block = get_block(block_idx, front_blocks, back_blocks);
std::destroy_at(std::addressof(block[block_idx]));
}
// move elements back
for (int i = pos_idx + count; i < pos_idx + 2 * count; ++i) {
move_deque_element(i, i - count);
}
m_size = new_size;
return iterator(front_blocks, back_blocks,
idx_to_block_position(pos_idx).first,
idx_to_block_position(pos_idx).second, pos_idx);
}
void clear() noexcept {
for (auto&& elem : *this) {
elem.~T();
}
m_size = 0;
}
private:
std::vector<T*> front_blocks, back_blocks;
int front_block_idx, front_idx_in_block;
int back_block_idx, back_idx_in_block;
std::size_t m_size;
constexpr void expand_front_if_needed() {
if (get_front_block_vector_idx(front_block_idx) >=
front_blocks.size()) {
front_blocks.push_back(new T[BLOCK_SIZE]);
}
}
constexpr void expand_back_if_needed() {
if (back_block_idx >= back_blocks.size()) {
back_blocks.push_back(new T[BLOCK_SIZE]);
}
}
constexpr std::pair<int, int>
idx_to_block_position(std::size_t idx) const noexcept {
int num_blocks = idx / BLOCK_SIZE;
int cur_block = front_block_idx + num_blocks;
int offset = idx % BLOCK_SIZE;
int idx_within_cur_block = front_idx_in_block + offset;
if (idx_within_cur_block >= BLOCK_SIZE) {
cur_block += 1;
idx_within_cur_block %= BLOCK_SIZE;
}
return {cur_block, idx_within_cur_block};
}
void move_deque_element(int src_idx, int dest_idx) {
auto [src_block, src_block_idx] = idx_to_block_position(src_idx);
auto [dest_block, dest_block_idx] = idx_to_block_position(dest_idx);
T* src = get_block(src_block, front_blocks, back_blocks);
T* dest = get_block(dest_block, front_blocks, back_blocks);
new (std::addressof(dest[dest_block_idx]))
T(std::move(src[src_block_idx]));
std::destroy_at(std::addressof(src[src_block_idx]));
}
};
The Iterator class this uses:
template <typename T, typename ElementType>
class Iterator {
public:
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
Iterator(const std::vector<T*>& front_blocks,
const std::vector<T*>& back_blocks,
int block_idx,
int idx_within_block,
int deque_idx)
: front_blocks{front_blocks},
back_blocks{back_blocks}, block_idx{block_idx},
idx_within_block{idx_within_block}, deque_idx{deque_idx} {
}
ElementType& operator*() const {
return *current();
}
ElementType* operator->() const {
return current();
}
Iterator& operator++() {
increment(idx_within_block, block_idx);
return *this;
}
Iterator operator++(int) {
Iterator temp = *this;
++(*this);
return temp;
}
Iterator& operator--() {
decrement(idx_within_block, block_idx);
return *this;
}
Iterator operator--(int) {
Iterator temp = *this;
--(*this);
return temp;
}
Iterator& operator+=(difference_type n) {
deque_idx += n;
shift_indices(block_idx, idx_within_block, n);
return *this;
}
Iterator& operator-=(difference_type n) {
deque_idx -= n;
shift_indices(block_idx, idx_within_block, -n);
return *this;
}
Iterator operator+(difference_type n) const {
Iterator temp = *this;
return temp += n;
}
Iterator operator-(difference_type n) const {
Iterator temp = *this;
return temp -= n;
}
difference_type operator-(const Iterator& other) const {
return this->deque_idx - other.deque_idx;
}
bool operator==(const Iterator& other) const {
return front_blocks == other.front_blocks and
back_blocks == other.back_blocks and
block_idx == other.block_idx and
idx_within_block == other.idx_within_block;
}
bool operator!=(const Iterator& other) const {
return !(*this == other);
}
private:
const std::vector<T*>&front_blocks, &back_blocks;
int block_idx, idx_within_block, deque_idx;
ElementType* current() const {
return get_block(block_idx, front_blocks, back_blocks) +
idx_within_block;
}
};
Some utility functions/constants (along with the headers used for the whole class):
#include <algorithm>
#include <cstddef>
#include <exception>
#include <memory>
#include <stdexcept>
#include <utility>
static constexpr std::size_t BLOCK_SIZE = 16;
constexpr int get_front_block_vector_idx(int block_idx) {
if (block_idx >= 0) {
throw std::out_of_range("only works with negative values");
}
return abs(block_idx) - 1;
}
constexpr void increment(int& idx_in_block, int& block_idx) noexcept {
idx_in_block++;
if (idx_in_block == BLOCK_SIZE) {
idx_in_block = 0;
block_idx++;
}
}
constexpr void decrement(int& idx_in_block, int& block_idx) noexcept {
if (idx_in_block > 0) {
idx_in_block--;
} else {
idx_in_block = BLOCK_SIZE - 1;
block_idx -= 1;
}
}
template <typename T>
constexpr T* get_block(int block_idx,
const std::vector<T*>& front_blocks,
const std::vector<T*>& back_blocks) {
if (block_idx >= 0) {
return back_blocks[block_idx];
} else {
return front_blocks[get_front_block_vector_idx(block_idx)];
}
}
constexpr void shift_indices(int& block_idx, int& idx_within_block, int shift) {
// Calculate the total index relative to the start of the deque
int total_idx = block_idx * BLOCK_SIZE + idx_within_block + shift;
// Update block_idx and idx_within_block based on the new total index
block_idx = total_idx / BLOCK_SIZE;
idx_within_block = total_idx % BLOCK_SIZE;
// Handle negative indices, ensuring block_idx and idx_within_block are
// always valid
while (idx_within_block < 0) {
idx_within_block += BLOCK_SIZE;
block_idx--;
}
}
And finally some unit tests:
#define BOOST_TEST_MODULE DequeTest
#include <boost/test/included/unit_test.hpp>
#include <deque>
#include "Deque.h"
BOOST_AUTO_TEST_CASE(TestConstructors) {
Deque<int> dq1;
BOOST_CHECK(dq1.size() == 0);
Deque<int> dq2{1, 2, 3, 4, 5};
BOOST_CHECK(dq2.size() == 5);
BOOST_CHECK(dq2[0] == 1 && dq2[4] == 5);
Deque<int> dq3(dq2);
BOOST_CHECK(dq3.size() == dq2.size());
BOOST_CHECK(dq3[0] == dq2[0] && dq3[4] == dq2[4]);
Deque<int> dq4(std::move(dq2));
BOOST_CHECK(dq4.size() == 5);
BOOST_CHECK(dq2.size() == 0);
}
BOOST_AUTO_TEST_CASE(TestPushPop) {
Deque<int> dq;
dq.push_back(1);
dq.push_front(2);
BOOST_CHECK(dq.size() == 2);
BOOST_CHECK(dq[0] == 2 && dq[1] == 1);
dq.pop_back();
BOOST_CHECK(dq.size() == 1 && dq[0] == 2);
dq.pop_front();
BOOST_CHECK(dq.empty());
for (int i = 1; i <= 100; ++i) {
dq.push_front(i);
BOOST_CHECK(dq.size() == i);
}
for (int i = 99; i >= 0; --i) {
dq.pop_back();
BOOST_CHECK(dq.size() == i);
}
}
BOOST_AUTO_TEST_CASE(TestIterators) {
Deque<int> dq;
for (int i = 0; i < 100; ++i) {
dq.push_back(i);
}
Deque<int> dq2;
for (auto it = dq.begin(); it != dq.end(); ++it) {
dq2.push_back(*it);
}
BOOST_CHECK(dq == dq2);
Deque<int> rev;
for (auto it = dq.rbegin(); it != dq.rend(); ++it) {
rev.push_back(*it);
}
for (int i = 0, j = rev.size() - 1; i < j; i++, j--) {
swap(rev[i], rev[j]);
}
BOOST_CHECK(dq == rev);
}
BOOST_AUTO_TEST_CASE(TestBoundaryInsertionAndDeletion) {
Deque<int> dq;
dq.insert(dq.begin(), 1);
BOOST_CHECK(dq.size() == 1 && dq[0] == 1);
dq.insert(dq.end(), 2);
BOOST_CHECK(dq.size() == 2 && dq[1] == 2);
dq.erase(dq.begin());
BOOST_CHECK(dq.size() == 1 && dq[0] == 2);
dq.erase(dq.begin());
BOOST_CHECK(dq.empty());
}
BOOST_AUTO_TEST_CASE(TestLargeDataHandling) {
Deque<int> dq;
const std::size_t large_size = 100000;
for (std::size_t i = 0; i < large_size; ++i) {
dq.push_back(i);
}
BOOST_CHECK(dq.size() == large_size);
BOOST_CHECK(dq[large_size - 1] == large_size - 1);
for (std::size_t i = 0; i < large_size; ++i) {
dq.pop_front();
}
BOOST_CHECK(dq.empty());
}
BOOST_AUTO_TEST_CASE(TestConsistencyAfterMultipleOperations) {
Deque<int> dq;
for (int i = 0; i < 1000; ++i) {
dq.push_back(i);
dq.push_front(-i);
}
BOOST_CHECK(dq.size() == 2000);
for (int i = 0; i < 1000; ++i) {
BOOST_CHECK(dq[i] == -999 + i);
BOOST_CHECK(dq[1999 - i] == 999 - i);
}
for (int i = 0; i < 1000; ++i) {
dq.pop_back();
dq.pop_front();
}
BOOST_CHECK(dq.empty());
}
BOOST_AUTO_TEST_CASE(TestEmplacement) {
Deque<std::pair<int, std::string>> dq;
dq.emplace_back(1, "one");
BOOST_CHECK(dq.back().first == 1 && dq.back().second == "one");
dq.emplace_front(0, "zero");
BOOST_CHECK(dq.front().first == 0 && dq.front().second == "zero");
BOOST_CHECK(dq.size() == 2);
BOOST_CHECK(dq[0].first == 0 && dq[1].first == 1);
}
BOOST_AUTO_TEST_CASE(TestNonIntTypes) {
Deque<std::string> dq;
dq.push_back("Hello");
dq.push_back("World");
BOOST_CHECK(dq.size() == 2);
BOOST_CHECK(dq[0] == "Hello" && dq[1] == "World");
}
BOOST_AUTO_TEST_CASE(TestStringLargeDataHandling) {
Deque<std::string> dq;
const std::size_t large_size = 10000;
for (std::size_t i = 0; i < large_size; ++i) {
dq.push_back("String " + std::to_string(i));
}
BOOST_CHECK(dq.size() == large_size);
BOOST_CHECK(dq[large_size - 1] ==
"String " + std::to_string(large_size - 1));
for (std::size_t i = 0; i < large_size; ++i) {
dq.pop_front();
}
BOOST_CHECK(dq.empty());
}
