Squashed 'third_party/boostorg/container/' content from commit 1ad6431
Change-Id: I7d095db3455264c03446268e5675b926bebedb0a
git-subtree-dir: third_party/boostorg/container
git-subtree-split: 1ad64316a432a7f021b4956acf88abc6aaa8a77e
diff --git a/example/Jamfile.v2 b/example/Jamfile.v2
new file mode 100644
index 0000000..0ba75ac
--- /dev/null
+++ b/example/Jamfile.v2
@@ -0,0 +1,34 @@
+# Boost Container Library Example Jamfile
+
+# (C) Copyright Ion Gaztanaga 2009
+# Use, modification and distribution are subject to the
+# Boost Software License, Version 1.0. (See accompanying file
+# LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+# Adapted from John Maddock's TR1 Jamfile.v2
+# Copyright John Maddock 2005.
+# Use, modification and distribution are subject to the
+# Boost Software License, Version 1.0. (See accompanying file
+# LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+# this rule enumerates through all the sources and invokes
+# the run rule for each source, the result is a list of all
+# the run rules, which we can pass on to the test_suite rule:
+
+rule test_all
+{
+ local all_rules = ;
+
+ for local fileb in [ glob doc_*.cpp ]
+ {
+ all_rules += [ run $(fileb) /boost/container//boost_container
+ : # additional args
+ : # test-files
+ : # requirements
+ ] ;
+ }
+
+ return $(all_rules) ;
+}
+
+test-suite container_example : [ test_all r ] : <threading>multi ;
diff --git a/example/doc_custom_tree.cpp b/example/doc_custom_tree.cpp
new file mode 100644
index 0000000..ad9d9e0
--- /dev/null
+++ b/example/doc_custom_tree.cpp
@@ -0,0 +1,69 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2013-2013. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#include <boost/container/detail/config_begin.hpp>
+#include <boost/container/detail/workaround.hpp>
+//[doc_custom_tree
+#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>, std::allocator<int>, AVLTree> AvlSet;
+
+ //AVLTree based set container without size optimization
+ typedef set<int, std::less<int>, std::allocator<int>, AVLTreeNoSizeOpt> AvlSetNoSizeOpt;
+
+ //Splay tree based multiset container
+ typedef multiset<int, std::less<int>, std::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;
+}
+//]
+#include <boost/container/detail/config_end.hpp>
diff --git a/example/doc_custom_vector.cpp b/example/doc_custom_vector.cpp
new file mode 100644
index 0000000..08dfad7
--- /dev/null
+++ b/example/doc_custom_vector.cpp
@@ -0,0 +1,54 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2013-2013. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+//[doc_custom_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;
+}
+//]
diff --git a/example/doc_emplace.cpp b/example/doc_emplace.cpp
new file mode 100644
index 0000000..2fe4aa0
--- /dev/null
+++ b/example/doc_emplace.cpp
@@ -0,0 +1,44 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2009-2013. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#include <boost/container/detail/config_begin.hpp>
+#include <boost/container/detail/workaround.hpp>
+//[doc_emplace
+#include <boost/container/list.hpp>
+#include <cassert>
+
+//Non-copyable and non-movable class
+class non_copy_movable
+{
+ non_copy_movable(const non_copy_movable &);
+ non_copy_movable& operator=(const non_copy_movable &);
+
+ public:
+ non_copy_movable(int = 0) {}
+};
+
+int main ()
+{
+ using namespace boost::container;
+
+ //Store non-copyable and non-movable objects in a list
+ list<non_copy_movable> l;
+ non_copy_movable ncm;
+
+ //A new element will be built calling non_copy_movable(int) contructor
+ l.emplace(l.begin(), 0);
+ assert(l.size() == 1);
+
+ //A new element will be value initialized
+ l.emplace(l.begin());
+ assert(l.size() == 2);
+ return 0;
+}
+//]
+#include <boost/container/detail/config_end.hpp>
diff --git a/example/doc_extended_allocators.cpp b/example/doc_extended_allocators.cpp
new file mode 100644
index 0000000..0eceba4
--- /dev/null
+++ b/example/doc_extended_allocators.cpp
@@ -0,0 +1,54 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2013-2013. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#include <boost/container/detail/config_begin.hpp>
+#include <boost/container/detail/workaround.hpp>
+//[doc_extended_allocators
+#include <boost/container/vector.hpp>
+#include <boost/container/flat_set.hpp>
+#include <boost/container/list.hpp>
+#include <boost/container/set.hpp>
+
+//"allocator" is a general purpose allocator that can reallocate
+//memory, something useful for vector and flat associative containers
+#include <boost/container/allocator.hpp>
+
+//"adaptive_pool" is a node allocator, specially suited for
+//node-based containers
+#include <boost/container/adaptive_pool.hpp>
+
+int main ()
+{
+ using namespace boost::container;
+
+ //A vector that can reallocate memory to implement faster insertions
+ vector<int, allocator<int> > extended_alloc_vector;
+
+ //A flat set that can reallocate memory to implement faster insertions
+ flat_set<int, std::less<int>, allocator<int> > extended_alloc_flat_set;
+
+ //A list that can manages nodes to implement faster
+ //range insertions and deletions
+ list<int, adaptive_pool<int> > extended_alloc_list;
+
+ //A set that can recycle nodes to implement faster
+ //range insertions and deletions
+ set<int, std::less<int>, adaptive_pool<int> > extended_alloc_set;
+
+ //Now user them as always
+ extended_alloc_vector.push_back(0);
+ extended_alloc_flat_set.insert(0);
+ extended_alloc_list.push_back(0);
+ extended_alloc_set.insert(0);
+
+ //...
+ return 0;
+}
+//]
+#include <boost/container/detail/config_end.hpp>
diff --git a/example/doc_move_containers.cpp b/example/doc_move_containers.cpp
new file mode 100644
index 0000000..e7b09f0
--- /dev/null
+++ b/example/doc_move_containers.cpp
@@ -0,0 +1,54 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2009-2013. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#include <boost/container/detail/config_begin.hpp>
+#include <boost/container/detail/workaround.hpp>
+//[doc_move_containers
+#include <boost/container/vector.hpp>
+#include <boost/move/utility_core.hpp>
+#include <cassert>
+
+//Non-copyable class
+class non_copyable
+{
+ BOOST_MOVABLE_BUT_NOT_COPYABLE(non_copyable)
+
+ public:
+ non_copyable(){}
+ non_copyable(BOOST_RV_REF(non_copyable)) {}
+ non_copyable& operator=(BOOST_RV_REF(non_copyable)) { return *this; }
+};
+
+int main ()
+{
+ using namespace boost::container;
+
+ //Store non-copyable objects in a vector
+ vector<non_copyable> v;
+ non_copyable nc;
+ v.push_back(boost::move(nc));
+ assert(v.size() == 1);
+
+ //Reserve no longer needs copy-constructible
+ v.reserve(100);
+ assert(v.capacity() >= 100);
+
+ //This resize overload only needs movable and default constructible
+ v.resize(200);
+ assert(v.size() == 200);
+
+ //Containers are also movable
+ vector<non_copyable> v_other(boost::move(v));
+ assert(v_other.size() == 200);
+ assert(v.empty());
+
+ return 0;
+}
+//]
+#include <boost/container/detail/config_end.hpp>
diff --git a/example/doc_pmr.cpp b/example/doc_pmr.cpp
new file mode 100644
index 0000000..0d4f5a2
--- /dev/null
+++ b/example/doc_pmr.cpp
@@ -0,0 +1,98 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+//[doc_pmr_ShoppingList_hpp
+//ShoppingList.hpp
+#include <boost/container/pmr/vector.hpp>
+#include <boost/container/pmr/string.hpp>
+
+class ShoppingList
+{
+ // A vector of strings using polymorphic allocators. Every element
+ // of the vector will use the same allocator as the vector itself.
+ boost::container::pmr::vector_of
+ <boost::container::pmr::string>::type m_strvec;
+ //Alternatively in compilers that support template aliases:
+ // boost::container::pmr::vector<boost::container::pmr::string> m_strvec;
+ public:
+
+ // This makes uses_allocator<ShoppingList, memory_resource*>::value true
+ typedef boost::container::pmr::memory_resource* allocator_type;
+
+ // If the allocator is not specified, "m_strvec" uses pmr::get_default_resource().
+ explicit ShoppingList(allocator_type alloc = 0)
+ : m_strvec(alloc) {}
+
+ // Copy constructor. As allocator is not specified,
+ // "m_strvec" uses pmr::get_default_resource().
+ ShoppingList(const ShoppingList& other)
+ : m_strvec(other.m_strvec) {}
+
+ // Copy construct using the given memory_resource.
+ ShoppingList(const ShoppingList& other, allocator_type a)
+ : m_strvec(other.m_strvec, a) {}
+
+ allocator_type get_allocator() const
+ { return m_strvec.get_allocator().resource(); }
+
+ void add_item(const char *item)
+ { m_strvec.emplace_back(item); }
+
+ //...
+};
+
+//]]
+
+//[doc_pmr_main_cpp
+
+//=#include "ShoppingList.hpp"
+#include <cassert>
+#include <boost/container/pmr/list.hpp>
+#include <boost/container/pmr/monotonic_buffer_resource.hpp>
+
+void processShoppingList(const ShoppingList&)
+{ /**/ }
+
+int main()
+{
+ using namespace boost::container;
+ //All memory needed by folder and its contained objects will
+ //be allocated from the default memory resource (usually new/delete)
+ pmr::list_of<ShoppingList>::type folder; // Default allocator resource
+ //Alternatively in compilers that support template aliases:
+ // boost::container::pmr::list<ShoppingList> folder;
+ {
+ char buffer[1024];
+ pmr::monotonic_buffer_resource buf_rsrc(&buffer, 1024);
+
+ //All memory needed by temporaryShoppingList will be allocated
+ //from the local buffer (speeds up "processShoppingList")
+ ShoppingList temporaryShoppingList(&buf_rsrc);
+ assert(&buf_rsrc == temporaryShoppingList.get_allocator());
+
+ //list nodes, and strings "salt" and "pepper" will be allocated
+ //in the stack thanks to "monotonic_buffer_resource".
+ temporaryShoppingList.add_item("salt");
+ temporaryShoppingList.add_item("pepper");
+ //...
+
+ //All modifications and additions to "temporaryShoppingList"
+ //will use memory from "buffer" until it's exhausted.
+ processShoppingList(temporaryShoppingList);
+
+ //Processing done, now insert it in "folder",
+ //which uses the default memory resource
+ folder.push_back(temporaryShoppingList);
+ assert(pmr::get_default_resource() == folder.back().get_allocator());
+ //temporaryShoppingList, buf_rsrc, and buffer go out of scope
+ }
+ return 0;
+}
+
+//]
diff --git a/example/doc_recursive_containers.cpp b/example/doc_recursive_containers.cpp
new file mode 100644
index 0000000..6a1746a
--- /dev/null
+++ b/example/doc_recursive_containers.cpp
@@ -0,0 +1,73 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2009-2013. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#include <boost/container/detail/config_begin.hpp>
+#include <boost/container/detail/workaround.hpp>
+//[doc_recursive_containers
+#include <boost/container/vector.hpp>
+#include <boost/container/stable_vector.hpp>
+#include <boost/container/deque.hpp>
+#include <boost/container/list.hpp>
+#include <boost/container/map.hpp>
+#include <boost/container/string.hpp>
+
+using namespace boost::container;
+
+struct data
+{
+ int i_;
+ //A vector holding still undefined class 'data'
+ vector<data> v_;
+ vector<data>::iterator vi_;
+ //A stable_vector holding still undefined class 'data'
+ stable_vector<data> sv_;
+ stable_vector<data>::iterator svi_;
+ //A stable_vector holding still undefined class 'data'
+ deque<data> d_;
+ deque<data>::iterator di_;
+ //A list holding still undefined 'data'
+ list<data> l_;
+ list<data>::iterator li_;
+ //A map holding still undefined 'data'
+ map<data, data> m_;
+ map<data, data>::iterator mi_;
+
+ friend bool operator <(const data &l, const data &r)
+ { return l.i_ < r.i_; }
+};
+
+struct tree_node
+{
+ string name;
+ string value;
+
+ //children nodes of this node
+ list<tree_node> children_;
+ list<tree_node>::iterator selected_child_;
+};
+
+
+
+int main()
+{
+ //a container holding a recursive data type
+ stable_vector<data> sv;
+ sv.resize(100);
+
+ //Let's build a tree based in
+ //a recursive data type
+ tree_node root;
+ root.name = "root";
+ root.value = "root_value";
+ root.children_.resize(7);
+ root.selected_child_ = root.children_.begin();
+ return 0;
+}
+//]
+#include <boost/container/detail/config_end.hpp>
diff --git a/example/doc_type_erasure.cpp b/example/doc_type_erasure.cpp
new file mode 100644
index 0000000..e776062
--- /dev/null
+++ b/example/doc_type_erasure.cpp
@@ -0,0 +1,91 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2009-2013. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#include <boost/container/detail/config_begin.hpp>
+#include <boost/container/detail/workaround.hpp>
+//[doc_type_erasure_MyClassHolder_h
+#include <boost/container/vector.hpp>
+
+//MyClassHolder.h
+
+//We don't need to include "MyClass.h"
+//to store vector<MyClass>
+class MyClass;
+
+class MyClassHolder
+{
+ public:
+
+ void AddNewObject(const MyClass &o);
+ const MyClass & GetLastObject() const;
+
+ private:
+ ::boost::container::vector<MyClass> vector_;
+};
+
+//]
+
+//[doc_type_erasure_MyClass_h
+
+//MyClass.h
+
+class MyClass
+{
+ private:
+ int value_;
+
+ public:
+ MyClass(int val = 0) : value_(val){}
+
+ friend bool operator==(const MyClass &l, const MyClass &r)
+ { return l.value_ == r.value_; }
+ //...
+};
+
+//]
+
+
+
+//[doc_type_erasure_main_cpp
+
+//Main.cpp
+
+//=#include "MyClassHolder.h"
+//=#include "MyClass.h"
+
+#include <cassert>
+
+int main()
+{
+ MyClass mc(7);
+ MyClassHolder myclassholder;
+ myclassholder.AddNewObject(mc);
+ return myclassholder.GetLastObject() == mc ? 0 : 1;
+}
+//]
+
+//[doc_type_erasure_MyClassHolder_cpp
+
+//MyClassHolder.cpp
+
+//=#include "MyClassHolder.h"
+
+//In the implementation MyClass must be a complete
+//type so we include the appropriate header
+//=#include "MyClass.h"
+
+void MyClassHolder::AddNewObject(const MyClass &o)
+{ vector_.push_back(o); }
+
+const MyClass & MyClassHolder::GetLastObject() const
+{ return vector_.back(); }
+
+//]
+
+#include <boost/container/detail/config_end.hpp>