Boost Container Selectors

Boost, and the C++ Boost Graph in particular, uses containers from the STL such as std::vector, std::list, and std::set to store elements of a set. Which is to be used is selected through empty classes passed as template paramenters upon declaration.

Generating your own Selector Struct with container_gen Traits Class

The adjacency_list class uses a traits class called container_gen to map the OutEdgeList and VertexList selectors to the actual container types used for the graph storage. The default version of the traits class is listed below, along with an example of how the class is specialized for the listS selector.

namespace boost {
  template <class Selector, class ValueType>
  struct container_gen { };

  template <class ValueType>
  struct container_gen<listS, ValueType> {
    typedef std::list<ValueType> type;
  };
}

To use some other container of your choice (such as std::unordered_set), define a selector class and then specialize the container_gen for your selector, inside the boost namespace.

struct unordered_setS { }; // your selector

  namespace boost {
    // the specialization for your selector
    template <class ValueType>
    struct container_gen<unordered_setS, ValueType> {
      typedef std::unordered_set<ValueType> type;
    };
  }

Templetized Selectors

There may also be situations when you want to use a container that has more template parameters than just ValueType. For instance, you may want to supply the allocator type. One way to do this is to hard-code in the extra parameters within the specialization of container_gen. However, if you want more flexibility then you can add a template parameter to the selector class. In the code below we show how to create a selector that lets you specify the allocator to be used with the std::list.

template <class Allocator>
  struct list_with_allocatorS { };

  namespace boost {
    template <class Alloc, class ValueType>
    struct container_gen<list_with_allocatorS<Alloc>, ValueType>
    {
      typedef typename Alloc::template rebind<ValueType>::other Allocator;
      typedef std::list<ValueType, Allocator> type;
    };
  }

  // now you can define a graph using std::list
  //   and a specific allocator
  typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;