STL-style deque class

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
#include
#include

template
class circular_deque_iterator {
public:
typedef circular_deque_iterator 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 &other) :
buf_(other.buf_), pos_(other.pos_) {
}

friend class circular_deque_iterator ;

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-(c

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
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 . 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>=. 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 

template 
void print(const circular_deque& c)
{
    for(auto it = c.crbegin(); it != c.crend(); ++it)
        std::cout  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, 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.

StackExchange Code Review Q#21487, answer score: 3