Boost C++ Libraries

Container allocators are normally default-constructible because the are stateless. std::allocator and Boost.Pool's boost::pool_allocator/boost::fast_pool_allocator are examples of default-constructible allocators.

On the other hand, Boost.Interprocess allocators need to allocate memory from a concrete memory segment and not from a system-wide memory source (like the heap). Boost.Interprocess allocators are stateful, which means that they must be configured to tell them where the shared memory or the memory mapped file is.

This information is transmitted at compile-time and run-time: The allocators receive a template parameter defining the type of the segment manager and their constructor receive a pointer to the segment manager of the managed memory segment where the user wants to allocate the values.

Boost.Interprocess allocators have no default-constructors and containers must be explicitly initialized with a configured allocator:

//The allocators must be templatized with the segment manager type
typedef any_interprocess_allocator
   <int, managed_shared_memory::segment_manager, ...> Allocator;

//The allocator must be constructed with a pointer to the segment manager
Allocator alloc_instance (segment.get_segment_manager(), ...);

//Containers must be initialized with a configured allocator
typedef my_list<int, Allocator> MyIntList;
MyIntList mylist(alloc_inst);

//This would lead to a compilation error, because
//the allocator has no default constructor
//MyIntList mylist;

Boost.Interprocess allocators also have a get_segment_manager() function that returns the underlying segment manager that they have received in the constructor:

Allocator::segment_manager s = alloc_instance.get_segment_manager();
AnotherType *a = s->construct<AnotherType>(anonymous_instance)(/*Parameters*/);

When swapping STL containers, there is an active discussion on what to do with the allocators. Some STL implementations, for example Dinkumware from Visual .NET 2003, perform a deep swap of the whole container through a temporary when allocators are not equal. The proposed resolution to container swapping is that allocators should be swapped in a non-throwing way.

Unfortunately, this approach is not valid with shared memory. Using heap allocators, if Group1 of node allocators share a common segregated storage, and Group2 share another common segregated storage, a simple pointer swapping is needed to swap an allocator of Group1 and another allocator of Group2. But when the user wants to swap two shared memory allocators, each one placed in a different shared memory segment, this is not possible. As generally shared memory is mapped in different addresses in each process, a pointer placed in one segment can't point to any object placed in other shared memory segment, since in each process, the distance between the segments is different. However, if both shared memory allocators are in the same segment, a non-throwing swap is possible, just like heap allocators.

Until a final resolution is achieved. Boost.Interprocess allocators implement a non-throwing swap function that swaps internal pointers. If an allocator placed in a shared memory segment is swapped with other placed in a different shared memory segment, the result is undefined. But a crash is quite sure.

The allocator class defines an allocator class that uses the managed memory segment's algorithm to allocate and deallocate memory. This is achieved through the segment manager of the managed memory segment. This allocator is the equivalent for managed memory segments of the standard std::allocator. allocator is templatized with the allocated type, and the segment manager.

Equality: Two allocator instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are implemented as calls to the segment manager's allocation function so the allocator offers the same thread-safety as the segment manager.

To use allocator you must include the following header:

#include <boost/interprocess/allocators/allocator.hpp>

allocator has the following declaration:

namespace boost {
namespace interprocess {

template<class T, class SegmentManager>
class allocator;

}  //namespace interprocess {
}  //namespace boost {

The allocator just provides the needed typedefs and forwards all allocation and deallocation requests to the segment manager passed in the constructor, just like std::allocator forwards the requests to operator new[].

Using allocator is straightforward:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <cassert>

using namespace boost::interprocess;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only, 
                                 "MySharedMemory",  //segment name
                                 65536);

   //Create an allocator that allocates ints from the managed segment
   allocator<int, managed_shared_memory::segment_manager>
      allocator_instance(segment.get_segment_manager());

   //Copy constructed allocator is equal
   allocator<int, managed_shared_memory::segment_manager>
      allocator_instance2(allocator_instance);
   assert(allocator_instance2 == allocator_instance);

   //Allocate and deallocate memory for 100 ints
   allocator_instance2.deallocate(allocator_instance.allocate(100), 100);

   return 0;
}

node_allocator, private_node_allocator and cached_node_allocator implement the standard allocator interface and the functions explained in the Properties of Boost.Interprocess allocators.

All these allocators are templatized by 3 parameters:

These allocators also offer the deallocate_free_chunks() function. This function will traverse all the memory chunks of the pool and will return to the managed memory segment the free chunks of memory. If this function is not used, deallocating the free chunks does not happen until the pool is destroyed so the only way to return memory allocated by the pool to the segment before destructing the pool is calling manually this function. This function is quite time-consuming because it has quadratic complexity (O(N^2)).

For heap-memory node allocators (like Boost.Pool's boost::fast_pool_allocator usually a global, thread-shared singleton pool is used for each node size. This is not possible if you try to share a node allocator between processes. To achieve this sharing node_allocator uses the segment manager's unique type allocation service (see Unique instance construction section).

In the initialization, a node_allocator object searches this unique object in the segment. If it is not preset, it builds one. This way, all node_allocator objects built inside a memory segment share a unique memory pool.

The common segregated storage is not only shared between node_allocators of the same type, but it is also shared between all node allocators that allocate objects of the same size, for example, node_allocator<uint32> and node_allocator<float32>. This saves a lot of memory but also imposes an synchronization overhead for each node allocation.

The dynamically created common segregated storage integrates a reference count so that a node_allocator can know if any other node_allocator is attached to the same common segregated storage. When the last allocator attached to the pool is destroyed, the pool is destroyed.

Equality: Two node_allocator instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are implemented as calls to the shared pool. The shared pool offers the same synchronization guarantees as the segment manager.

To use node_allocator, you must include the following header:

#include <boost/interprocess/allocators/node_allocator.hpp>

node_allocator has the following declaration:

namespace boost {
namespace interprocess {

template<class T, class SegmentManager, std::size_t NodesPerChunk = ...>
class node_allocator;

}  //namespace interprocess {
}  //namespace boost {

An example using node_allocator:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/node_allocator.hpp>
#include <cassert>

using namespace boost::interprocess;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only, 
                                 "MySharedMemory",  //segment name
                                 65536);

   //Create a node_allocator that allocates ints from the managed segment
   //The number of chunks per segment is the default value
   typedef node_allocator<int, managed_shared_memory::segment_manager>
      node_allocator_t;
   node_allocator_t allocator_instance(segment.get_segment_manager());

   //Create another node_allocator. Since the segment manager address
   //is the same, this node_allocator will be
   //attached to the same pool so "allocator_instance2" can deallocate
   //nodes allocated by "allocator_instance"
   node_allocator_t allocator_instance2(segment.get_segment_manager());

   //Create another node_allocator using copy-constructor. This
   //node_allocator will also be attached to the same pool
   node_allocator_t allocator_instance3(allocator_instance2);

   //All allocators are equal
   assert(allocator_instance == allocator_instance2);
   assert(allocator_instance2 == allocator_instance3);

   //So memory allocated with one can be deallocated with another
   allocator_instance2.deallocate(allocator_instance.allocate(1), 1);
   allocator_instance3.deallocate(allocator_instance2.allocate(1), 1);

   //The common pool will be destroyed here, since no allocator is
   //attached to the pool
   return 0;
}

As said, the node_allocator shares a common segregated storage between node_allocators that allocate objects of the same size and this optimizes memory usage. However, it needs a unique/named object construction feature so that this sharing can be possible. Also imposes a synchronization overhead per node allocation because of this share. Sometimes, the unique object service is not available (for example, when building index types to implement the named allocation service itself) or the synchronization overhead is not acceptable. Many times the programmer wants to make sure that the pool is destroyed when the allocator is destroyed, to free the memory as soon as possible.

So private_node_allocator uses the same segregated storage as node_allocator, but each private_node_allocator has its own segregated storage pool. No synchronization is used when allocating nodes, so there is far less overhead for an operation that usually involves just a few pointer operations when allocating and deallocating a node.

Equality: Two private_node_allocator instances never compare equal. Memory allocated with one allocator can't be deallocated with another one.

Allocation thread-safety: Allocation and deallocation are not thread-safe.

To use private_node_allocator, you must include the following header:

#include <boost/interprocess/allocators/private_node_allocator.hpp>

private_node_allocator has the following declaration:

namespace boost {
namespace interprocess {

template<class T, class SegmentManager, std::size_t NodesPerChunk = ...>
class private_node_allocator;

}  //namespace interprocess {
}  //namespace boost {

An example using private_node_allocator:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/private_node_allocator.hpp>
#include <cassert>

using namespace boost::interprocess;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   }  remover;

   //Create shared memory
   managed_shared_memory segment(create_only, 
                                 "MySharedMemory",  //segment name
                                 65536);

   //Create a private_node_allocator that allocates ints from the managed segment
   //The number of chunks per segment is the default value
   typedef private_node_allocator<int, managed_shared_memory::segment_manager>
      private_node_allocator_t;
   private_node_allocator_t allocator_instance(segment.get_segment_manager());

   //Create another private_node_allocator.
   private_node_allocator_t allocator_instance2(segment.get_segment_manager());

   //Although the segment manager address
   //is the same, this private_node_allocator will have its own pool so
   //"allocator_instance2" CAN'T deallocate nodes allocated by "allocator_instance".
   //"allocator_instance2" is NOT equal to "allocator_instance"
   assert(allocator_instance != allocator_instance2);   

   //Create another node_allocator using copy-constructor.
   private_node_allocator_t allocator_instance3(allocator_instance2);

   //This allocator is also unequal to allocator_instance2
   assert(allocator_instance2 != allocator_instance3);

   //Pools are destroyed with the allocators
   return 0;
}

The total node sharing of node_allocator can impose a high overhead for some applications and the minimal synchronization overhead of private_node_allocator can impose a unacceptable memory waste for other applications.

To solve this, Boost.Interprocess offers an allocator, cached_node_allocator, that allocates nodes from the common pool but caches some of them privately so that following allocations have no synchronization overhead. When the cache is full, the allocator returns some cached nodes to the common pool, and those will be available to other allocators.

Equality: Two cached_node_allocator instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are not thread-safe.

To use cached_node_allocator, you must include the following header:

#include <boost/interprocess/allocators/cached_node_allocator.hpp>

cached_node_allocator has the following declaration:

namespace boost {
namespace interprocess {

template<class T, class SegmentManager, std::size_t NodesPerChunk = ...>
class cached_node_allocator;

}  //namespace interprocess {
}  //namespace boost {

A cached_node_allocator instance and a node_allocator instance share the same pool if both instances receive the same template parameters. This means that nodes returned to the shared pool by one of them can be reused by the other. Please note that this does not mean that both allocators compare equal, this is just information for programmers that want to maximize the use of the pool.

cached_node_allocator, offers additional functions to control the cache (the cache can be controlled per instance):

An example using cached_node_allocator:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/cached_node_allocator.hpp>
#include <cassert>

using namespace boost::interprocess;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only, 
                                 "MySharedMemory",  //segment name
                                 65536);

   //Create a cached_node_allocator that allocates ints from the managed segment
   //The number of chunks per segment is the default value
   typedef cached_node_allocator<int, managed_shared_memory::segment_manager>
      cached_node_allocator_t;
   cached_node_allocator_t allocator_instance(segment.get_segment_manager());

   //The max cached nodes are configurable per instance
   allocator_instance.set_max_cached_nodes(3);

   //Create another cached_node_allocator. Since the segment manager address
   //is the same, this cached_node_allocator will be
   //attached to the same pool so "allocator_instance2" can deallocate
   //nodes allocated by "allocator_instance"
   cached_node_allocator_t allocator_instance2(segment.get_segment_manager());

   //The max cached nodes are configurable per instance
   allocator_instance2.set_max_cached_nodes(5);

   //Create another cached_node_allocator using copy-constructor. This
   //cached_node_allocator will also be attached to the same pool
   cached_node_allocator_t allocator_instance3(allocator_instance2);

   //We can clear the cache
   allocator_instance3.deallocate_cache();

   //All allocators are equal
   assert(allocator_instance == allocator_instance2);
   assert(allocator_instance2 == allocator_instance3);

   //So memory allocated with one can be deallocated with another
   allocator_instance2.deallocate(allocator_instance.allocate(1), 1);
   allocator_instance3.deallocate(allocator_instance2.allocate(1), 1);

   //The common pool will be destroyed here, since no allocator is
   //attached to the pool
   return 0;
}

adaptive_pool, private_adaptive_pool and cached_adaptive_pool implement the standard allocator interface and the functions explained in the Properties of Boost.Interprocess allocators.

All these allocators are templatized by 4 parameters:

These allocators also offer the deallocate_free_chunks() function. This function will traverse all the memory chunks of the pool and will return to the managed memory segment the free chunks of memory. This function is much faster than for segregated storage allocators, because the adaptive pool algorithm offers constant-time access to free chunks.

Just like node_allocator a global, process-thread pool is used for each node size. In the initialization, adaptive_pool searches the pool in the segment. If it is not preset, it builds one. The adaptive pool, is created using a unique name. The adaptive pool it is also shared between all node_allocators that allocate objects of the same size, for example, adaptive_pool<uint32> and adaptive_pool<float32>.

The common adaptive pool is destroyed when all the allocators attached to the pool are destroyed.

Equality: Two adaptive_pool instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are implemented as calls to the shared pool. The shared pool offers the same synchronization guarantees as the segment manager.

To use adaptive_pool, you must include the following header:

#include <boost/interprocess/allocators/adaptive_pool.hpp>

adaptive_pool has the following declaration:

namespace boost {
namespace interprocess {

template<class T, class SegmentManager, std::size_t NodesPerChunk = ..., std::size_t MaxFreeChunks = ...>
class adaptive_pool;

}  //namespace interprocess {
}  //namespace boost {

An example using adaptive_pool:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/adaptive_pool.hpp>
#include <cassert>

using namespace boost::interprocess;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only, 
                                 "MySharedMemory",  //segment name
                                 65536);

   //Create a adaptive_pool that allocates ints from the managed segment
   //The number of chunks per segment is the default value
   typedef adaptive_pool<int, managed_shared_memory::segment_manager>
      adaptive_pool_t;
   adaptive_pool_t allocator_instance(segment.get_segment_manager());

   //Create another adaptive_pool. Since the segment manager address
   //is the same, this adaptive_pool will be
   //attached to the same pool so "allocator_instance2" can deallocate
   //nodes allocated by "allocator_instance"
   adaptive_pool_t allocator_instance2(segment.get_segment_manager());

   //Create another adaptive_pool using copy-constructor. This
   //adaptive_pool will also be attached to the same pool
   adaptive_pool_t allocator_instance3(allocator_instance2);

   //All allocators are equal
   assert(allocator_instance == allocator_instance2);
   assert(allocator_instance2 == allocator_instance3);

   //So memory allocated with one can be deallocated with another
   allocator_instance2.deallocate(allocator_instance.allocate(1), 1);
   allocator_instance3.deallocate(allocator_instance2.allocate(1), 1);

   //The common pool will be destroyed here, since no allocator is
   //attached to the pool
   return 0;
}

Just like private_node_allocator owns a private segregated storage pool, private_adaptive_pool owns its own adaptive pool. If the user wants to avoid the excessive node allocation synchronization overhead in a container private_adaptive_pool is a good choice.

Equality: Two private_adaptive_pool instances never compare equal. Memory allocated with one allocator can't be deallocated with another one.

Allocation thread-safety: Allocation and deallocation are not thread-safe.

To use private_adaptive_pool, you must include the following header:

#include <boost/interprocess/allocators/private_adaptive_pool.hpp>

private_adaptive_pool has the following declaration:

namespace boost {
namespace interprocess {

template<class T, class SegmentManager, std::size_t NodesPerChunk = ..., std::size_t MaxFreeChunks = ...>
class private_adaptive_pool;

}  //namespace interprocess {
}  //namespace boost {

An example using private_adaptive_pool:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/private_adaptive_pool.hpp>
#include <cassert>

using namespace boost::interprocess;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only, 
                                 "MySharedMemory",  //segment name
                                 65536);

   //Create a private_adaptive_pool that allocates ints from the managed segment
   //The number of chunks per segment is the default value
   typedef private_adaptive_pool<int, managed_shared_memory::segment_manager>
         private_adaptive_pool_t;
   private_adaptive_pool_t allocator_instance(segment.get_segment_manager());

   //Create another private_adaptive_pool.
   private_adaptive_pool_t allocator_instance2(segment.get_segment_manager());

   //Although the segment manager address
   //is the same, this private_adaptive_pool will have its own pool so
   //"allocator_instance2" CAN'T deallocate nodes allocated by "allocator_instance".
   //"allocator_instance2" is NOT equal to "allocator_instance"
   assert(allocator_instance != allocator_instance2);   

   //Create another adaptive_pool using copy-constructor.
   private_adaptive_pool_t allocator_instance3(allocator_instance2);

   //This allocator is also unequal to allocator_instance2
   assert(allocator_instance2 != allocator_instance3);

   //Pools are destroyed with the allocators
   return 0;
}

Adaptive pools have also a cached version. In this allocator the allocator caches some nodes to avoid the synchronization and bookkeeping overhead of the shared adaptive pool. cached_adaptive_pool allocates nodes from the common adaptive pool but caches some of them privately so that following allocations have no synchronization overhead. When the cache is full, the allocator returns some cached nodes to the common pool, and those will be available to other cached_adaptive_pools or adaptive_pools of the same managed segment.

Equality: Two cached_adaptive_pool instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are not thread-safe.

To use cached_adaptive_pool, you must include the following header:

#include <boost/interprocess/allocators/cached_adaptive_pool.hpp>

cached_adaptive_pool has the following declaration:

namespace boost {
namespace interprocess {

template<class T, class SegmentManager, std::size_t NodesPerChunk = ..., std::size_t MaxFreeNodes = ...>
class cached_adaptive_pool;

}  //namespace interprocess {
}  //namespace boost {

A cached_adaptive_pool instance and an adaptive_pool instance share the same pool if both instances receive the same template parameters. This means that nodes returned to the shared pool by one of them can be reused by the other. Please note that this does not mean that both allocators compare equal, this is just information for programmers that want to maximize the use of the pool.

cached_adaptive_pool, offers additional functions to control the cache (the cache can be controlled per instance):

An example using cached_adaptive_pool:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/cached_adaptive_pool.hpp>
#include <cassert>

using namespace boost::interprocess;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only, 
                                 "MySharedMemory",  //segment name
                                 65536);

   //Create a cached_adaptive_pool that allocates ints from the managed segment
   //The number of chunks per segment is the default value
   typedef cached_adaptive_pool<int, managed_shared_memory::segment_manager>
      cached_adaptive_pool_t;
   cached_adaptive_pool_t allocator_instance(segment.get_segment_manager());

   //The max cached nodes are configurable per instance
   allocator_instance.set_max_cached_nodes(3);

   //Create another cached_adaptive_pool. Since the segment manager address
   //is the same, this cached_adaptive_pool will be
   //attached to the same pool so "allocator_instance2" can deallocate
   //nodes allocated by "allocator_instance"
   cached_adaptive_pool_t allocator_instance2(segment.get_segment_manager());

   //The max cached nodes are configurable per instance
   allocator_instance2.set_max_cached_nodes(5);

   //Create another cached_adaptive_pool using copy-constructor. This
   //cached_adaptive_pool will also be attached to the same pool
   cached_adaptive_pool_t allocator_instance3(allocator_instance2);

   //We can clear the cache
   allocator_instance3.deallocate_cache();

   //All allocators are equal
   assert(allocator_instance == allocator_instance2);
   assert(allocator_instance2 == allocator_instance3);

   //So memory allocated with one can be deallocated with another
   allocator_instance2.deallocate(allocator_instance.allocate(1), 1);
   allocator_instance3.deallocate(allocator_instance2.allocate(1), 1);

   //The common pool will be destroyed here, since no allocator is
   //attached to the pool
   return 0;
}

Boost.Interprocess STL compatible allocators offer a STL compatible allocator interface and if they define their internal pointer typedef as a relative pointer, they can sbe used to place STL containers in shared memory, memory mapped files or in a user defined memory segment.

However, as Scott Meyers mentions in his Effective STL book, Item 10, "Be aware of allocator conventions and restrictions":

Obviously, if any STL implementation ignores pointer typedefs, no smart pointer can be used as allocator::pointer. If STL implementations assume all allocator objects of the same type compare equal, it will assume that two allocators, each one allocating from a different memory pool are equal, which is a complete disaster.

STL containers that we want to place in shared memory or memory mapped files with Boost.Interprocess can't make any of these assumptions, so:

Unfortunately, many STL implementations use raw pointers for internal data and ignore allocator pointer typedefs and others suppose at some point that the allocator::typedef is T. This is because in practice, there wasn't need of allocators with a pointer typedef different from T for pooled/node memory allocators.

Until STL implementations handle allocator::pointer typedefs in a generic way, Boost.Interprocess offers the following classes:

#include <boost/interprocess/containers/vector.hpp>

#include <boost/interprocess/containers/deque.hpp>

#include <boost/interprocess/containers/list.hpp>

#include <boost/interprocess/containers/slist.hpp>

#include <boost/interprocess/containers/set.hpp>
#include <boost/interprocess/containers/map.hpp>

#include <boost/interprocess/containers/flat_set.hpp>
#include <boost/interprocess/containers/flat_map.hpp>

#include <boost/interprocess/containers/string.hpp>

All these containers have the same default arguments as standard containers and they can be used with other, non Boost.Interprocess allocators (std::allocator, or boost::pool_allocator, for example).

To place any of these containers in managed memory segments, we must define the allocator template parameter with a Boost.Interprocess allocator so that the container allocates the values in the managed memory segment. To place the container itself in shared memory, we construct it in the managed memory segment just like any other object with Boost.Interprocess:

#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/managed_shared_memory.hpp>

int main ()
{
   using namespace boost::interprocess;
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //A managed shared memory where we can construct objects
   //associated with a c-string
   managed_shared_memory segment(create_only,
                                 "MySharedMemory",  //segment name
                                 65536);

   //Alias an STL-like allocator of ints that allocates ints from the segment
   typedef allocator<int, managed_shared_memory::segment_manager> 
      ShmemAllocator;

   //Alias a vector that uses the previous STL-like allocator
   typedef vector<int, ShmemAllocator> MyVector;

   int initVal[]        = {0, 1, 2, 3, 4, 5, 6 };
   const int *begVal    = initVal;
   const int *endVal    = initVal + sizeof(initVal)/sizeof(initVal[0]);

   //Initialize the STL-like allocator
   const ShmemAllocator alloc_inst (segment.get_segment_manager());

   //Construct the vector in the shared memory segment with the STL-like allocator 
   //from a range of iterators
   MyVector *myvector = 
      segment.construct<MyVector>
         ("MyVector")/*object name*/
         (begVal     /*first ctor parameter*/,
         endVal     /*second ctor parameter*/, 
         alloc_inst /*third ctor parameter*/); 

   //Use vector as your want
   std::sort(myvector->rbegin(), myvector->rend());
   // . . .
   //When done, destroy and delete vector from the segment
   segment.destroy<MyVector>("MyVector");
   return 0;
}

These containers also show how easy is to create/modify an existing container making possible to place it in shared memory.

Boost.Interprocess containers are placed in shared memory/memory mapped files, etc... using two mechanisms at the same time:

This means that to place any Boost.Interprocess container (including Boost.Interprocess strings) in shared memory or memory mapped files, containers must:

If you do the first two points but you don't use construct<> or find_or_construct<> you are creating a container placed only in your process but that allocates memory for contained types from shared memory/memory mapped file.

Let's see an example:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/containers/string.hpp>
#include <boost/interprocess/allocators/allocator.hpp>

int main ()
{
   using namespace boost::interprocess;
   //Typedefs
   typedef allocator<char, managed_shared_memory::segment_manager> 
      CharAllocator;
   typedef basic_string<char, std::char_traits<char>, CharAllocator>
      MyShmString;
   typedef allocator<MyShmString, managed_shared_memory::segment_manager>
      StringAllocator;      
   typedef vector<MyShmString, StringAllocator>
      MyShmStringVector;

   //Open shared memory
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   managed_shared_memory shm(create_only, "MySharedMemory", 10000);

   //Create allocators
   CharAllocator     charallocator  (shm.get_segment_manager());
   StringAllocator   stringallocator(shm.get_segment_manager());

   //This string is in only in this process (the pointer pointing to the
   //buffer that will hold the text is not in shared memory). 
   //But the buffer that will hold "this is my text" is allocated from 
   //shared memory
   MyShmString mystring(charallocator);
   mystring = "this is my text";

   //This vector is only in this process (the pointer pointing to the
   //buffer that will hold the MyShmString-s is not in shared memory). 
   //But the buffer that will hold 10 MyShmString-s is allocated from 
   //shared memory using StringAllocator. Since strings use a shared 
   //memory allocator (CharAllocator) the 10 buffers that hold 
   //"this is my text" text are also in shared memory.
   MyShmStringVector myvector(stringallocator);
   myvector.insert(myvector.begin(), 10, mystring);

   //This vector is fully constructed in shared memory. All pointers
   //buffers are constructed in the same shared memory segment
   //This vector can be safely accessed from other processes.
   MyShmStringVector *myshmvector = 
      shm.construct<MyShmStringVector>("myshmvector")(stringallocator);
   myshmvector->insert(myshmvector->begin(), 10, mystring);

   //Destroy vector. This will free all strings that the vector contains
   shm.destroy_ptr(myshmvector);
   return 0;
}

Boost.Interprocess containers support move semantics, which means that the contents of a container can be moved from a container two another one, without any copying. The contents of the source container are transferred to the target container and the source container is left in default-constructed state.

When using containers of containers, we can also use move-semantics to insert objects in the container, avoiding unnecessary copies.

To transfer the contents of a container to another one, use boost::interprocess::move() function, as shown in the example. For more details about functions supporting move-semantics, see the reference section of Boost.Interprocess containers:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/containers/string.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <cassert>

int main ()
{
   using namespace boost::interprocess;

   //Typedefs
   typedef managed_shared_memory::segment_manager     SegmentManager;
   typedef allocator<char, SegmentManager>            CharAllocator;
   typedef basic_string<char, std::char_traits<char>
                        ,CharAllocator>                MyShmString;
   typedef allocator<MyShmString, SegmentManager>     StringAllocator;      
   typedef vector<MyShmString, StringAllocator>       MyShmStringVector;

   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   managed_shared_memory shm(create_only, "MySharedMemory", 10000);

   //Create allocators
   CharAllocator     charallocator  (shm.get_segment_manager());
   StringAllocator   stringallocator(shm.get_segment_manager());

   //Create a vector of strings in shared memory.
   MyShmStringVector *myshmvector = 
      shm.construct<MyShmStringVector>("myshmvector")(stringallocator);

   //Insert 50 strings in shared memory. The strings will be allocated
   //only once and no string copy-constructor will be called when inserting
   //strings, leading to a great performance.
   MyShmString string_to_compare(charallocator);
   string_to_compare = "this is a long, long, long, long, long, long, string...";
   
   myshmvector->reserve(50);
   for(int i = 0; i < 50; ++i){
      MyShmString move_me(string_to_compare);
      //In the following line, no string copy-constructor will be called.
      //"move_me"'s contents will be transferred to the string created in
      //the vector
      myshmvector->push_back(boost::interprocess::move(move_me));

      //The source string is in default constructed state
      assert(move_me.empty());

      //The newly created string will be equal to the "move_me"'s old contents
      assert(myshmvector->back() == string_to_compare);
   }

   //Now erase a string...
   myshmvector->pop_back();

   //...And insert one in the first position.
   //No string copy-constructor or assignments will be called, but
   //move constructors and move-assignments. No memory allocation 
   //function will be called in this operations!!
   myshmvector->insert(myshmvector->begin(), boost::interprocess::move(string_to_compare));

   //Destroy vector. This will free all strings that the vector contains
   shm.destroy_ptr(myshmvector);
   return 0;
}

When creating containers of containers, each container needs an allocator. To avoid using several allocators with complex type definitions, we can take advantage of the type erasure provided by void allocators and the ability to implicitly convert void allocators in allocators that allocate other types.

Here we have an example that builds a map in shared memory. Key is a string and the mapped type is a class that stores several containers:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/containers/map.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/containers/string.hpp>

using namespace boost::interprocess;

//Typedefs of allocators and containers
typedef managed_shared_memory::segment_manager                       segment_manager_t;
typedef allocator<void, segment_manager_t>                           void_allocator;
typedef allocator<int, segment_manager_t>                            int_allocator;
typedef vector<int, int_allocator>                                   int_vector;
typedef allocator<int_vector, segment_manager_t>                     int_vector_allocator;
typedef vector<int_vector, int_vector_allocator>                     int_vector_vector;
typedef allocator<char, segment_manager_t>                           char_allocator;
typedef basic_string<char, std::char_traits<char>, char_allocator>   char_string;

class complex_data
{
   int               id_;
   char_string       char_string_;
   int_vector_vector int_vector_vector_;

   public:
   //Since void_allocator is convertible to any other allocator<T>, we can simplify
   //the initialization taking just one allocator for all inner containers.
   complex_data(int id, const char *name, const void_allocator &void_alloc)
      : id_(id), char_string_(name, void_alloc), int_vector_vector_(void_alloc)
   {}
   //Other members...
};

//Definition of the map holding a string as key and complex_data as mapped type
typedef std::pair<const char_string, complex_data>                      map_value_type;
typedef std::pair<char_string, complex_data>                            movable_to_map_value_type;
typedef allocator<map_value_type, segment_manager_t>                    map_value_type_allocator;
typedef map< char_string, complex_data
           , std::less<char_string>, map_value_type_allocator>          complex_map_type;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only,"MySharedMemory", 65536);

   //An allocator convertible to any allocator<T, segment_manager_t> type
   void_allocator alloc_inst (segment.get_segment_manager());

   //Construct the shared memory map and fill it
   complex_map_type *mymap = segment.construct<complex_map_type>
      //(object name), (first ctor parameter, second ctor parameter)
         ("MyMap")(std::less<char_string>(), alloc_inst);

   for(int i = 0; i < 100; ++i){
      //Both key(string) and value(complex_data) need an allocator in their constructors
      char_string  key_object(alloc_inst);
      complex_data mapped_object(i, "default_name", alloc_inst);
      map_value_type value(key_object, mapped_object);
      //Modify values and insert them in the map
      mymap->insert(value);
   }
   return 0;
}

Boost.Unordered containers are compatible with Interprocess, so programmers can store hash containers in shared memory and memory mapped files. Here is a small example storing unordered_map in shared memory:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>

#include <boost/unordered_map.hpp>     //boost::unordered_map
#include <functional>                  //std::equal_to
#include <boost/functional/hash.hpp>   //boost::hash

int main ()
{
   using namespace boost::interprocess;
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only, "MySharedMemory", 65536);

   //Note that unordered_map<Key, MappedType>'s value_type is std::pair<const Key, MappedType>,
   //so the allocator must allocate that pair.
   typedef int    KeyType;
   typedef float  MappedType;
   typedef std::pair<const int, float> ValueType;

   //Typedef the allocator
   typedef allocator<ValueType, managed_shared_memory::segment_manager> ShmemAllocator;

   //Alias an unordered_map of ints that uses the previous STL-like allocator.
   typedef boost::unordered_map
      < KeyType               , MappedType
      , boost::hash<KeyType>  ,std::equal_to<KeyType>
      , ShmemAllocator>
   MyHashMap;

   //Construct a shared memory hash map.
   //Note that the first parameter is the initial bucket count and
   //after that, the hash function, the equality function and the allocator
   MyHashMap *myhashmap = segment.construct<MyHashMap>("MyHashMap")  //object name
      ( 3, boost::hash<int>(), std::equal_to<int>()                  //
      , segment.get_allocator<ValueType>());                         //allocator instance

   //Insert data in the hash map
   for(int i = 0; i < 100; ++i){
      myhashmap->insert(ValueType(i, (float)i));
   }
   return 0;
}

The widely used Boost.MultiIndex library is compatible with Boost.Interprocess so we can construct pretty good databases in shared memory. Constructing databases in shared memory is a bit tougher than in normal memory, usually because those databases contain strings and those strings need to be placed in shared memory. Shared memory strings require an allocator in their constructors so this usually makes object insertion a bit more complicated.

Here is an example that shows how to put a multi index container in shared memory:

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/containers/string.hpp>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>

using namespace boost::interprocess;
namespace bmi = boost::multi_index;

typedef managed_shared_memory::allocator<char>::type              char_allocator;
typedef basic_string<char, std::char_traits<char>, char_allocator>shm_string;

//Data to insert in shared memory
struct employee
{
   int         id;
   int         age;
   shm_string  name;
   employee( int id_
           , int age_
           , const char *name_
           , const char_allocator &a)
      : id(id_), age(age_), name(name_, a)
   {}
};

//Tags
struct id{};
struct age{};
struct name{};

// Define a multi_index_container of employees with following indices:
//   - a unique index sorted by employee::int,
//   - a non-unique index sorted by employee::name,
//   - a non-unique index sorted by employee::age.
typedef bmi::multi_index_container<
  employee,
  bmi::indexed_by<
    bmi::ordered_unique
      <bmi::tag<id>,  BOOST_MULTI_INDEX_MEMBER(employee,int,id)>,
    bmi::ordered_non_unique<
      bmi::tag<name>,BOOST_MULTI_INDEX_MEMBER(employee,shm_string,name)>,
    bmi::ordered_non_unique
      <bmi::tag<age>, BOOST_MULTI_INDEX_MEMBER(employee,int,age)> >,
  managed_shared_memory::allocator<employee>::type
> employee_set;

int main ()
{
   //Remove shared memory on construction and destruction
   struct shm_remove
   {
      shm_remove() { shared_memory_object::remove("MySharedMemory"); }
      ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
   } remover;

   //Create shared memory
   managed_shared_memory segment(create_only,"MySharedMemory", 65536);

   //Construct the multi_index in shared memory
   employee_set *es = segment.construct<employee_set>
      ("My MultiIndex Container")            //Container's name in shared memory
      ( employee_set::ctor_args_list()
      , segment.get_allocator<employee>());  //Ctor parameters

   //Now insert elements
   char_allocator ca(segment.get_allocator<char>());
   es->insert(employee(0,31, "Joe", ca));
   es->insert(employee(1,27, "Robert", ca));
   es->insert(employee(2,40, "John", ca));
   return 0;
}

The algorithm is a variation of sequential fit using singly linked list of free memory buffers. The algorithm is based on the article about shared memory titled "Taming Shared Memory" . The algorithm is as follows:

The shared memory is divided in blocks of free shared memory, each one with some control data and several bytes of memory ready to be used. The control data contains a pointer (in our case offset_ptr) to the next free block and the size of the block. The allocator consists of a singly linked list of free blocks, ordered by address. The last block, points always to the first block:

simple_seq_fit memory layout:

    main      extra  allocated  free_block_1     allocated   free_block_2    allocated   free_block_3    
    header    header  block       ctrl     usr     block      ctrl     usr     block      ctrl     usr
   _________  _____  _________  _______________  _________  _______________  _________  _______________ 
  |         ||     ||         ||         |     ||         ||         |     ||         ||         |     |
  |free|ctrl||extra||         ||next|size| mem ||         ||next|size| mem ||         ||next|size| mem |
  |_________||_____||_________||_________|_____||_________||_________|_____||_________||_________|_____|
      |                         | |                         |  |                       | |             
      |_>_>_>_>_>_>_>_>_>_>_>_>_| |_>_>_>_>_>_>_>_>_>_>_>_>_|  |_>_>_>_>_>_>_>_>_>_>_>_| |            
                                |                                                        |
                                |_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<__|

When a user requests N bytes of memory, the allocator traverses the free block list looking for a block large enough. If the "mem" part of the block has the same size as the requested memory, we erase the block from the list and return a pointer to the "mem" part of the block. If the "mem" part size is bigger than needed, we split the block in two blocks, one of the requested size and the other with remaining size. Now, we take the block with the exact size, erase it from list and give it to the user.

When the user deallocates a block, we traverse the list (remember that the list is ordered), and search its place depending on the block address. Once found, we try to merge the block with adjacent blocks if possible.

To ease implementation, the size of the free memory block is measured in multiples of "basic_size" bytes. The basic size will be the size of the control block aligned to machine most restrictive alignment.

This algorithm is a low size overhead algorithm suitable for simple allocation schemes. This algorithm should only be used when size is a major concern, because the performance of this algorithm suffers when the memory is fragmented. This algorithm has linear allocation and deallocation time, so when the number of allocations is high, the user should use a more performance-friendly algorithm.

In most 32 systems, with 8 byte alignment, "basic_size" is 8 bytes. This means that an allocation request of 1 byte leads to the creation of a 16 byte block, where 8 bytes are available to the user. The allocation of 8 bytes leads also to the same 16 byte block.

This algorithm is an advanced algorithm using red-black trees to sort the free portions of the memory segment by size. This allows logarithmic complexity allocation. Apart from this, a doubly-linked list of all portions of memory (free and allocated) is maintained to allow constant-time access to previous and next blocks when doing merging operations.

The data used to create the red-black tree of free nodes is overwritten by the user since it's no longer used once the memory is allocated. This maintains the memory size overhead down to the doubly linked list overhead, which is pretty small (two pointers). Basically this is the scheme:

rbtree_best_fit memory layout:

   main            allocated block   free block                        allocated block  free block
   header          
  _______________  _______________  _________________________________  _______________  _________________________________   
 |               ||         |     ||         |                 |     ||         |     ||         |                 |     |   
 |  main header  ||next|prev| mem ||next|prev|left|right|parent| mem ||next|prev| mem ||next|prev|left|right|parent| mem |   
 |_______________||_________|_____||_________|_________________|_____||_________|_____||_________|_________________|_____|   

This allocation algorithm is pretty fast and scales well with big shared memory segments and big number of allocations. To form a block a minimum memory size is needed: the sum of the doubly linked list and the red-black tree control data. The size of a block is measured in multiples of the most restrictive alignment value.

In most 32 systems with 8 byte alignment the minimum size of a block is 24 byte. When a block is allocated the control data related to the red black tree is overwritten by the user (because it's only needed for free blocks).

In those systems a 1 byte allocation request means that:

For really small allocations (<= 8 bytes), this algorithm wastes more memory than the simple sequential fit algorithm (8 bytes more). For allocations bigger than 8 bytes the memory overhead is exactly the same. This is the default allocation algorithm in Boost.Interprocess managed memory segments.