Home | Libraries | People | FAQ | More |
Boost.Container offers the possibility to configure at compile time some parameters of several containers, apart from the stored type and the allocator. This configuration is passed as the last template parameter and defined using the utility classes. The following containers can receive useful configuration options:
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:
tree_type
).
By default these containers use a red-black tree but the user can use
other tree types:
optimize_size
).
By default this option is activated and is only meaningful to red-black
and avl trees (in other cases, this option will be ignored). This option
will try to put rebalancing metadata inside the "parent" pointer
of the node if the pointer type has enough alignment. Usually, due to
alignment issues, the metadata uses the size of a pointer yielding to
four pointer size overhead per node, whereas activating this option usually
leads to 3 pointer size overhead. Although some mask operations must
be performed to extract data from this special "parent" pointer,
in several systems this option also improves performance due to the improved
cache usage produced by the node size reduction.
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:
growth_factor
:
the growth policy of the vector. The rate at which the capacity of a
vector grows is implementation dependent and implementations choose exponential
growth in order to meet the amortized constant time requirement for push_back.
A higher growth factor will make it faster as it will require less data
movement, but it will have a greater memory impact (on average, more
memory will be unused). A user can provide a custom implementation of
the growth factor and some predefined policies are available: growth_factor_50
,
growth_factor_60
(usually the default) and growth_factor_100
.
stored_size
:
the type that will be used to store size-related parameters inside of
the vector. Sometimes, when the maximum capacity to be used is much less
than the theoretical maximum that a vector can hold, it's interesting
to use smaller unsigned integer types to represent size()
and capacity()
inside vector, so that the size of
an empty vector is minimized and cache performance might be improved.
See stored_size
for more details.
See the following example to see how vector_options
can be used to customize vector
:
#include <boost/container/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 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 static_vector
is passed as the last template parameter and defined using the utility class
static_vector_options
.
The following parameters can be configured:
inplace_alignment
:
the minimum alignment (in bytes) that the stored value type needs. This
option allows static vectors that need non-default alignments, e.g.,
to be used in SIMD operations.
throw_on_overflow
:
A boolean that specifies if the container should throw an exception when
the compile-time capacity is not enough to hold the requesteed number
of objects. When "false", if the capacit is overflowed, the
implementation calls to BOOST_ASSERT and if that assertion does not throw
or abort, undefined behavior is triggered.
See the following example to see how static_vector_options
can be used to customize static_vector
:
#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:
inplace_alignment
:
the minimum alignment (in bytes) for the in-place storage used to build
the "small" number of elements. The alignment
of the dynamic memory must be provided by the allocator and it is not
affected by this option.
growth_factor
:
the growth policy of the vector. The rate at which the capacity of a
vector grows is implementation dependent and implementations choose exponential
growth in order to meet the amortized constant time requirement for push_back.
A higher growth factor will make it faster as it will require less data
movement, but it will have a greater memory impact (on average, more
memory will be unused). A user can provide a custom implementation of
the growth factor and some predefined policies are available: growth_factor_50
,
growth_factor_60
and growth_factor_100
.
See the following example to see how small_vector_options
can be used to customize small_vector
:
#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; }
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:
block_bytes
:
the number of bytes deque will allocate for store elements contiguously:
deque::get_block_size()
will return aproximately block_bytes/sizeof(value_type)
. A value of zero means the default value.
block_size
:
the number of elements deque will allocate contiguously. If this option
is specified, deque::get_block_size()
will return the specified block_size
.
A value of zero means the default value.
See the following example to see how deque_options
can be used to customize deque
:
#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 devector
is passed as the last template parameter and defined using the utility class
devector_options
.
The following parameters can be configured:
growth_factor
:
the growth policy of the devector. The rate at which the capacity of
a devector grows is implementation dependent and implementations choose
exponential growth in order to meet the amortized constant time requirement
for push_back. A higher growth factor will make it faster as it will
require less data movement, but it will have a greater memory impact
(on average, more memory will be unused). A user can provide a custom
implementation of the growth factor and some predefined policies are
available: growth_factor_50
,
growth_factor_60
(usually the default) and growth_factor_100
.
stored_size
:
the type that will be used to store size-related parameters inside of
the devector. Sometimes, when the maximum capacity to be used is much
less than the theoretical maximum that a devector can hold, it's interesting
to use smaller unsigned integer types to represent size()
and capacity()
inside devector, so that the size of
an empty devector is minimized and cache performance might be improved.
See stored_size
for more details.
relocate_on_XX
:
load factor limit that will determine if new memory should be allocated
or elements should relocated inside existing memory, when the free space
is exhausted at one end of the container.
See the following example to see how devector_options
can be used to customize devector
:
#include <boost/container/devector.hpp> #include <boost/static_assert.hpp> //Make sure assertions are active #ifdef NDEBUG #undef NDEBUG #endif #include <cassert> int main () { using namespace boost::container; //////////////////////////////////////////////// // 'stored_size' option //////////////////////////////////////////////// //Specify that a devector will use "unsigned char" as the type to store size/capacity typedef devector_options< stored_size<unsigned char> >::type size_option_t; //Size-optimized devector is smaller than the default one. typedef devector<int, new_allocator<int>, size_option_t > size_optimized_devector_t; BOOST_STATIC_ASSERT(( sizeof(size_optimized_devector_t) < sizeof(devector<int>) )); //Requesting capacity for more elements than representable by "unsigned char" is an error bool exception_thrown = false; try { size_optimized_devector_t v(256); } catch(...){ exception_thrown = true; } assert(exception_thrown == true); //////////////////////////////////////////////// // 'growth_factor' option //////////////////////////////////////////////// //Specify that a devector will increase its capacity 50% when reallocating typedef devector_options< growth_factor<growth_factor_50> >::type growth_50_option_t; //Fill the devector until full capacity is reached devector<int, new_allocator<int>, growth_50_option_t > growth_50_dv(5, 0); std::size_t old_cap = growth_50_dv.capacity(); growth_50_dv.resize(old_cap); //Now insert an additional item and check the new buffer is 50% bigger growth_50_dv.push_back(1); assert(growth_50_dv.capacity() == old_cap*3/2); //////////////////////////////////////////////// // 'relocate_on' option //////////////////////////////////////////////// //Specifies that a devector will not reallocate but relocate elements if the free space //at one end is exhausted and the total load factor is below the 66% threshold. typedef devector_options< relocate_on_66 >::type relocation_66_option_t; //Configure devector to have equal free space at both ends devector<int, new_allocator<int>, relocation_66_option_t > reloc_66_dv (16u, 16u, reserve_only_tag_t()); old_cap = reloc_66_dv.capacity(); const std::size_t front_free_cap = reloc_66_dv.front_free_capacity(); //Fill vector at the back end while (reloc_66_dv.back_free_capacity() > 0) reloc_66_dv.push_back(0); //Front free capacity is intact assert(reloc_66_dv.front_free_capacity() == front_free_cap); //Now insert new element, values should relocated to the middle as the //load factor is near 50% reloc_66_dv.push_back(0); assert(reloc_66_dv.capacity() == old_cap); assert(reloc_66_dv.front_free_capacity() < front_free_cap); //Fill the back end again while (reloc_66_dv.back_free_capacity() > 0) reloc_66_dv.push_back(1); //New insertion should reallocate as load factor is higher than 66% reloc_66_dv.push_back(-1); assert(reloc_66_dv.capacity() > old_cap); return 0; }