src/commons/deque.h

#ifndef COMMONS_DEQUE_H
#define COMMONS_DEQUE_H

#include <list>
#include <vector>

namespace commons
{
  using namespace std;

  template <typename T>
  class deque
  {
  private:
    class chunk
    {
    public:
      chunk() : xs(node_size) {}
    private:
      vector<T> xs;
    };

    list<chunk> chunks;
    size_t node_size;
  public:
    deque(size_t node_size = 8192) : node_size(node_size) {}

    void push_back(const T& x)
    {
      chunk& last = chunks.back();
      if (last.xs.size() == last.xs.capacity()) {
        chunks.push_back(chunk());
      }
      last.push_back(x);
    }
  };
}

#endif

---