4
\$\begingroup\$

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());
}
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Try making a “barking” class; a class that does nothing but print a message for every special operation (copy/move/default construct, destruct, copy/move assign). Now try creating a program whose entire body is just auto main() -> int { Deque<barker> d; }. Observe the output. Compare that to what you get with auto main() -> int { std::deque<barker> d; }. \$\endgroup\$
    – indi
    Jan 15 at 21:55
  • \$\begingroup\$ @indi Thanks for pointing out, the object is created and destroyed BLOCK_SIZE number of times due to the line back_blocks.push_back(new T[BLOCK_SIZE]). The reason for building this block up front is to simplify some of the logic in emplace_back, because including the first emplacement, I can assume that an emplace_back operation has enough space to emplace an element, then you check and see if you need to expand after. \$\endgroup\$
    – jdav22
    Jan 15 at 22:28
  • 1
    \$\begingroup\$ (Properly aligned) blocks of std::byte (not char) is the correct answer (and reinterpret_cast is not; what you want is std::construct_at()). But the most important takeaway here is to use a barking type for testing containers. There are several other bugs lurking, like in the emplace functions, where you construct an object over an existing one without destroying the old one first. You should use a barking-like type for testing (it doesn’t need to print, it could just count or log operations, then you check the logs in tests). \$\endgroup\$
    – indi
    Jan 16 at 11:04
  • 2
    \$\begingroup\$ You don’t need reinterpret_cast; in the cppreference example, you could static_cast the storage address to void*, then static_cast it again to S*. That would be silly, though; reinterpret_cast is fine there. The reason reinterpret_cast is not needed in real-world container implementations is because you’d normally be using allocators, not raw std::byte allocations, and allocator_traits<Allocator>::allocate() already returns a T*, so there’s no casting necessary. Without allocators, using raw byte arrays as storage, you do need to cast. \$\endgroup\$
    – indi
    Jan 16 at 20:58
  • 1
    \$\begingroup\$ Also, correct: so long as there is no existing object in the place you’re constructing a new one—either because there never was one, or there was one but it’s been destroyed—then you’re safe. \$\endgroup\$
    – indi
    Jan 16 at 20:58

2 Answers 2

4
\$\begingroup\$

It leaks memory when used as a queue

The name "deque" stands for double-ended queue. A typical way to use a deque is when you need a queue where you push only into one end and pop only from the other end. Often, the total number of elements in a deque has a small upper bound. However, in this scenario, your Deque will allocate more and more memory the longer it is used, as it never deletes blocks until the whole Deque object is destructed.

Use more helper classes

It's already great that you used std::vector for front_blocks and back_blocks, that saves you a lot of trouble having to manage memory for those. But you can create some more classes yourself to simplify Deque itself. For example, you could create a class Block that represents one block, with helper functions to construct, access and destroy its elements.

Use std::unique_ptr to avoid managing memory for the blocks.

Also consider creating a class Index that groups a block_idx and idx_in_block together. You can then for example add operator++() and operator--() member functions to make modying an index as simple as possible.

Use std::size_t for counts and indices

You use int for counts and indices, but an int might not be large enough to handle all the elements you could store in memory. Instead, use std::size_t. Of course, if you really need to handle negative indices, you need something else, like std::ptrdiff_t.

Also, consider that a single std::size_t is large enough to be able to index any amount of elements that could ever be stored in memory. So instead of having a "block index" and "index in block", you can have a single index where the low bits are the index inside the block, and the high bits the block index.

Reduce the size of an Iterator

Your Iterator stores two pointers and three integers. That's quite a lot. You can simplify this by storing just a pointer to the Deque object itself, and you can store the index in a single integer; I've already mentioned that above, and it seems deque_idx already fulfills that role.

The reduced size will help a lot in case a user wants to store many iterators somewhere. And while it looks less efficient to dereference a Deque* to get a pointer to front_blocks and/or back_blocks, the code will be inlined anyway, and the compiler will very likely be able to optimize that away.

Make BLOCK_SIZE a static member

Instead of having a global constant BLOCK_SIZE, make it a static constexpr member variable. This way, you can make it have a different value depending on sizeof(T). Consider for example having a Deque<char>: allocating only 16 bytes for a block is very inefficient, while for Deque<HugeClass> you might even want to have a BLOCK_SIZE of 1.

Missing const versions of front() and back()

You added const iterators and several other const member functions, but you forgot to add const versions of front() and back().

Unnecessary swap()

Your swap() just calls swap() on all member variables. In that case, you don't need to implement swap() at all.

Don't declare Iterator in the global namespace

While the name Deque is quite unique, what if you also want to implement your own Vector, Array and Map? These would all need their own iterator types, so you will then run into an issue if you have the genericly named Iterator in the global namespace. There are several solutions:

  • Rename Iterator to DequeIterator.
  • Create a unique namespace where you can put this Iterator in.
  • Move Iterator into class Deque.
\$\endgroup\$
2
  • \$\begingroup\$ Thanks @G. Sliepen for the thoughtful review! Only thing I was a bit confused about is the memory leak comment. It's true I don't free blocks until the data structure is destroyed, but isn't this true of STL data structures in general? For example, I thought std::vector doesn't free up memory when you call pop_back(), it only destroys the element you popped, unless you call shrink_to_fit (which might not even shrink the vector as requested). Is std::deque different and it cleans up after itself in some way before deletion? \$\endgroup\$
    – jdav22
    Jan 16 at 19:30
  • 1
    \$\begingroup\$ Yes, std::deque is different. To quote cppreference.com: "The storage of a deque is automatically expanded and contracted as needed." This description is different from that of std::vector, which mentions it is only "being expanded as needed." \$\endgroup\$
    – G. Sliepen
    Jan 16 at 20:06
3
\$\begingroup\$

A double-ended queue (hereon simply deque) contains a single run of elements with consecutive indices.

None of those indices should be treated as in any way special, which means the indices must use modulo-arithmetic (std::size_t fits), and the blocks used should for simplicity and efficiency hold an exact power of 2 elements.

Using two std::vectors to hold block-pointers certainly doesn't fit the purpose, especially as you fix their start to index zero.

You have three kinds of memory-leaks:

  1. Your blocks consist of fully constructed elements, which leaks resources. Let's not even talk about the semantics, and whether the element-type supports default-construction.
  2. Your blocks are allocated around index zero, however far away your sequence of valid indices is. Fairly consistently wandering further off in either direction is to be expected, as one end is generally preferred for insertion, and one for removing.
  3. You simply don't free blocks.

Iterators should be small, cheap and regular:

Just about all code, be it standard algorithms or whatever, expects that.

Currently, they have two references and three integers, which are involved in some convoluted dance, thus they are neither.
It should be easy to redesign to just a single pointer (to the container, or leaving out one indirection trading stability for efficiency, to the array containing the block-pointers) and one integer (index for the former, localized index for the latter).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.