Doubly ended queue

The deque structure implements a fast doubly ended queue that supports logarithmic-time operations for both weighted split and concatenation.

Runtime interface

The deque interface has much of the interface of the STL deque. All operations for accessing the front and back of the container (e.g., front, push_front, pop_front, etc.) are supported. In addition, the deque supports splitting and concatenation in logarithmic time and provides a random-access iterator.

Template interface

Like the STL deque, the following deque constructor takes template parameters for the Item and Item_alloc types. The constructor takes three additional template parameters:

• The Chunk_capacity specifies the maximum number of items that can fit in each chunk. Although each chunk can store at most Chunk_capacity items, the container can only guarantee that at most half of the cells of any given chunk are filled.
• The Cache type specifies the strategy to be used internally by the deque to maintain monoid-cached measurements of groups of items (see Customized data structures by cached measurement).
• The Chunk_struct type specifies the fixed-capacity ring-buffer representation to be used for storing items (see Fixed-capacity vectors).

namespace pasl {
namespace data {
namespace chunkedseq {
namespace bootstrapped {

template <
  class Item,
  int Chunk_capacity = 512,
  class Cache = cachedmeasure::trivial<Item, size_t>,
  template <
    class Chunk_item,
    int Capacity,
    class Chunk_item_alloc=std::allocator<Item>
  >
  class Chunk_struct = fixedcapacity::heap_allocated::ringbuffer_ptrx,
  class Item_alloc = std::allocator<Item>
>
using deque;

}}}}

Example: push and pop

#include <iostream>
#include <string>
#include <assert.h>

#include "chunkedseq.hpp"

int main(int argc, const char * argv[]) {
  
  using mydeque_type = pasl::data::chunkedseq::bootstrapped::deque<int>;

  const int nb = 5;
  
  mydeque_type mydeque;
  
  for (int i = 0; i < nb; i++)
    mydeque.push_back(i);
  for (int i = 0; i < nb; i++)
    mydeque.push_front(nb+i);
  
  assert(mydeque.size() == 2*nb);
  
  std::cout << "mydeque contains:";
  for (int i = 0; i < 2*nb; i++) {
    int v = (i % 2) ? mydeque.pop_front() : mydeque.pop_back();
    std::cout << " " << v;
  }
  std::cout << std::endl;
  
  assert(mydeque.empty());
  
  return 0;
  
}

Output

mydeque contains: 4 9 3 8 2 7 1 6 0 5

Example: split and concat

#include <iostream>
#include <string>
#include <assert.h>

#include "chunkedseq.hpp"

using mydeque_type = pasl::data::chunkedseq::bootstrapped::deque<int>;

static
void myprint(mydeque_type& mydeque) {
  auto it = mydeque.begin();
  while (it != mydeque.end())
    std::cout << " " << *it++;
  std::cout << std::endl;
}

int main(int argc, const char * argv[]) {
  
  mydeque_type mydeque = { 0, 1, 2, 3, 4, 5 };
  mydeque_type mydeque2;
  
  mydeque.split(size_t(3), mydeque2);
  
  mydeque.pop_back();
  mydeque.push_back(8888);
  
  mydeque2.pop_front();
  mydeque2.push_front(9999);
  
  std::cout << "Just after split:" << std::endl;
  std::cout << "contents of mydeque:";
  myprint(mydeque);
  std::cout << "contents of mydeque2:";
  myprint(mydeque2);
  
  mydeque.concat(mydeque2);
  
  std::cout << "Just after merge:" << std::endl;
  std::cout << "contents of mydeque:";
  myprint(mydeque);
  std::cout << "contents of mydeque2:";
  myprint(mydeque2);
  
  return 0;
  
}

Output

Just after split:
contents of mydeque: 0 1 8888
contents of mydeque2: 9999 4 5
Just after merge:
contents of mydeque: 0 1 8888 9999 4 5
contents of mydeque2: