STL-style deque class

Question

I decided to write an STL-style class as an exercise. I followed a tutorial of sorts that I found online, but I also made some modifications. I'd like to hear any criticisms you folks might have. Be harsh; I can take it.

#ifndef CIRCULARDEQUE_HPP_
#define CIRCULARDEQUE_HPP_

#include <iterator>
#include <stdexcept>
#include <cassert>

template<typename T, typename T_nonconst,
        typename elem_type = typename T::value_type>
class circular_deque_iterator {
public:
    typedef circular_deque_iterator<T, T_nonconst, elem_type> self_type;
    typedef T deque_type;
    typedef std::random_access_iterator_tag iterator_category;
    typedef typename deque_type::value_type value_type;
    typedef typename deque_type::size_type size_type;
    typedef typename deque_type::pointer pointer;
    typedef typename deque_type::const_pointer const_pointer;
    typedef typename deque_type::reference reference;
    typedef typename deque_type::const_reference const_reference;
    typedef typename deque_type::difference_type difference_type;

    circular_deque_iterator(deque_type* b, size_t start_pos) :
            buf_(b), pos_(start_pos) {
    }

    // Converting a non-const iterator to a const iterator
    circular_deque_iterator(
            const circular_deque_iterator<T_nonconst, T_nonconst,
                    typename T_nonconst::value_type> &other) :
            buf_(other.buf_), pos_(other.pos_) {
    }

    friend class circular_deque_iterator<const T, T, const elem_type> ;

    elem_type& operator*() {
        return (*buf_)[pos_];
    }

    elem_type* operator->() {
        return &(operator*());
    }
    //prefix
    self_type& operator++() {
        ++pos_;
        return *this;
    }
    //prefix
    self_type& operator--() {
        --pos_;
        return *this;
    }

    self_type operator++(int) {
        self_type tmp(*this);
        ++(*this);
        return tmp;
    }

    self_type operator--(int) {
        self_type tmp(*this);
        --(*this);
        return tmp;
    }

    self_type& operator+=(difference_type n) {
        pos_ += n;
        return *this;
    }

    self_type& operator-=(difference_type n) {
        pos_ -= n;
        return *this;
    }

    difference_type operator-(const self_type &c) const {
        return pos_ - c.pos_;
    }

    self_type operator-(difference_type n) const {
        self_type tmp(*this);
        tmp.pos_ -= n;
        return tmp;
    }

    difference_type operator+(const self_type &c) const {
        return pos_ + c.pos_;
    }

    self_type operator+(difference_type n) const {
        self_type tmp(*this);
        tmp.pos_ += n;
        return tmp;
    }

    bool operator==(const self_type &other) const {
        return mask(pos_) == mask(other.pos_) && buf_ == other.buf_;
    }

    bool operator!=(const self_type &other) const {
        return mask(pos_) != mask(other.pos_) || buf_ != other.buf_;
    }

    bool operator>(const self_type &other) const {
        return pos_ > other.pos_;
    }

    bool operator>=(const self_type &other) const {
        return pos_ >= other.pos_;
    }

    bool operator<(const self_type &other) const {
        return pos_ < other.pos_;
    }

    bool operator<=(const self_type& other) const {
        return pos_ <= other.pos_;
    }

private:
    size_type mask(int val) const {
        return val & (buf_->capacity() - 1);
    }

    deque_type *buf_;
    int pos_;
};

template<typename T, typename Alloc = std::allocator<T>>
class circular_deque {
public:
    typedef circular_deque<T, Alloc> self_type;

    typedef Alloc allocator_type;

    typedef typename Alloc::value_type value_type;
    typedef typename Alloc::pointer pointer;
    typedef typename Alloc::const_pointer const_pointer;
    typedef typename Alloc::reference reference;
    typedef typename Alloc::const_reference const_reference;

    typedef typename Alloc::size_type size_type;
    typedef typename Alloc::difference_type difference_type;

    typedef circular_deque_iterator<self_type, self_type> iterator;
    typedef circular_deque_iterator<const self_type, self_type, const value_type> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    const static size_type default_capacity = 16;

    explicit circular_deque(size_type num_of_elmts_to_hold = default_capacity) :
            array_(alloc_.allocate(get_needed_capacity(num_of_elmts_to_hold))), capacity_(
                    num_of_elmts_to_hold), head_(0), tail_(0) {
        assert(invariants());
    }

    circular_deque(const circular_deque &other) :
            array_(alloc_.allocate(other.capacity_)), capacity_(
                    other.capacity_), head_(0), tail_(0) {
        try {
            assign_into(other.cbegin(), other.cend());
            assert(invariants());
        } catch (...) {
            destroy_all_elements();
            alloc_.deallocate(array_, capacity_);
            throw;
        }
    }

    template<class InputIterator>
    circular_deque(InputIterator from, InputIterator to) :
            array_(alloc_.allocate(0)), capacity_(0), head_(0), tail_(0) {
        circular_deque tmp;
        tmp.assign_into(from, to);
        swap(tmp);
        assert(invariants());
    }

    ~circular_deque() {
        destroy_all_elements();
        alloc_.deallocate(array_, capacity_);
    }

    circular_deque &operator=(const self_type &other) {
        circular_deque tmp(other);
        swap(tmp);
        assert(invariants());
        return *this;
    }

private:
    //TODO make this relative to actual int type
    static size_type get_needed_capacity(size_type num_of_elmts_to_hold) {
        size_type initialCapacity = num_of_elmts_to_hold;
        initialCapacity |= (initialCapacity >> 1);
        initialCapacity |= (initialCapacity >> 2);
        initialCapacity |= (initialCapacity >> 4);
        initialCapacity |= (initialCapacity >> 8);
        initialCapacity |= (initialCapacity >> 16);
        initialCapacity++;
        return initialCapacity;
    }

    void destroy_all_elements() {
        for (size_type n = 0; n < size(); ++n) {
            alloc_.destroy(array_ + mask(n));
        }
    }

    template<typename iter>
    void assign_into(iter from, iter to) {
        while (from != to) {
            push_back(*from);
            ++from;
        }
        assert(invariants());
    }
public:
    void clear() {
        for (size_type n = 0; n < size(); ++n) {
            alloc_.destroy(array_ + mask(n));
        }
        head_ = tail_ = 0;
    }

    void swap(circular_deque& other) {
        std::swap(array_, other.array_);
        std::swap(head_, other.head_);
        std::swap(tail_, other.tail_);
        std::swap(capacity_, other.capacity_);
        assert(invariants());
    }

    iterator begin() {
        return iterator(this, 0);
    }

    const_iterator cbegin() const {
        return const_iterator(this, 0);
    }

    iterator end() {
        return iterator(this, size());
    }

    const_iterator cend() const {
        return const_iterator(this, size());
    }

    reverse_iterator rbegin() {
        return reverse_iterator(end());
    }

    const_reverse_iterator rbegin() const {
        return const_reverse_iterator(cend());
    }

    reverse_iterator rend() {
        return reverse_iterator(begin());
    }

    const_reverse_iterator crend() const {
        return const_reverse_iterator(cbegin());
    }

    reference at(size_type n) {
        return at_checked(n);
    }

    const_reference at(size_type n) const {
        return at_checked(n);
    }

    reference operator[](size_type n) {
        return at_unchecked(n);
    }

    const_reference operator[](size_type n) const {
        return at_unchecked(n);
    }

private:
    size_type mask(int val) const {
        return val & (capacity() - 1);
    }

    reference at_unchecked(size_type index) const {
        return array_[mask(head_ + index)];
    }

    reference at_checked(size_type index) const {
        if (index >= size()) {
            throw std::out_of_range("out of range");
        }
        return at_unchecked(index);
    }

public:
    iterator erase(iterator i) {
        size_type idx = i - begin();
        circular_deque tmp(capacity());
        auto start = begin();
        while (start != end()) {
            if (start != i) {
                tmp.push_back(*start);
            }
            ++start;
        }
        swap(tmp);
        assert(invariants());
        return begin() + idx;
    }

    void push_front(const value_type& elem) {
        if (mask(head_ - 1) == tail_) {
            double_capacity();
        }
        head_ = mask(head_ - 1);
        array_[head_] = elem;

        assert(front() == elem);
        assert(invariants());
    }

    void push_back(const value_type& elem) {
        if (mask(tail_ + 1) == head_) {
            double_capacity();
        }
        array_[tail_] = elem;
        tail_ = mask(tail_ + 1);
        assert(back() == elem);
        assert(invariants());
    }

    void pop_front() {
        if (empty()) {
            return;
        }
        int destroy_pos = head_;
        head_ = mask(head_ + 1);
        alloc_.destroy(array_ + destroy_pos);
        assert(invariants());
    }

    void pop_back() {
        if (empty()) {
            return;
        }
        int destroy_pos = mask(tail_ - 1);
        tail_ = destroy_pos;
        alloc_.destroy(array_ + destroy_pos);
        assert(invariants());
    }

    reference front() {
        return array_[head_];
    }

    reference back() {
        return array_[mask(tail_ - 1)];
    }

    const_reference front() const {
        return array_[head_];
    }

    const_reference back() const {
        return array_[mask(tail_ - 1)];
    }

    size_type size() const {
        return mask(tail_ - head_);
    }

    size_type capacity() const {
        return capacity_;
    }

    bool empty() const {
        return head_ == tail_;
    }

private:
    bool invariants() const {
        assert(front() == this->operator [](0));
        assert(front() == *cbegin());
//      assert(front() == *(crend() + 1)); TODO doesn't compile
        assert(back() == this->operator [](size() - 1));
        assert(back() == *(cend() - 1));
//      assert(back() == *rbegin()); TODO this doens't compile either

        assert(size() < capacity());
        assert(size() >= 0);
        assert( capacity() == 0 || mask(capacity()) == 0);
        return true;
    }

    void double_capacity() {
        circular_deque temp(capacity() * 2);
        assert(temp.capacity() == capacity() * 2);
        auto it = begin();
        while (it != end()) {
            auto val = *it;
            temp.push_back(*it);
            ++it;
        }
        swap(temp);
        assert(invariants());
    }

    allocator_type alloc_;
    value_type * array_;
    size_t capacity_;
    int head_;
    int tail_;

};

template<typename T, typename Alloc>
bool operator==(const circular_deque<T, Alloc> &a,
        const circular_deque<T, Alloc> &b) {
    return a.size() == b.size() && std::equal(a.cbegin(), a.cend(), b.cbegin());
}

template<typename T, typename Alloc>
bool operator!=(const circular_deque<T, Alloc> &a,
        const circular_deque<T, Alloc> &b) {
    return a.size() != b.size() || !std::equal(a.cbegin(), a.cend(), b.cbegin());
}

#endif

Answer 1

Your code on the whole looks good, there's very little I can pick at. I can only offer a few minor suggestions for improvement.

Firstly, your operator= can be made slightly shorter and cleaner:

circular_deque& operator=(self_type other)
{
    swap(*this, other);
    assert(invariants);
    return *this;
}

Note that the parameter is passed by value, hence eliminating the need for a tmp in the function. This also uses a non-member swap function which you haven't provided, but probably should.

Minor slip up with:

template<typename iter>
void assign_into(iter from, iter to)

iter should be upper case. It's not going to change the semantics of the code of course, just sticking to the template parameters should be upper case convention (which is followed everywhere else in this code).

Your iterator erase(iterator i) function is less efficient than it could be - there's no good reason to construct a temporary here. Simply erase the position given and shift everything after it back one. If the iterator passed in is (say) the 2nd to last element, this should be effectively constant, whereas the current method will require a full construction, walking through the entire deque, and then complete destruction of the old deque.

A minor nitpick, but I'd rename double_capacity(). Perhaps sometime in the future you'll profile and decide that doubling the current capacity is not the optimal technique - maybe some other multiple would result in less wasted memory, or will result in less allocations. Maybe expand_capacity() would be a better function name. It is a private function, though, so this is a very minor complaint.

There's a missing include for std::equal: #include <algorithm>. Something else obviously pulls it in but it's best not to rely on that.

There are some missing functions you should provide:

Non-member: operator<, operator<=, operator>, operator>=. std::lexicographic_compare should be useful for this.

Member: const_iterator begin() const, const_iterator end() const - both of these should still be available. You do have cbegin() and cend(), but these are designed to get const_iterator from a non-const container. begin() and end() should still be overloaded with const versions. If you want to adhere more closely to the standard, there should also be some other functions like max_size, resize, get_allocator and the like.

Depending on if you want to add some C++11 functionality to this or not, you might want to also add a move constructor and move assignment operator:

circular_deque& operator=(circular_deque&& other);
circular_deque(circular_deque&& other);

With swap already implemented, these are pretty easy to implement.

Edit: Ok, as to the question of getting your invariants to compile, this actually shows up a bit of a deeper problem. This minimal program won't compile (for two reasons, actually - you're missing a crbegin() method, but we'll assume that gets added in before we try and compile this).

#include <iostream>

template <typename T>
void print(const circular_deque<T>& c)
{
    for(auto it = c.crbegin(); it != c.crend(); ++it)
        std::cout << *it << ", ";
    std::cout << "\n";
}

int main()
{
    circular_deque<int> d;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);

    print(d);

    return 0;
}

This spits out an error that looks something like the following:

stl_iterator.h:165:12: error: invalid initialization of reference of type
'std::reverse_iterator<circular_deque_iterator<const circular_deque<int>,
circular_deque<int>, const int> >::reference {aka int&}' from expression of type '
const int'

So what's this telling us? It's saying that reverse_iterator is trying to utilize reference, which is int&, but we're giving it a const int. How do we fix this? Well, we can replace the typedef for reference in circular_deque_iterator with

typedef typename deque_type::const_reference reference;

This will let your code compile, but it is a bit of a hack. Generally, getting all the code for an iterator and a const_iterator into a single class is tricky. A const_iterator shouldn't have a method like:

elem_type& operator*() {
    return (*buf_)[pos_];
}

It should have the const-equivalent:

const elem_type& operator*() const {
    return (*buf_)[pos_];
}

Obviously with what you're passing in at the moment, elem_type& will be equivalent to const elem_type& for the const version, but it is still missing the guarantee that it won't modify the iterator class itself. Likewise with operator->(). There are some rather sophisticated tricks you can get into to (possibly) correct this, utilizing traits classes along with the curiously recurring template pattern (CRTP), but this post is long enough as is already, and it all gets somewhat complicated.