gistfile1.cpp

#ifndef CDEQUE_H
#define CDEQUE_H

#include <memory>
#include <utility>

// C++03 / C++11 compatability.
#if __cplusplus > 199711L
    #define COMP_CPP11
#endif

#ifdef COMP_CPP11
    #define COMP_NOEXCEPT noexcept
    #define COMP_NOEXCEPT_VAR(x) noexcept(x)
#else
    #define COMP_NOEXCEPT
    #define COMP_NOEXCEPT_VAR(x)
#endif


template<class T, class Allocator = std::allocator<T> >
class cdeque {
private:
    // Allocator typedefs were changed in C++11, make it version agnostic.
    #ifdef COMP_CPP11
        typedef std::allocator_traits<Allocator> allocator_traits;
    #else
        typedef Allocator allocator_traits;
    #endif

public:
    // Typedefs.
    typedef T                                          value_type;
    typedef Allocator                                  allocator_type;
    typedef typename allocator_traits::size_type       size_type;
    typedef typename allocator_traits::difference_type difference_type;
    typedef typename allocator_traits::pointer         pointer;
    typedef typename allocator_traits::const_pointer   const_pointer;

    #ifdef COMP_CPP11
        typedef T&                                     reference;
        typedef const T&                               const_reference;
    #else
        typedef typename Allocator::reference          reference;
        typedef typename Allocator::const_reference    const_reference;
    #endif

    typedef pointer                                    iterator;
    typedef const_pointer                              const_iterator;
    typedef std::reverse_iterator<iterator>            reverse_iterator;
    typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;

    // Construct/copy/destroy.
    ~cdeque();

    cdeque() COMP_NOEXCEPT_VAR(std::is_nothrow_default_constructible<allocator_type>::value);
    explicit cdeque(const Allocator& allocator);
    explicit cdeque(size_type n, const Allocator& allocator = Allocator());
    cdeque(size_type n, const T& value, const Allocator& allocator = Allocator());

    template<class InputIterator>
    cdeque(InputIterator first, InputIterator last, const Allocator& allocator = Allocator());

    cdeque(const cdeque<T, Allocator>& other);
    cdeque(const cdeque<T, Allocator>& other, const Allocator& allocator);

    cdeque<T, Allocator>& operator=(const cdeque<T, Allocator>& other);

    template<class InputIterator>
    void assign(InputIterator first, InputIterator last);

    void assign(size_type n, const T& t);
    allocator_type get_allocator() const COMP_NOEXCEPT;

    #ifdef COMP_CPP11
        cdeque(cdeque<T, Allocator>&& other);
        cdeque(cdeque<T, Allocator>&& other, const Allocator& allocator);
        cdeque(std::initializer_list<T> il, const Allocator& allocator = Allocator());
        cdeque<T, Allocator>& operator=(cdeque<T, Allocator>&&);
        cdeque<T, Allocator>& operator=(std::initializer_list<T> il);
        void assign(std::initializer_list<T> il);
    #endif

    // Iterators.
    iterator               begin()         COMP_NOEXCEPT { return iterator(impl.begin_cursor); }
    const_iterator         begin()   const COMP_NOEXCEPT { return iterator(impl.begin_cursor); }
    iterator               end()           COMP_NOEXCEPT { return iterator(impl.end_cursor); }
    const_iterator         end()     const COMP_NOEXCEPT { return iterator(impl.end_cursor); }

    reverse_iterator       rbegin()        COMP_NOEXCEPT { return reverse_iterator(end()); }
    const_reverse_iterator rbegin()  const COMP_NOEXCEPT { return const_reverse_iterator(end()); }
    reverse_iterator       rend()          COMP_NOEXCEPT { return reverse_iterator(begin()); }
    const_reverse_iterator rend()    const COMP_NOEXCEPT { return const_reverse_iterator(begin()); }

    const_iterator         cbegin()  const COMP_NOEXCEPT { return begin(); }
    const_iterator         cend()    const COMP_NOEXCEPT { return end(); }
    const_reverse_iterator crbegin() const COMP_NOEXCEPT { return rbegin(); }
    const_reverse_iterator crend()   const COMP_NOEXCEPT { return rend(); }

    // Capacity.
    size_type size() const COMP_NOEXCEPT;
    size_type max_size() const COMP_NOEXCEPT;
    size_type capacity() const COMP_NOEXCEPT;
    size_type capacity_front() const COMP_NOEXCEPT;
    size_type capacity_back() const COMP_NOEXCEPT;
    void resize(size_type n);
    void resize(size_type n, const T& t);
    void resize_front(size_type n);
    void resize_front(size_type n, const T& t);
    void resize_back(size_type n);
    void resize_back(size_type n, const T& t);
    void reserve(size_type n);
    void reserve_front(size_type n);
    void reserve_back(size_type n);
    void shrink_to_fit();
    bool empty() const COMP_NOEXCEPT;

    // Indexing.
    reference         operator[](size_type i);
    const_reference   operator[](size_type i) const;
    reference         at(size_type i);
    const_reference   at(size_type i) const;

    reference         front();
    const_reference   front() const;
    reference         back();
    const_reference   back() const;

    T*                data() COMP_NOEXCEPT;
    const T*          data() const COMP_NOEXCEPT;

    // Modifiers.
    void push_front(const T& x);
    void push_back(const T& x);
    void pop_front();
    void pop_back();
    iterator insert(const_iterator position, const T& t);
    iterator insert(const_iterator position, size_type n, const T& t);
    
    template<class InputIterator>
    iterator insert(const_iterator position, InputIterator first, InputIterator last);

    #ifdef COMP_CPP11
        void push_front(T&& x);
        void push_back(T&& x);
        template<class... Args> void emplace_front(Args&&... args);
        template<class... Args> void emplace_back(Args&&... args);
        template<class... Args> iterator emplace(const_iterator position, Args&&... args);
        iterator insert(const_iterator position, T&& t);
        iterator insert(const_iterator position, std::initializer_list<T> il);
    #endif

    iterator erase(const_iterator position);
    iterator erase(const_iterator first, const_iterator last);

    void swap(cdeque<T, Allocator>& other);
    void clear() COMP_NOEXCEPT;

private:
    // Empty base class optimization.
    struct impl_ : public Allocator {
        pointer begin_cursor; // cdeque[0]
        pointer end_cursor; // cdeque[n] (one-past-end)
        pointer begin_storage; // storage[0]
        pointer end_storage; // storage[n] (one-past-end)
    } impl;
};

// Comparison operators;
template<class T, class Allocator>
bool operator==(const cdeque<T, Allocator>& lhs, const cdeque<T, Allocator>& rhs);

template<class T, class Allocator>
bool operator< (const cdeque<T, Allocator>& lhs, const cdeque<T, Allocator>& rhs);

template<class T, class Allocator>
bool operator!=(const cdeque<T, Allocator>& lhs, const cdeque<T, Allocator>& rhs);

template<class T, class Allocator>
bool operator> (const cdeque<T, Allocator>& lhs, const cdeque<T, Allocator>& rhs);

template<class T, class Allocator>
bool operator<=(const cdeque<T, Allocator>& lhs, const cdeque<T, Allocator>& rhs);

template<class T, class Allocator>
bool operator>=(const cdeque<T, Allocator>& lhs, const cdeque<T, Allocator>& rhs);

namespace std {
    template<class T, class Allocator>
    void swap(cdeque<T, Allocator>& lhs, cdeque<T, Allocator>& rhs);
}

#ifdef COMP_CPP11
    #undef COMP_CPP11
#endif

#undef COMP_NOEXCEPT
#undef COMP_NOEXCEPT_VAR

#endif