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
STL-style deque class
c++;beginner;c++11;queue;stl