Boost C++ Libraries

set, multiset, map and multimap associative containers are implemented as binary search trees which offer the needed complexity and stability guarantees required by the C++ standard for associative containers.

Boost.Container offers the possibility to configure at compile time some parameters of the binary search tree implementation. This configuration is passed as the last template parameter and defined using the utility class tree_assoc_options. The following parameters can be configured:

See the following example to see how tree_assoc_options can be used to customize these containers:

#include <boost/container/set.hpp>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

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

   //First define several options
   //

   //This option specifies an AVL tree based associative container
   typedef tree_assoc_options< tree_type<avl_tree> >::type AVLTree;

   //This option specifies an AVL tree based associative container
   //disabling node size optimization.
   typedef tree_assoc_options< tree_type<avl_tree>
                             , optimize_size<false> >::type AVLTreeNoSizeOpt;

   //This option specifies an Splay tree based associative container
   typedef tree_assoc_options< tree_type<splay_tree> >::type SplayTree;

   //Now define new tree-based associative containers
   //

   //AVLTree based set container
   typedef set<int, std::less<int>, new_allocator<int>, AVLTree> AvlSet;

   //AVLTree based set container without size optimization
   typedef set<int, std::less<int>, new_allocator<int>, AVLTreeNoSizeOpt> AvlSetNoSizeOpt;

   //Splay tree based multiset container
   typedef multiset<int, std::less<int>, new_allocator<int>, SplayTree> SplayMultiset;

   //Use them
   //
   AvlSet avl_set;
   avl_set.insert(0);
   assert(avl_set.find(0) != avl_set.end());

   AvlSetNoSizeOpt avl_set_no_szopt;
   avl_set_no_szopt.insert(1);
   avl_set_no_szopt.insert(1);
   assert(avl_set_no_szopt.count(1) == 1);

   SplayMultiset splay_mset;
   splay_mset.insert(2);
   splay_mset.insert(2);
   assert(splay_mset.count(2) == 2);
   return 0;
}

The configuration for vector is passed as the last template parameter and defined using the utility class vector_options. The following parameters can be configured:

See the following example to see how vector_options can be used to customize vector container:

#include <boost/container/vector.hpp>
#include <boost/static_assert.hpp>
#include <boost/core/no_exceptions_support.hpp>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

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

   //This option specifies that a vector that will use "unsigned char" as
   //the type to store capacity or size internally.
   typedef vector_options< stored_size<unsigned char> >::type size_option_t;

   //Size-optimized vector is smaller than the default one.
   typedef vector<int, new_allocator<int>, size_option_t > size_optimized_vector_t;
   BOOST_STATIC_ASSERT(( sizeof(size_optimized_vector_t) < sizeof(vector<int>) ));

   //Requesting capacity for more elements than representable by "unsigned char"
   //is an error in the size optimized vector.
   bool exception_thrown = false;

   try       { size_optimized_vector_t v(256); }
   catch(...){ exception_thrown = true;        }

   assert(exception_thrown == true);

   //This option specifies that a vector will increase its capacity 50%
   //each time the previous capacity was exhausted.
   typedef vector_options< growth_factor<growth_factor_50> >::type growth_50_option_t;

   //Fill the vector until full capacity is reached
   vector<int, new_allocator<int>, growth_50_option_t > growth_50_vector(5, 0);
   const std::size_t old_cap = growth_50_vector.capacity();
   growth_50_vector.resize(old_cap);

   //Now insert an additional item and check the new buffer is 50% bigger
   growth_50_vector.push_back(1);
   assert(growth_50_vector.capacity() == old_cap*3/2);

   return 0;
}

The configuration for deque is passed as the last template parameter and defined using the utility class deque_options. The following parameters can be configured:

Parameters that control the size of deque's 'block' (deque allocates contiguous chunks of elements, called 'blocks'). Only one of these paratemers can be specified:

See the following example to see how deque_options can be used to customize deque container:

#include <boost/container/deque.hpp>
#include <boost/static_assert.hpp>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

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

   //This option specifies the desired block size for deque
   typedef deque_options< block_size<128u> >::type block_128_option_t;

   //This deque will allocate blocks of 128 elements
   typedef deque<int, void, block_128_option_t > block_128_deque_t;
   assert(block_128_deque_t::get_block_size() == 128u);

   //This option specifies the maximum block size for deque
   //in bytes
   typedef deque_options< block_bytes<1024u> >::type block_1024_bytes_option_t;

   //This deque will allocate blocks of 1024 bytes
   typedef deque<int, void, block_1024_bytes_option_t > block_1024_bytes_deque_t;
   assert(block_1024_bytes_deque_t::get_block_size() == 1024u/sizeof(int));

   return 0;
}

The configuration for static_vector is passed as the last template parameter and defined using the utility class static_vector_options. The following parameters can be configured:

See the following example to see how static_vector_options can be used to customize static_vector container:

#include <boost/container/static_vector.hpp>
#include <boost/static_assert.hpp>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

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

   //This option specifies the desired alignment for value_type
   typedef static_vector_options< inplace_alignment<16u> >::type alignment_16_option_t;

   //Check 16 byte alignment option
   static_vector<int, 10, alignment_16_option_t > sv;
   assert(((std::size_t)sv.data() % 16u) == 0);

   //This static_vector won't throw on overflow, for maximum performance
   typedef static_vector_options< throw_on_overflow<false> >::type no_throw_options_t;

   //Create static_vector with no throw on overflow
   static_vector<int, 10, no_throw_options_t > sv2;

   return 0;
}

The configuration for small_vector is passed as the last template parameter and defined using the utility class small_vector_options. The following parameters can be configured:

See the following example to see how small_vector_options can be used to customize small_vector container:

#include <boost/container/small_vector.hpp>
#include <boost/static_assert.hpp>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

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

   //This option specifies the desired alignment for the internal value_type
   typedef small_vector_options< inplace_alignment<16u> >::type alignment_16_option_t;

   //Check 16 byte alignment option
   small_vector<int, 10, void, alignment_16_option_t > sv;
   assert(((std::size_t)sv.data() % 16u) == 0);


   //This option specifies that a vector will increase its capacity 50%
   //each time the previous capacity was exhausted.
   typedef small_vector_options< growth_factor<growth_factor_50> >::type growth_50_option_t;

   //Fill the vector until full capacity is reached
   small_vector<int, 10, void, growth_50_option_t > growth_50_vector(10, 0);
   const std::size_t old_cap = growth_50_vector.capacity();
   growth_50_vector.resize(old_cap);

   //Now insert an additional item and check the new buffer is 50% bigger
   growth_50_vector.push_back(1);
   assert(growth_50_vector.capacity() == old_cap*3/2);

   return 0;
}