Bag

Our bag is a generic container that trades the guarantee of order between its items for stronger guarantees on space usage and faster push and pop operations than the corresponding properties of the stack structure. In particular, the bag guarantees that there are no empty spaces in between consecutive items of the sequence, whereas stack and deque can guarantee only that no more than half of the cells of the chunks are empty.

Runtime interface

Although our bag is unordered in general, in particular use cases, order among items is guaranteed. Order of insertion and removal of the items is guaranteed by the bag under any sequence of push or pop operations that affect the back of the container. The split and concatenation operations typically reorder items.

The container supports front, push_front and pop_front operations for the sole purpose of interface compatibility. These operations simply perform the corresponding actions on the back of the container.

Template interface

The template interface of the bag is similar to that of stack.

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

template <
  class Item,
  int Chunk_capacity = 512,
  class Cache = cachedmeasure::trivial<Item, size_t>,
  class Item_alloc = std::allocator<Item>
>
using bagopt;

}}}}

Example

#include <iostream>
#include <string>

#include "chunkedbag.hpp"

int main(int argc, const char * argv[]) {
  
  using mybag_type = pasl::data::chunkedseq::bootstrapped::bagopt<int>;
  
  mybag_type mybag = { 0, 1, 2, 3, 4 };

  std::cout << "mybag contains:";
  while (! mybag.empty())
    std::cout << " " << mybag.pop();
  std::cout << std::endl;
  
  return 0;
  
}

Output

mybag contains: 4 3 2 1 0