Implementation of std::deque (obsolete)

Warning: This implementation is obsolete, because it doesn't meet the standard. Specifically, while the standard guarantee any pointers and references to elements to remain valid after insertion or erasure at the front or the back element, this implementation doesn't. This issue will be discussed later.

In fact, entire deque header, though.

According to Wikipedia, common implementations of std::deque include:

• Storing deque contents in a circular buffer, and only resizing when the buffer becomes full. This decreases the frequency of resizings.

• Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.

• Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.

But I had another idea: what if I join two std::vectors, facing opposite ways?

So I tried implementing this way:

```
#include
#include
#include
#include
#include
#include
#include
#include
namespace std {
template > class deque;
template
bool operator==(const deque& x, const deque& y);
template
bool operator& x, const deque& y);
template
bool operator!=(const deque& x, const deque& y);
template
bool operator>(const deque& x, const deque& y);
template
bool operator>=(const deque& x, const deque& y);
template
bool operator& x, const deque& y);
template
void swap(deque& x, deque& y);

template >
class deque {
public:
// types:
typedef T value_type;
typedef Allocator allocator_type;
typedef value_type &reference;
typedef const value_type &const_reference;
class iterator;
class const_iterator;

You've independently discovered how to implement a (double-ended) queue using two stacks. See for example How to implement a queue using two stacks? or google that phrase for lots of hits.

If you've implemented them efficiently, each of the implementations you mentioned should be equally efficient: amortized constant time for insertions and deletions. The details really depend on exactly what workload you're expecting to handle: lots of push_fronts followed by lots of pop_backs? lots of push_fronts followed by lots of pop_fronts? alternating push_fronts and pop_backs? alternating push_fronts and pop_fronts? etc.

As for the efficiency of your C++ implementation, I have a few comments, but they're mostly minor. Basically it looks very thorough, and matches the Standard's style very well.

template  class deque::iterator

Look into the SCARY iterator pattern. You should be able to do something like

template class deque_iterator { ... };

template class deque {
    using iterator = deque_iterator;
};

so that deque and deque don't need to instantiate two different iterator classes. This will improve compile times, and more importantly improve binary sizes (which translates into "programs that require less RAM" and "programs that fit into icache better").

iterator(const iterator &other) : bound(other.bound), pos(other.pos) {}

This and all your special member functions (constructors and assignment operators) for iterator and const_iterator can be =default'ed (and therefore should be, just in case they're used in a situation where trivial construction/assignment gives a performance benefit).

typename vector::iterator operator -> () const

Why not T *operator->() const?

template 
deque &deque::operator = (deque &&x) {
    negative = x.negative;
    positive = x.positive;
    return *this;
}

You're not getting move semantics here. This function should be =default'ed anyway; but if you're not going to =default it, then you ought to be doing

negative = std::move(x.negative);
positive = std::move(x.positive);

so that the vector contents are moved rather than copied.

In particular, because of your inefficient move-assignment operator, your swap operation is neither efficient nor noexcept:

template 
void swap(deque &x, deque &y) {
    deque temp(std::move(x));
    x = std::move(y);
    y = std::move(temp);
}

You should instead implement non-member swap as

template 
void swap(deque &x, deque &y) noexcept {
    x.swap(y);
}

and then implement the member function swap as

template 
void deque::swap(deque &other) noexcept {
    positive.swap(other.positive);
    negative.swap(other.negative);
}

StackExchange Code Review Q#101038, answer score: 12