Squashed 'third_party/boostorg/multi_index/' content from commit d95a949
Change-Id: Ie67c2d797c11dc122c7f11e767e81691bf2191a4
git-subtree-dir: third_party/boostorg/multi_index
git-subtree-split: d95a94942b918140e565feb99ed36ea97c30084e
diff --git a/example/Jamfile.v2 b/example/Jamfile.v2
new file mode 100644
index 0000000..a4dc9c3
--- /dev/null
+++ b/example/Jamfile.v2
@@ -0,0 +1,69 @@
+# Boost.MultiIndex examples Jamfile
+#
+# Copyright 2003-2007 Joaquín M López Muñoz.
+# 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/multi_index for library home page.
+
+exe basic
+ : basic.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe bimap
+ : bimap.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe complex_structs
+ : complex_structs.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe composite_keys
+ : composite_keys.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe fun_key
+ : fun_key.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe hashed
+ : hashed.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe ip_allocator
+ : ip_allocator.cpp
+ : <include>$(BOOST_ROOT) <threading>multi
+ ;
+
+exe non_default_ctor
+ : non_default_ctor.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe random_access
+ : random_access.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe rearrange
+ : rearrange.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe sequenced
+ : sequenced.cpp
+ : <include>$(BOOST_ROOT)
+ ;
+
+exe serialization
+ : serialization.cpp
+ /boost/serialization//boost_serialization
+ : <include>$(BOOST_ROOT)
+ ;
diff --git a/example/basic.cpp b/example/basic.cpp
new file mode 100644
index 0000000..f7c46ce
--- /dev/null
+++ b/example/basic.cpp
@@ -0,0 +1,119 @@
+/* Boost.MultiIndex basic example.
+ *
+ * Copyright 2003-2013 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <algorithm>
+#include <iostream>
+#include <iterator>
+#include <string>
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+
+/* an employee record holds its ID, name and age */
+
+struct employee
+{
+ int id;
+ std::string name;
+ int age;
+
+ employee(int id_,std::string name_,int age_):id(id_),name(name_),age(age_){}
+
+ friend std::ostream& operator<<(std::ostream& os,const employee& e)
+ {
+ os<<e.id<<" "<<e.name<<" "<<e.age<<std::endl;
+ return os;
+ }
+};
+
+/* tags for accessing the corresponding indices of employee_set */
+
+struct id{};
+struct name{};
+struct age{};
+
+/* see Compiler specifics: Use of member_offset for info on
+ * BOOST_MULTI_INDEX_MEMBER
+ */
+
+/* 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 multi_index_container<
+ employee,
+ indexed_by<
+ ordered_unique<
+ tag<id>, BOOST_MULTI_INDEX_MEMBER(employee,int,id)>,
+ ordered_non_unique<
+ tag<name>,BOOST_MULTI_INDEX_MEMBER(employee,std::string,name)>,
+ ordered_non_unique<
+ tag<age>, BOOST_MULTI_INDEX_MEMBER(employee,int,age)> >
+> employee_set;
+
+template<typename Tag,typename MultiIndexContainer>
+void print_out_by(const MultiIndexContainer& s)
+{
+ /* obtain a reference to the index tagged by Tag */
+
+ const typename boost::multi_index::index<MultiIndexContainer,Tag>::type& i=
+ get<Tag>(s);
+
+ typedef typename MultiIndexContainer::value_type value_type;
+
+ /* dump the elements of the index to cout */
+
+ std::copy(i.begin(),i.end(),std::ostream_iterator<value_type>(std::cout));
+}
+
+
+int main()
+{
+ employee_set es;
+
+ es.insert(employee(0,"Joe",31));
+ es.insert(employee(1,"Robert",27));
+ es.insert(employee(2,"John",40));
+
+ /* next insertion will fail, as there is an employee with
+ * the same ID
+ */
+
+ es.insert(employee(2,"Aristotle",2387));
+
+ es.insert(employee(3,"Albert",20));
+ es.insert(employee(4,"John",57));
+
+ /* list the employees sorted by ID, name and age */
+
+ std::cout<<"by ID"<<std::endl;
+ print_out_by<id>(es);
+ std::cout<<std::endl;
+
+ std::cout<<"by name"<<std::endl;
+ print_out_by<name>(es);
+ std::cout<<std::endl;
+
+ std::cout<<"by age"<<std::endl;
+ print_out_by<age>(es);
+ std::cout<<std::endl;
+
+ return 0;
+}
diff --git a/example/bimap.cpp b/example/bimap.cpp
new file mode 100644
index 0000000..aac99d0
--- /dev/null
+++ b/example/bimap.cpp
@@ -0,0 +1,149 @@
+/* Boost.MultiIndex example of a bidirectional map.
+ *
+ * Copyright 2003-2009 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <iostream>
+#include <string>
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+
+/* tags for accessing both sides of a bidirectional map */
+
+struct from{};
+struct to{};
+
+/* The class template bidirectional_map wraps the specification
+ * of a bidirectional map based on multi_index_container.
+ */
+
+template<typename FromType,typename ToType>
+struct bidirectional_map
+{
+ struct value_type
+ {
+ value_type(const FromType& first_,const ToType& second_):
+ first(first_),second(second_)
+ {}
+
+ FromType first;
+ ToType second;
+ };
+
+#if defined(BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS) ||\
+ defined(BOOST_MSVC)&&(BOOST_MSVC<1300) ||\
+ defined(BOOST_INTEL_CXX_VERSION)&&defined(_MSC_VER)&&\
+ (BOOST_INTEL_CXX_VERSION<=700)
+
+/* see Compiler specifics: Use of member_offset for info on member<> and
+ * member_offset<>
+ */
+
+ BOOST_STATIC_CONSTANT(unsigned,from_offset=offsetof(value_type,first));
+ BOOST_STATIC_CONSTANT(unsigned,to_offset =offsetof(value_type,second));
+
+ typedef multi_index_container<
+ value_type,
+ indexed_by<
+ ordered_unique<
+ tag<from>,member_offset<value_type,FromType,from_offset> >,
+ ordered_unique<
+ tag<to>, member_offset<value_type,ToType,to_offset> >
+ >
+ > type;
+
+#else
+
+ /* A bidirectional map can be simulated as a multi_index_container
+ * of pairs of (FromType,ToType) with two unique indices, one
+ * for each member of the pair.
+ */
+
+ typedef multi_index_container<
+ value_type,
+ indexed_by<
+ ordered_unique<
+ tag<from>,member<value_type,FromType,&value_type::first> >,
+ ordered_unique<
+ tag<to>, member<value_type,ToType,&value_type::second> >
+ >
+ > type;
+
+#endif
+};
+
+/* a dictionary is a bidirectional map from strings to strings */
+
+typedef bidirectional_map<std::string,std::string>::type dictionary;
+
+int main()
+{
+ dictionary d;
+
+ /* Fill up our microdictionary. first members Spanish, second members
+ * English.
+ */
+
+ d.insert(dictionary::value_type("hola","hello"));
+ d.insert(dictionary::value_type("adios","goodbye"));
+ d.insert(dictionary::value_type("rosa","rose"));
+ d.insert(dictionary::value_type("mesa","table"));
+
+
+ std::cout<<"enter a word"<<std::endl;
+ std::string word;
+ std::getline(std::cin,word);
+
+#if defined(BOOST_NO_MEMBER_TEMPLATES) /* use global get<> and family instead */
+
+ dictionary::iterator it=get<from>(d).find(word);
+ if(it!=d.end()){
+ std::cout<<word<<" is said "<<it->second<<" in English"<<std::endl;
+ }
+ else{
+ nth_index<dictionary,1>::type::iterator it2=get<1>(d).find(word);
+ if(it2!=get<1>(d).end()){
+ std::cout<<word<<" is said "<<it2->first<<" in Spanish"<<std::endl;
+ }
+ else std::cout<<"No such word in the dictionary"<<std::endl;
+ }
+
+#else
+
+ /* search the queried word on the from index (Spanish) */
+
+ dictionary::iterator it=d.get<from>().find(word);
+ if(it!=d.end()){ /* found */
+
+ /* the second part of the element is the equivalent in English */
+
+ std::cout<<word<<" is said "<<it->second<<" in English"<<std::endl;
+ }
+ else{
+ /* word not found in Spanish, try our luck in English */
+
+ dictionary::index<to>::type::iterator it2=d.get<to>().find(word);
+ if(it2!=d.get<to>().end()){
+ std::cout<<word<<" is said "<<it2->first<<" in Spanish"<<std::endl;
+ }
+ else std::cout<<"No such word in the dictionary"<<std::endl;
+ }
+
+#endif
+
+ return 0;
+}
diff --git a/example/complex_structs.cpp b/example/complex_structs.cpp
new file mode 100644
index 0000000..70eb78b
--- /dev/null
+++ b/example/complex_structs.cpp
@@ -0,0 +1,315 @@
+/* Boost.MultiIndex example: complex searches and foreign keys.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <iostream>
+#include <string>
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+
+/* This small utility that cascades two key extractors will be
+ * used througout the example.
+ */
+
+template<class KeyExtractor1,class KeyExtractor2>
+struct key_from_key
+{
+public:
+ typedef typename KeyExtractor1::result_type result_type;
+
+ key_from_key(
+ const KeyExtractor1& key1_=KeyExtractor1(),
+ const KeyExtractor2& key2_=KeyExtractor2()):
+ key1(key1_),key2(key2_)
+ {}
+
+ template<typename Arg>
+ result_type operator()(Arg& arg)const
+ {
+ return key1(key2(arg));
+ }
+
+private:
+ KeyExtractor1 key1;
+ KeyExtractor2 key2;
+};
+
+/* tags for accessing several indices defined below */
+
+struct model{};
+struct manufacturer{};
+struct price{};
+
+/* a manufacturer struct just holds the name of the manufacturer */
+
+struct car_manufacturer
+{
+ std::string name;
+
+ car_manufacturer(const std::string& name_):name(name_){}
+};
+
+/* car_model holds the model of car, its price and a pointer to the
+ * manufacturer. The pointer thing eliminates duplication of the same
+ * data among cars of the same manufacturer.
+ */
+
+struct car_model
+{
+ std::string model;
+ const car_manufacturer* manufacturer;
+ int price;
+
+ car_model(
+ const std::string& model_,const car_manufacturer* manufacturer_,int price_):
+ model(model_),manufacturer(manufacturer_),price(price_)
+ {}
+
+ friend std::ostream& operator<<(std::ostream& os,const car_model& c)
+ {
+ os<<c.manufacturer->name<<" "<<c.model<<" $"<<c.price<<std::endl;
+ return os;
+ }
+};
+
+/* see Compiler specifics: Use of member_offset for info on
+ * BOOST_MULTI_INDEX_MEMBER
+ */
+
+/* Car manufacturers are stored in a multi_index_container with one single
+ * index on the name member. This is functionally equivalent to an std::set,
+ * though in this latter case we woud have to define a non-default comparison
+ * predicate (with multi_index_container, member<> does the work for us.)
+ */
+
+typedef multi_index_container<
+ car_manufacturer,
+ indexed_by<
+ ordered_unique<
+ BOOST_MULTI_INDEX_MEMBER(car_manufacturer,std::string,name)
+ >
+ >
+> car_manufacturer_table;
+
+/* Define a multi_index_container of car_models with following indices:
+ * - a unique index sorted by car_model::model,
+ * - a non-unique index sorted by car_model::manufacturer; note the
+ * non-standard manufacturer_extractor used.
+ * - a non-unique index sorted by car_model::price.
+ */
+
+typedef multi_index_container<
+ car_model,
+ indexed_by<
+ ordered_unique<
+ tag<model>,BOOST_MULTI_INDEX_MEMBER(car_model,std::string,model)
+ >,
+ ordered_non_unique<
+ tag<manufacturer>,
+ key_from_key<
+ BOOST_MULTI_INDEX_MEMBER(car_manufacturer,const std::string,name),
+ BOOST_MULTI_INDEX_MEMBER(
+ car_model,const car_manufacturer *,manufacturer)
+ >
+ >,
+ ordered_non_unique<
+ tag<price>,BOOST_MULTI_INDEX_MEMBER(car_model,int,price)
+ >
+ >
+> car_table;
+
+/* We call a *view* to a multi_index_container storing pointers instead of
+ * actual objects. These views are used in the complex search performed
+ * in the program. Resorting to multi_index of pointers eliminates
+ * unnecessary copying of objects, and provides us with an opportunity
+ * to show how BOOST_MULTI_INDEX_MEMBER can be used with pointer
+ * type elements.
+ * car_table_price_view indexes (pointers to) car_models by price.
+ */
+
+typedef multi_index_container<
+ const car_model*,
+ indexed_by<
+ ordered_non_unique<BOOST_MULTI_INDEX_MEMBER(car_model,const int,price)>
+ >
+> car_table_price_view;
+
+/* car_table_manufacturer_view indexes (pointers to) car_models by
+ * manufacturer
+ */
+
+typedef multi_index_container<
+ const car_model*,
+ indexed_by<
+ ordered_non_unique<
+ key_from_key<
+ BOOST_MULTI_INDEX_MEMBER(car_manufacturer,const std::string,name),
+ BOOST_MULTI_INDEX_MEMBER(
+ car_model,const car_manufacturer * const,manufacturer)
+ >
+ >
+ >
+> car_table_manufacturer_view;
+
+int main()
+{
+ car_manufacturer_table cmt;
+
+ /* Fill the car_manufacturer table and keep pointers to the
+ * elements inserted.
+ */
+
+ const car_manufacturer * cadillac=
+ &*(cmt.insert(car_manufacturer("Cadillac")).first);
+ const car_manufacturer * ford =
+ &*(cmt.insert(car_manufacturer("Ford")).first);
+ const car_manufacturer * bmw =
+ &*(cmt.insert(car_manufacturer("BMW")).first);
+ const car_manufacturer * audi =
+ &*(cmt.insert(car_manufacturer("Audi")).first);
+
+ car_table ct;
+
+ /* Fill the car_model_table. We use the previously initialized
+ * pointers to the elements of cmt.
+ */
+
+ ct.insert(car_model("XLR",cadillac,76200));
+ ct.insert(car_model("SRX",cadillac,38690));
+ ct.insert(car_model("CTS",cadillac,30695));
+ ct.insert(car_model("Escalade",cadillac,54770));
+ ct.insert(car_model("ESV",cadillac,57195));
+ ct.insert(car_model("EXT",cadillac,52045));
+ ct.insert(car_model("Deville",cadillac,45195));
+ ct.insert(car_model("Seville",cadillac,46330));
+
+ ct.insert(car_model("ZX2",ford,15355));
+ ct.insert(car_model("Thunderbird",ford,43995));
+ ct.insert(car_model("Windstar",ford,35510));
+ ct.insert(car_model("Focus",ford,19630));
+ ct.insert(car_model("Taurus",ford,24290));
+ ct.insert(car_model("Mustang",ford,39900));
+ ct.insert(car_model("Crown Victoria",ford,30370));
+
+ ct.insert(car_model("325i",bmw,27800));
+ ct.insert(car_model("545i",bmw,54300));
+ ct.insert(car_model("745i",bmw,68500));
+ ct.insert(car_model("M3 coupe",bmw,46500));
+ ct.insert(car_model("Z4 roadster 3.0i",bmw,40250));
+ ct.insert(car_model("X5 4.4i",bmw,49950));
+
+ ct.insert(car_model("A4 1.8T",audi,25940));
+ ct.insert(car_model("TT Coupe",audi,33940));
+ ct.insert(car_model("A6 3.0",audi,36640));
+ ct.insert(car_model("Allroad quattro 2.7T",audi,40640));
+ ct.insert(car_model("A8 L",audi,69190));
+
+ std::cout<<"enter a car manufacturer"<<std::endl;
+ std::string cm;
+ std::getline(std::cin,cm);
+
+ /* check for manufacturer */
+
+ car_manufacturer_table::iterator icm=cmt.find(cm);
+
+ if(icm==cmt.end()){
+ std::cout<<"no such manufacturer in the table"<<std::endl;
+ return 0;
+ }
+
+ std::cout<<"enter a minimum price"<<std::endl;
+ int min_price;
+ std::cin>>min_price;
+ std::cout<<"enter a maximum price"<<std::endl;
+ int max_price;
+ std::cin>>max_price;
+
+ {
+ /* method 1 */
+
+ /* find all the cars for the manufacturer given */
+
+ boost::multi_index::index<car_table,manufacturer>::type::iterator ic0,ic1;
+ boost::tuples::tie(ic0,ic1)=get<manufacturer>(ct).equal_range(cm);
+
+ /* construct a view (indexed by price) with these */
+
+ car_table_price_view ctpv;
+ while(ic0!=ic1){
+ ctpv.insert(&*ic0);
+ ++ic0;
+ }
+
+ /* select the cars in the range given */
+
+ car_table_price_view::iterator ictpv0=ctpv.lower_bound(min_price);
+ car_table_price_view::iterator ictpv1=ctpv.upper_bound(max_price);
+ if(ictpv0==ictpv1){
+ std::cout<<"no cars in the range given"<<std::endl;
+ return 0;
+ }
+
+ /* list them */
+
+ std::cout<<"listing by method 1"<<std::endl;
+ while(ictpv0!=ictpv1){
+ std::cout<<**ictpv0;
+ ++ictpv0;
+ }
+ std::cout<<std::endl;
+ }
+
+ {
+ /* method 2 will give the same results */
+
+ /* find the cars in the range given */
+
+ boost::multi_index::index<car_table,price>::type::iterator ic0,ic1;
+ ic0=get<price>(ct).lower_bound(min_price);
+ ic1=get<price>(ct).upper_bound(max_price);
+
+ /* construct a view with these */
+
+ car_table_manufacturer_view ctmv;
+ while(ic0!=ic1){
+ ctmv.insert(&*ic0);
+ ++ic0;
+ }
+
+ /* select the cars with given manufacturer */
+
+ car_table_manufacturer_view::iterator ictmv0,ictmv1;
+ boost::tuples::tie(ictmv0,ictmv1)=ctmv.equal_range(cm);
+ if(ictmv0==ictmv1){
+ std::cout<<"no cars in the range given"<<std::endl;
+ return 0;
+ }
+
+ /* list them */
+
+ std::cout<<"listing by method 2"<<std::endl;
+ while(ictmv0!=ictmv1){
+ std::cout<<**ictmv0;
+ ++ictmv0;
+ }
+ std::cout<<std::endl;
+ }
+
+ return 0;
+}
diff --git a/example/composite_keys.cpp b/example/composite_keys.cpp
new file mode 100644
index 0000000..e9da2af
--- /dev/null
+++ b/example/composite_keys.cpp
@@ -0,0 +1,285 @@
+/* Boost.MultiIndex example of composite keys.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/call_traits.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/next_prior.hpp>
+#include <boost/tokenizer.hpp>
+#include <functional>
+#include <iostream>
+#include <iterator>
+#include <map>
+#include <string>
+
+using namespace boost::multi_index;
+
+/* A file record maintains some info on name and size as well
+ * as a pointer to the directory it belongs (null meaning the root
+ * directory.)
+ */
+
+struct file_entry
+{
+ file_entry(
+ std::string name_,unsigned size_,bool is_dir_,const file_entry* dir_):
+ name(name_),size(size_),is_dir(is_dir_),dir(dir_)
+ {}
+
+ std::string name;
+ unsigned size;
+ bool is_dir;
+ const file_entry* dir;
+
+ friend std::ostream& operator<<(std::ostream& os,const file_entry& f)
+ {
+ os<<f.name<<"\t"<<f.size;
+ if(f.is_dir)os<<"\t <dir>";
+ return os;
+ }
+};
+
+/* A file system is just a multi_index_container of entries with indices on
+ * file and size. These indices are firstly ordered by directory, as commands
+ * work on a current directory basis. Composite keys are just fine to model
+ * this.
+ * NB: The use of derivation here instead of simple typedef is explained in
+ * Compiler specifics: type hiding.
+ */
+
+struct name_key:composite_key<
+ file_entry,
+ BOOST_MULTI_INDEX_MEMBER(file_entry,const file_entry*,dir),
+ BOOST_MULTI_INDEX_MEMBER(file_entry,std::string,name)
+>{};
+
+struct size_key:composite_key<
+ file_entry,
+ BOOST_MULTI_INDEX_MEMBER(file_entry,const file_entry* const,dir),
+ BOOST_MULTI_INDEX_MEMBER(file_entry,unsigned,size)
+>{};
+
+/* see Compiler specifics: composite_key in compilers without partial
+ * template specialization, for info on composite_key_result_less
+ */
+
+typedef multi_index_container<
+ file_entry,
+ indexed_by<
+ /* primary index sorted by name (inside the same directory) */
+ ordered_unique<name_key>,
+ /* secondary index sorted by size (inside the same directory) */
+ ordered_non_unique<size_key>
+ >
+> file_system;
+
+/* typedef's of the two indices of file_system */
+
+typedef nth_index<file_system,0>::type file_system_by_name;
+typedef nth_index<file_system,1>::type file_system_by_size;
+
+/* We build a rudimentary file system simulation out of some global
+ * info and a map of commands provided to the user.
+ */
+
+static file_system fs; /* the one and only file system */
+static file_system_by_name& fs_by_name=fs; /* name index to fs */
+static file_system_by_size& fs_by_size=get<1>(fs); /* size index to fs */
+static const file_entry* current_dir=0; /* root directory */
+
+/* command framework */
+
+/* A command provides an execute memfun fed with the corresponding params
+ * (first param is stripped off as it serves to identify the command
+ * currently being used.)
+ */
+
+typedef boost::tokenizer<boost::char_separator<char> > command_tokenizer;
+
+class command
+{
+public:
+ virtual ~command(){}
+ virtual void execute(
+ command_tokenizer::iterator tok1,command_tokenizer::iterator tok2)=0;
+};
+
+/* available commands */
+
+/* cd: syntax cd [.|..|<directory>] */
+
+class command_cd:public command
+{
+public:
+ virtual void execute(
+ command_tokenizer::iterator tok1,command_tokenizer::iterator tok2)
+ {
+ if(tok1==tok2)return;
+ std::string dir=*tok1++;
+
+ if(dir==".")return;
+ if(dir==".."){
+ if(current_dir)current_dir=current_dir->dir;
+ return;
+ }
+
+ file_system_by_name::iterator it=fs.find(
+ boost::make_tuple(current_dir,dir));
+ if(it==fs.end()){
+ std::cout<<"non-existent directory"<<std::endl;
+ return;
+ }
+ if(!it->is_dir){
+ std::cout<<dir<<" is not a directory"<<std::endl;
+ return;
+ }
+ current_dir=&*it;
+ }
+};
+static command_cd cd;
+
+/* ls: syntax ls [-s] */
+
+class command_ls:public command
+{
+public:
+ virtual void execute(
+ command_tokenizer::iterator tok1,command_tokenizer::iterator tok2)
+ {
+ std::string option;
+ if(tok1!=tok2)option=*tok1++;
+
+ if(!option.empty()){
+ if(option!="-s"){
+ std::cout<<"incorrect parameter"<<std::endl;
+ return;
+ }
+
+ /* list by size */
+
+ file_system_by_size::iterator it0,it1;
+ boost::tie(it0,it1)=fs_by_size.equal_range(
+ boost::make_tuple(current_dir));
+ std::copy(it0,it1,std::ostream_iterator<file_entry>(std::cout,"\n"));
+
+ return;
+ }
+
+ /* list by name */
+
+ file_system_by_name::iterator it0,it1;
+ boost::tie(it0,it1)=fs.equal_range(boost::make_tuple(current_dir));
+ std::copy(it0,it1,std::ostream_iterator<file_entry>(std::cout,"\n"));
+ }
+};
+static command_ls ls;
+
+/* mkdir: syntax mkdir <directory> */
+
+class command_mkdir:public command
+{
+public:
+ virtual void execute(
+ command_tokenizer::iterator tok1,command_tokenizer::iterator tok2)
+ {
+ std::string dir;
+ if(tok1!=tok2)dir=*tok1++;
+
+ if(dir.empty()){
+ std::cout<<"missing parameter"<<std::endl;
+ return;
+ }
+
+ if(dir=="."||dir==".."){
+ std::cout<<"incorrect parameter"<<std::endl;
+ return;
+ }
+
+ if(!fs.insert(file_entry(dir,0,true,current_dir)).second){
+ std::cout<<"directory already exists"<<std::endl;
+ return;
+ }
+ }
+};
+static command_mkdir mkdir;
+
+/* table of commands, a map from command names to class command pointers */
+
+typedef std::map<std::string,command*> command_table;
+static command_table cmt;
+
+int main()
+{
+ /* fill the file system with some data */
+
+ file_system::iterator it0,it1;
+
+ fs.insert(file_entry("usr.cfg",240,false,0));
+ fs.insert(file_entry("memo.txt",2430,false,0));
+ it0=fs.insert(file_entry("dev",0,true,0)).first;
+ fs.insert(file_entry("tty0",128,false,&*it0));
+ fs.insert(file_entry("tty1",128,false,&*it0));
+ it0=fs.insert(file_entry("usr",0,true,0)).first;
+ it1=fs.insert(file_entry("bin",0,true,&*it0)).first;
+ fs.insert(file_entry("bjam",172032,false,&*it1));
+ it0=fs.insert(file_entry("home",0,true,0)).first;
+ it1=fs.insert(file_entry("andy",0,true,&*it0)).first;
+ fs.insert(file_entry("logo.jpg",5345,false,&*it1)).first;
+ fs.insert(file_entry("foo.cpp",890,false,&*it1)).first;
+ fs.insert(file_entry("foo.hpp",93,false,&*it1)).first;
+ fs.insert(file_entry("foo.html",750,false,&*it1)).first;
+ fs.insert(file_entry("a.obj",12302,false,&*it1)).first;
+ fs.insert(file_entry(".bash_history",8780,false,&*it1)).first;
+ it1=fs.insert(file_entry("rachel",0,true,&*it0)).first;
+ fs.insert(file_entry("test.py",650,false,&*it1)).first;
+ fs.insert(file_entry("todo.txt",241,false,&*it1)).first;
+ fs.insert(file_entry(".bash_history",9510,false,&*it1)).first;
+
+ /* fill the command table */
+
+ cmt["cd"] =&cd;
+ cmt["ls"] =&ls;
+ cmt["mkdir"]=&mkdir;
+
+ /* main looop */
+
+ for(;;){
+ /* print out the current directory and the prompt symbol */
+
+ if(current_dir)std::cout<<current_dir->name;
+ std::cout<<">";
+
+ /* get an input line from the user: if empty, exit the program */
+
+ std::string com;
+ std::getline(std::cin,com);
+ command_tokenizer tok(com,boost::char_separator<char>(" \t\n"));
+ if(tok.begin()==tok.end())break; /* null command, exit */
+
+ /* select the corresponding command and execute it */
+
+ command_table::iterator it=cmt.find(*tok.begin());
+ if(it==cmt.end()){
+ std::cout<<"invalid command"<<std::endl;
+ continue;
+ }
+
+ it->second->execute(boost::next(tok.begin()),tok.end());
+ }
+
+ return 0;
+}
diff --git a/example/fun_key.cpp b/example/fun_key.cpp
new file mode 100644
index 0000000..769d7bf
--- /dev/null
+++ b/example/fun_key.cpp
@@ -0,0 +1,100 @@
+/* Boost.MultiIndex example of functions used as key extractors.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/global_fun.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <iostream>
+#include <string>
+
+using namespace boost::multi_index;
+
+/* A name record consists of the given name (e.g. "Charlie")
+ * and the family name (e.g. "Brown"). The full name, calculated
+ * by name_record::name() is laid out in the "phonebook order"
+ * family name + given_name.
+ */
+
+struct name_record
+{
+ name_record(std::string given_name_,std::string family_name_):
+ given_name(given_name_),family_name(family_name_)
+ {}
+
+ std::string name()const
+ {
+ std::string str=family_name;
+ str+=" ";
+ str+=given_name;
+ return str;
+ }
+
+private:
+ std::string given_name;
+ std::string family_name;
+};
+
+std::string::size_type name_record_length(const name_record& r)
+{
+ return r.name().size();
+}
+
+/* multi_index_container with indices based on name_record::name()
+ * and name_record_length().
+ * See Compiler specifics: Use of const_mem_fun_explicit and
+ * mem_fun_explicit for info on BOOST_MULTI_INDEX_CONST_MEM_FUN.
+ */
+
+typedef multi_index_container<
+ name_record,
+ indexed_by<
+ ordered_unique<
+ BOOST_MULTI_INDEX_CONST_MEM_FUN(name_record,std::string,name)
+ >,
+ ordered_non_unique<
+ global_fun<const name_record&,std::string::size_type,name_record_length>
+ >
+ >
+> name_record_set;
+
+int main()
+{
+ name_record_set ns;
+
+ ns.insert(name_record("Joe","Smith"));
+ ns.insert(name_record("Robert","Nightingale"));
+ ns.insert(name_record("Robert","Brown"));
+ ns.insert(name_record("Marc","Tuxedo"));
+
+ /* list the names in ns in phonebook order */
+
+ std::cout<<"Phonenook order\n"
+ <<"---------------"<<std::endl;
+ for(name_record_set::iterator it=ns.begin();it!=ns.end();++it){
+ std::cout<<it->name()<<std::endl;
+ }
+
+ /* list the names in ns according to their length*/
+
+ std::cout<<"\nLength order\n"
+ << "------------"<<std::endl;
+ for(nth_index<name_record_set,1>::type::iterator it1=get<1>(ns).begin();
+ it1!=get<1>(ns).end();++it1){
+ std::cout<<it1->name()<<std::endl;
+ }
+
+ return 0;
+}
diff --git a/example/hashed.cpp b/example/hashed.cpp
new file mode 100644
index 0000000..98228ea
--- /dev/null
+++ b/example/hashed.cpp
@@ -0,0 +1,124 @@
+/* Boost.MultiIndex example of use of hashed indices.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/tokenizer.hpp>
+#include <iomanip>
+#include <iostream>
+#include <string>
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+
+/* word_counter keeps the ocurrences of words inserted. A hashed
+ * index allows for fast checking of preexisting entries.
+ */
+
+struct word_counter_entry
+{
+ std::string word;
+ unsigned int occurrences;
+
+ word_counter_entry(std::string word_):word(word_),occurrences(0){}
+};
+
+/* see Compiler specifics: Use of member_offset for info on
+ * BOOST_MULTI_INDEX_MEMBER
+ */
+
+typedef multi_index_container<
+ word_counter_entry,
+ indexed_by<
+ ordered_non_unique<
+ BOOST_MULTI_INDEX_MEMBER(word_counter_entry,unsigned int,occurrences),
+ std::greater<unsigned int> /* sorted beginning with most frequent */
+ >,
+ hashed_unique<
+ BOOST_MULTI_INDEX_MEMBER(word_counter_entry,std::string,word)
+ >
+ >
+> word_counter;
+
+/* utilities */
+
+template<typename T>
+struct increment
+{
+ void operator()(T& x)const{++x;}
+};
+
+typedef boost::tokenizer<boost::char_separator<char> > text_tokenizer;
+
+int main()
+{
+ /* boostinspect:noascii */
+
+ std::string text=
+ "En un lugar de la Mancha, de cuyo nombre no quiero acordarme, no ha "
+ "mucho tiempo que vivía un hidalgo de los de lanza en astillero, adarga "
+ "antigua, rocín flaco y galgo corredor. Una olla de algo más vaca que "
+ "carnero, salpicón las más noches, duelos y quebrantos los sábados, "
+ "lantejas los viernes, algún palomino de añadidura los domingos, "
+ "consumían las tres partes de su hacienda. El resto della concluían sayo "
+ "de velarte, calzas de velludo para las fiestas, con sus pantuflos de lo "
+ "mesmo, y los días de entresemana se honraba con su vellorí de lo más "
+ "fino. Tenía en su casa una ama que pasaba de los cuarenta, y una "
+ "sobrina que no llegaba a los veinte, y un mozo de campo y plaza, que "
+ "así ensillaba el rocín como tomaba la podadera. Frisaba la edad de "
+ "nuestro hidalgo con los cincuenta años; era de complexión recia, seco "
+ "de carnes, enjuto de rostro, gran madrugador y amigo de la caza. "
+ "Quieren decir que tenía el sobrenombre de Quijada, o Quesada, que en "
+ "esto hay alguna diferencia en los autores que deste caso escriben; "
+ "aunque, por conjeturas verosímiles, se deja entender que se llamaba "
+ "Quejana. Pero esto importa poco a nuestro cuento; basta que en la "
+ "narración dél no se salga un punto de la verdad.";
+
+ /* feed the text into the container */
+
+ word_counter wc;
+ text_tokenizer tok(text,boost::char_separator<char>(" \t\n.,;:!?'\"-"));
+ unsigned int total_occurrences=0;
+ for(text_tokenizer::iterator it=tok.begin(),it_end=tok.end();
+ it!=it_end;++it){
+ /* Insert the word into the container. If duplicate, wit will point to
+ * the preexistent entry.
+ */
+
+ ++total_occurrences;
+ word_counter::iterator wit=wc.insert(*it).first;
+
+ /* Increment occurrences.
+ * In a lambda-capable compiler, this can be written as:
+ * wc.modify_key(wit,++_1);
+ */
+
+ wc.modify_key(wit,increment<unsigned int>());
+ }
+
+ /* list words by frequency of appearance */
+
+ std::cout<<std::fixed<<std::setprecision(2);
+ for(word_counter::iterator wit=wc.begin(),wit_end=wc.end();
+ wit!=wit_end;++wit){
+ std::cout<<std::setw(11)<<wit->word<<": "
+ <<std::setw(5) <<100.0*wit->occurrences/total_occurrences<<"%"
+ <<std::endl;
+ }
+
+ return 0;
+}
diff --git a/example/ip_allocator.cpp b/example/ip_allocator.cpp
new file mode 100644
index 0000000..f2c6d67
--- /dev/null
+++ b/example/ip_allocator.cpp
@@ -0,0 +1,293 @@
+/* Boost.MultiIndex example of use of Boost.Interprocess allocators.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
+#include <algorithm>
+#include <boost/interprocess/allocators/allocator.hpp>
+#include <boost/interprocess/containers/string.hpp>
+#include <boost/interprocess/managed_mapped_file.hpp>
+#include <boost/interprocess/sync/named_mutex.hpp>
+#include <boost/interprocess/sync/scoped_lock.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <iostream>
+#include <iterator>
+#include <sstream>
+#include <string>
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+namespace bip=boost::interprocess;
+
+/* shared_string is a string type placeable in shared memory,
+ * courtesy of Boost.Interprocess.
+ */
+
+typedef bip::basic_string<
+ char,std::char_traits<char>,
+ bip::allocator<char,bip::managed_mapped_file::segment_manager>
+> shared_string;
+
+/* Book record. All its members can be placed in shared memory,
+ * hence the structure itself can too.
+ */
+
+struct book
+{
+ shared_string name;
+ shared_string author;
+ unsigned pages;
+ unsigned prize;
+
+ book(const shared_string::allocator_type& al):
+ name(al),author(al),pages(0),prize(0)
+ {}
+
+ friend std::ostream& operator<<(std::ostream& os,const book& b)
+ {
+ os<<b.author<<": \""<<b.name<<"\", $"<<b.prize<<", "<<b.pages<<" pages\n";
+ return os;
+ }
+};
+
+/* partial_str_less allows for partial searches taking into account
+ * only the first n chars of the strings compared against. See
+ * Tutorial: Basics: Special lookup operations for more info on this
+ * type of comparison functors.
+ */
+
+/* partial_string is a mere string holder used to differentiate from
+ * a plain string.
+ */
+
+struct partial_string
+{
+ partial_string(const shared_string& str):str(str){}
+ shared_string str;
+};
+
+struct partial_str_less
+{
+ bool operator()(const shared_string& x,const shared_string& y)const
+ {
+ return x<y;
+ }
+
+ bool operator()(const shared_string& x,const partial_string& y)const
+ {
+ return x.substr(0,y.str.size())<y.str;
+ }
+
+ bool operator()(const partial_string& x,const shared_string& y)const
+ {
+ return x.str<y.substr(0,x.str.size());
+ }
+};
+
+/* Define a multi_index_container of book records with indices on
+ * author, name and prize. The index on names allows for partial
+ * searches. This container can be placed in shared memory because:
+ * * book can be placed in shared memory.
+ * * We are using a Boost.Interprocess specific allocator.
+ */
+
+/* see Compiler specifics: Use of member_offset for info on
+ * BOOST_MULTI_INDEX_MEMBER
+ */
+
+typedef multi_index_container<
+ book,
+ indexed_by<
+ ordered_non_unique<
+ BOOST_MULTI_INDEX_MEMBER(book,shared_string,author)
+ >,
+ ordered_non_unique<
+ BOOST_MULTI_INDEX_MEMBER(book,shared_string,name),
+ partial_str_less
+ >,
+ ordered_non_unique<
+ BOOST_MULTI_INDEX_MEMBER(book,unsigned,prize)
+ >
+ >,
+ bip::allocator<book,bip::managed_mapped_file::segment_manager>
+> book_container;
+
+/* A small utility to get data entered via std::cin */
+
+template<typename T>
+void enter(const char* msg,T& t)
+{
+ std::cout<<msg;
+ std::string str;
+ std::getline(std::cin,str);
+ std::istringstream iss(str);
+ iss>>t;
+}
+
+void enter(const char* msg,std::string& str)
+{
+ std::cout<<msg;
+ std::getline(std::cin,str);
+}
+
+void enter(const char* msg,shared_string& str)
+{
+ std::cout<<msg;
+ std::string stdstr;
+ std::getline(std::cin,stdstr);
+ str=stdstr.c_str();
+}
+
+int main()
+{
+ /* Create (or open) the memory mapped file where the book container
+ * is stored, along with a mutex for synchronized access.
+ */
+
+ bip::managed_mapped_file seg(
+ bip::open_or_create,"./book_container.db",
+ 65536);
+ bip::named_mutex mutex(
+ bip::open_or_create,"7FD6D7E8-320B-11DC-82CF-F0B655D89593");
+
+ /* create or open the book container in shared memory */
+
+ book_container* pbc=seg.find_or_construct<book_container>("book container")(
+ book_container::ctor_args_list(),
+ book_container::allocator_type(seg.get_segment_manager()));
+
+ std::string command_info=
+ "1. list books by author\n"
+ "2. list all books by prize\n"
+ "3. insert a book\n"
+ "4. delete a book\n"
+ "0. exit\n";
+
+ std::cout<<command_info;
+
+ /* main loop */
+
+ for(bool exit=false;!exit;){
+ int command=-1;
+ enter("command: ",command);
+
+ switch(command){
+ case 0:{ /* exit */
+ exit=true;
+ break;
+ }
+ case 1:{ /* list books by author */
+ std::string author;
+ enter("author (empty=all authors): ",author);
+
+ /* operations with the container must be mutex protected */
+
+ bip::scoped_lock<bip::named_mutex> lock(mutex);
+
+ std::pair<book_container::iterator,book_container::iterator> rng;
+ if(author.empty()){
+ rng=std::make_pair(pbc->begin(),pbc->end());
+ }
+ else{
+ rng=pbc->equal_range(
+ shared_string(
+ author.c_str(),
+ shared_string::allocator_type(seg.get_segment_manager())));
+ }
+
+ if(rng.first==rng.second){
+ std::cout<<"no entries\n";
+ }
+ else{
+ std::copy(
+ rng.first,rng.second,std::ostream_iterator<book>(std::cout));
+ }
+ break;
+ }
+ case 2:{ /* list all books by prize */
+ bip::scoped_lock<bip::named_mutex> lock(mutex);
+
+ std::copy(
+ get<2>(*pbc).begin(),get<2>(*pbc).end(),
+ std::ostream_iterator<book>(std::cout));
+ break;
+ }
+ case 3:{ /* insert a book */
+ book b(shared_string::allocator_type(seg.get_segment_manager()));
+
+ enter("author: ",b.author);
+ enter("name: " ,b.name);
+ enter("prize: " ,b.prize);
+ enter("pages: " ,b.pages);
+
+ std::cout<<"insert the following?\n"<<b<<"(y/n): ";
+ char yn='n';
+ enter("",yn);
+ if(yn=='y'||yn=='Y'){
+ bip::scoped_lock<bip::named_mutex> lock(mutex);
+ pbc->insert(b);
+ }
+
+ break;
+ }
+ case 4:{ /* delete a book */
+ shared_string name(
+ shared_string::allocator_type(seg.get_segment_manager()));
+ enter(
+ "name of the book (you can enter\nonly the first few characters): ",
+ name);
+
+ typedef nth_index<book_container,1>::type index_by_name;
+ index_by_name& idx=get<1>(*pbc);
+ index_by_name::iterator it;
+ book b(shared_string::allocator_type(seg.get_segment_manager()));
+
+ {
+ /* Look for a book whose title begins with name. Note that we
+ * are unlocking after doing the search so as to not leave the
+ * container blocked during user prompting. That is also why a
+ * local copy of the book is done.
+ */
+
+ bip::scoped_lock<bip::named_mutex> lock(mutex);
+
+ it=idx.find(partial_string(name));
+ if(it==idx.end()){
+ std::cout<<"no such book found\n";
+ break;
+ }
+ b=*it;
+ }
+
+ std::cout<<"delete the following?\n"<<b<<"(y/n): ";
+ char yn='n';
+ enter("",yn);
+ if(yn=='y'||yn=='Y'){
+ bip::scoped_lock<bip::named_mutex> lock(mutex);
+ idx.erase(it);
+ }
+
+ break;
+ }
+ default:{
+ std::cout<<"select one option:\n"<<command_info;
+ break;
+ }
+ }
+ }
+
+ return 0;
+}
diff --git a/example/non_default_ctor.cpp b/example/non_default_ctor.cpp
new file mode 100644
index 0000000..afdbd51
--- /dev/null
+++ b/example/non_default_ctor.cpp
@@ -0,0 +1,96 @@
+/* Boost.MultiIndex example of use of multi_index_container::ctor_args_list.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <algorithm>
+#include <iostream>
+#include <iterator>
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+
+/* modulo_less order numbers according to their division residual.
+ * For instance, if modulo==10 then 22 is less than 15 as 22%10==2 and
+ * 15%10==5.
+ */
+
+template<typename IntegralType>
+struct modulo_less
+{
+ modulo_less(IntegralType m):modulo(m){}
+
+ bool operator()(IntegralType x,IntegralType y)const
+ {
+ return (x%modulo)<(y%modulo);
+ }
+
+private:
+ IntegralType modulo;
+};
+
+/* multi_index_container of unsigned ints holding a "natural" index plus
+ * an ordering based on modulo_less.
+ */
+
+typedef multi_index_container<
+ unsigned int,
+ indexed_by<
+ ordered_unique<identity<unsigned int> >,
+ ordered_non_unique<identity<unsigned int>, modulo_less<unsigned int> >
+ >
+> modulo_indexed_set;
+
+int main()
+{
+ /* define a modulo_indexed_set with modulo==10 */
+
+ modulo_indexed_set::ctor_args_list args_list=
+ boost::make_tuple(
+ /* ctor_args for index #0 is default constructible */
+ nth_index<modulo_indexed_set,0>::type::ctor_args(),
+
+ /* first parm is key_from_value, second is our sought for key_compare */
+ boost::make_tuple(identity<unsigned int>(),modulo_less<unsigned int>(10))
+ );
+
+ modulo_indexed_set m(args_list);
+ /* this could have be written online without the args_list variable,
+ * left as it is for explanatory purposes. */
+
+ /* insert some numbers */
+
+ unsigned int numbers[]={0,1,20,40,33,68,11,101,60,34,88,230,21,4,7,17};
+ const std::size_t numbers_length(sizeof(numbers)/sizeof(numbers[0]));
+
+ m.insert(&numbers[0],&numbers[numbers_length]);
+
+ /* lists all numbers in order, along with their "equivalence class", that is,
+ * the equivalent numbers under modulo_less
+ */
+
+ for(modulo_indexed_set::iterator it=m.begin();it!=m.end();++it){
+ std::cout<<*it<<" -> ( ";
+
+ nth_index<modulo_indexed_set,1>::type::iterator it0,it1;
+ boost::tie(it0,it1)=get<1>(m).equal_range(*it);
+ std::copy(it0,it1,std::ostream_iterator<unsigned int>(std::cout," "));
+
+ std::cout<<")"<<std::endl;
+ }
+
+ return 0;
+}
diff --git a/example/random_access.cpp b/example/random_access.cpp
new file mode 100644
index 0000000..7532c6d
--- /dev/null
+++ b/example/random_access.cpp
@@ -0,0 +1,102 @@
+/* Boost.MultiIndex example of use of random access indices.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/random_access_index.hpp>
+#include <boost/tokenizer.hpp>
+#include <algorithm>
+#include <iostream>
+#include <iterator>
+#include <string>
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+
+/* text_container holds words as inserted and also keep them indexed
+ * by dictionary order.
+ */
+
+typedef multi_index_container<
+ std::string,
+ indexed_by<
+ random_access<>,
+ ordered_non_unique<identity<std::string> >
+ >
+> text_container;
+
+/* ordered index */
+
+typedef nth_index<text_container,1>::type ordered_text;
+
+/* Helper function for obtaining the position of an element in the
+ * container.
+ */
+
+template<typename IndexIterator>
+text_container::size_type text_position(
+ const text_container& tc,IndexIterator it)
+{
+ /* project to the base index and calculate offset from begin() */
+
+ return project<0>(tc,it)-tc.begin();
+}
+
+typedef boost::tokenizer<boost::char_separator<char> > text_tokenizer;
+
+int main()
+{
+ std::string text=
+ "'Oh, you wicked little thing!' cried Alice, catching up the kitten, "
+ "and giving it a little kiss to make it understand that it was in "
+ "disgrace. 'Really, Dinah ought to have taught you better manners! You "
+ "ought, Dinah, you know you ought!' she added, looking reproachfully at "
+ "the old cat, and speaking in as cross a voice as she could manage "
+ "-- and then she scrambled back into the armchair, taking the kitten and "
+ "the worsted with her, and began winding up the ball again. But she "
+ "didn't get on very fast, as she was talking all the time, sometimes to "
+ "the kitten, and sometimes to herself. Kitty sat very demurely on her "
+ "knee, pretending to watch the progress of the winding, and now and then "
+ "putting out one paw and gently touching the ball, as if it would be glad "
+ "to help, if it might.";
+
+ /* feed the text into the container */
+
+ text_container tc;
+ tc.reserve(text.size()); /* makes insertion faster */
+ text_tokenizer tok(text,boost::char_separator<char>(" \t\n.,;:!?'\"-"));
+ std::copy(tok.begin(),tok.end(),std::back_inserter(tc));
+
+ std::cout<<"enter a position (0-"<<tc.size()-1<<"):";
+ text_container::size_type pos=tc.size();
+ std::cin>>pos;
+ if(pos>=tc.size()){
+ std::cout<<"out of bounds"<<std::endl;
+ }
+ else{
+ std::cout<<"the word \""<<tc[pos]<<"\" appears at position(s): ";
+
+ std::pair<ordered_text::iterator,ordered_text::iterator> p=
+ get<1>(tc).equal_range(tc[pos]);
+ while(p.first!=p.second){
+ std::cout<<text_position(tc,p.first++)<<" ";
+ }
+
+ std::cout<<std::endl;
+ }
+
+ return 0;
+}
diff --git a/example/rearrange.cpp b/example/rearrange.cpp
new file mode 100644
index 0000000..3138851
--- /dev/null
+++ b/example/rearrange.cpp
@@ -0,0 +1,265 @@
+/* Boost.MultiIndex example of use of rearrange facilities.
+ *
+ * Copyright 2003-2015 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/config.hpp>
+#include <boost/detail/iterator.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/random_access_index.hpp>
+#include <boost/random/binomial_distribution.hpp>
+#include <boost/random/uniform_real.hpp>
+#include <boost/random/mersenne_twister.hpp>
+#include <algorithm>
+#include <iostream>
+#include <iterator>
+#include <vector>
+
+#if !defined(BOOST_NO_CXX11_HDR_RANDOM)
+#include <random>
+#endif
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+
+/* We model a card deck with a random access array containing
+ * card numbers (from 0 to 51), supplemented with an additional
+ * index which retains the start ordering.
+ */
+
+class deck
+{
+ BOOST_STATIC_CONSTANT(std::size_t,num_cards=52);
+
+ typedef multi_index_container<
+ int,
+ indexed_by<
+ random_access<>, /* base index */
+ random_access<> /* "start" index */
+ >
+ > container_type;
+ container_type cont;
+
+public:
+ deck()
+ {
+ cont.reserve(num_cards);
+ get<1>(cont).reserve(num_cards);
+ for(std::size_t i=0;i<num_cards;++i)cont.push_back(i);
+ }
+
+ typedef container_type::iterator iterator;
+ typedef container_type::size_type size_type;
+
+ iterator begin()const{return cont.begin();}
+ iterator end()const{return cont.end();}
+ size_type size()const{return cont.size();}
+
+ template<typename InputIterator>
+ void rearrange(InputIterator it)
+ {
+ cont.rearrange(it);
+ }
+
+ void reset()
+ {
+ /* simply rearrange the base index like the start index */
+
+ cont.rearrange(get<1>(cont).begin());
+ }
+
+ std::size_t position(int i)const
+ {
+ /* The position of a card in the deck is calculated by locating
+ * the card through the start index (which is ordered), projecting
+ * to the base index and diffing with the begin position.
+ * Resulting complexity: constant.
+ */
+
+ return project<0>(cont,get<1>(cont).begin()+i)-cont.begin();
+ }
+
+ std::size_t rising_sequences()const
+ {
+ /* Iterate through all cards and increment the sequence count
+ * when the current position is left to the previous.
+ * Resulting complexity: O(n), n=num_cards.
+ */
+
+ std::size_t s=1;
+ std::size_t last_pos=0;
+
+ for(std::size_t i=0;i<num_cards;++i){
+ std::size_t pos=position(i);
+ if(pos<last_pos)++s;
+ last_pos=pos;
+ }
+
+ return s;
+ }
+};
+
+/* A vector of reference_wrappers to deck elements can be used
+ * as a view to the deck container.
+ * We use a special implicit_reference_wrapper having implicit
+ * ctor from its base type, as this simplifies the use of generic
+ * techniques on the resulting data structures.
+ */
+
+template<typename T>
+class implicit_reference_wrapper:public boost::reference_wrapper<T>
+{
+private:
+ typedef boost::reference_wrapper<T> super;
+public:
+ implicit_reference_wrapper(T& t):super(t){}
+};
+
+typedef std::vector<implicit_reference_wrapper<const int> > deck_view;
+
+/* Riffle shuffle is modeled like this: A cut is selected in the deck
+ * following a binomial distribution. Then, cards are randomly selected
+ * from one packet or the other with probability proportional to
+ * packet size.
+ */
+
+template<typename RandomAccessIterator,typename OutputIterator>
+void riffle_shuffle(
+ RandomAccessIterator first,RandomAccessIterator last,
+ OutputIterator out)
+{
+ static boost::mt19937 rnd_gen;
+
+ typedef typename boost::detail::iterator_traits<
+ RandomAccessIterator>::difference_type difference_type;
+ typedef boost::binomial_distribution<
+ difference_type> rnd_cut_select_type;
+ typedef boost::uniform_real<> rnd_deck_select_type;
+
+ rnd_cut_select_type cut_select(last-first);
+ RandomAccessIterator middle=first+cut_select(rnd_gen);
+ difference_type s0=middle-first;
+ difference_type s1=last-middle;
+ rnd_deck_select_type deck_select;
+
+ while(s0!=0&&s1!=0){
+ if(deck_select(rnd_gen)<(double)s0/(s0+s1)){
+ *out++=*first++;
+ --s0;
+ }
+ else{
+ *out++=*middle++;
+ --s1;
+ }
+ }
+ std::copy(first,first+s0,out);
+ std::copy(middle,middle+s1,out);
+}
+
+struct riffle_shuffler
+{
+ void operator()(deck& d)const
+ {
+ dv.clear();
+ dv.reserve(d.size());
+ riffle_shuffle(
+ d.begin(),d.end(),std::back_inserter(dv)); /* do the shuffling */
+ d.rearrange(dv.begin()); /* apply to the deck */
+ }
+
+private:
+ mutable deck_view dv;
+};
+
+/* A truly random shuffle (up to stdlib implementation quality) using
+ * std::shuffle.
+ */
+
+struct random_shuffler
+{
+ void operator()(deck& d)
+ {
+ dv.clear();
+ dv.reserve(d.size());
+ std::copy(d.begin(),d.end(),std::back_inserter(dv));
+ shuffle_view();
+ d.rearrange(dv.begin()); /* apply to the deck */
+ }
+
+private:
+ deck_view dv;
+
+#if !defined(BOOST_NO_CXX11_HDR_RANDOM)
+ std::mt19937 e;
+
+ void shuffle_view()
+ {
+ std::shuffle(dv.begin(),dv.end(),e);
+ }
+#else
+ /* for pre-C++11 compilers we use std::random_shuffle */
+
+ void shuffle_view()
+ {
+ std::random_shuffle(dv.begin(),dv.end());
+ }
+#endif
+};
+
+/* Repeat a given shuffling algorithm repeats_num times
+ * and obtain the resulting rising sequences number. Average
+ * for tests_num trials.
+ */
+
+template<typename Shuffler>
+double shuffle_test(
+ unsigned int repeats_num,unsigned int tests_num
+ BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Shuffler))
+{
+ deck d;
+ Shuffler sh;
+ unsigned long total=0;
+
+ for(unsigned int n=0;n<tests_num;++n){
+ for(unsigned m=0;m<repeats_num;++m)sh(d);
+ total+=d.rising_sequences();
+ d.reset();
+ }
+
+ return (double)total/tests_num;
+}
+
+int main()
+{
+ unsigned rifs_num=0;
+ unsigned tests_num=0;
+
+ std::cout<<"number of riffle shuffles (vg 5):";
+ std::cin>>rifs_num;
+ std::cout<<"number of tests (vg 1000):";
+ std::cin>>tests_num;
+
+ std::cout<<"shuffling..."<<std::endl;
+
+ std::cout<<"riffle shuffling\n"
+ " avg number of rising sequences: "
+ <<shuffle_test<riffle_shuffler>(rifs_num,tests_num)
+ <<std::endl;
+
+ std::cout<<"random shuffling\n"
+ " avg number of rising sequences: "
+ <<shuffle_test<random_shuffler>(1,tests_num)
+ <<std::endl;
+
+ return 0;
+}
diff --git a/example/sequenced.cpp b/example/sequenced.cpp
new file mode 100644
index 0000000..14651da
--- /dev/null
+++ b/example/sequenced.cpp
@@ -0,0 +1,100 @@
+/* Boost.MultiIndex example of use of sequenced indices.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/tokenizer.hpp>
+#include <algorithm>
+#include <iomanip>
+#include <iostream>
+#include <iterator>
+#include <string>
+
+using boost::multi_index_container;
+using namespace boost::multi_index;
+
+/* text_container holds words as inserted and also keep them indexed
+ * by dictionary order.
+ */
+
+typedef multi_index_container<
+ std::string,
+ indexed_by<
+ sequenced<>,
+ ordered_non_unique<identity<std::string> >
+ >
+> text_container;
+
+/* ordered index */
+
+typedef nth_index<text_container,1>::type ordered_text;
+
+typedef boost::tokenizer<boost::char_separator<char> > text_tokenizer;
+
+int main()
+{
+ std::string text=
+ "Alice was beginning to get very tired of sitting by her sister on the "
+ "bank, and of having nothing to do: once or twice she had peeped into the "
+ "book her sister was reading, but it had no pictures or conversations in "
+ "it, 'and what is the use of a book,' thought Alice 'without pictures or "
+ "conversation?'";
+
+ /* feed the text into the container */
+
+ text_container tc;
+ text_tokenizer tok(text,boost::char_separator<char>(" \t\n.,;:!?'\"-"));
+ std::copy(tok.begin(),tok.end(),std::back_inserter(tc));
+
+ /* list all words in alphabetical order along with their number
+ * of occurrences
+ */
+
+ ordered_text& ot=get<1>(tc);
+ for(ordered_text::iterator it=ot.begin();it!=ot.end();){
+ std::cout<<std::left<<std::setw(14)<<*it<<":"; /* print the word */
+ ordered_text::iterator it2=ot.upper_bound(*it); /* jump to next */
+ std::cout<<std::right<<std::setw(3) /* and compute the distance */
+ <<std::distance(it,it2)<<" times"<<std::endl;
+ it=it2;
+ }
+
+ /* reverse the text and print it out */
+
+ tc.reverse();
+ std::cout<<std::endl;
+ std::copy(
+ tc.begin(),tc.end(),std::ostream_iterator<std::string>(std::cout," "));
+ std::cout<<std::endl;
+ tc.reverse(); /* undo */
+
+ /* delete most common English words and print the result */
+
+ std::string common_words[]=
+ {"the","of","and","a","to","in","is","you","that","it",
+ "he","for","was","on","are","as","with","his","they","at"};
+
+ for(std::size_t n=0;n<sizeof(common_words)/sizeof(common_words[0]);++n){
+ ot.erase(common_words[n]);
+ }
+ std::cout<<std::endl;
+ std::copy(
+ tc.begin(),tc.end(),std::ostream_iterator<std::string>(std::cout," "));
+ std::cout<<std::endl;
+
+ return 0;
+}
diff --git a/example/serialization.cpp b/example/serialization.cpp
new file mode 100644
index 0000000..46ccf50
--- /dev/null
+++ b/example/serialization.cpp
@@ -0,0 +1,144 @@
+/* Boost.MultiIndex example of serialization of a MRU list.
+ *
+ * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * 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/multi_index for library home page.
+ */
+
+#if !defined(NDEBUG)
+#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
+#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
+#endif
+
+#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
+#include <algorithm>
+#include <boost/archive/text_oarchive.hpp>
+#include <boost/archive/text_iarchive.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <fstream>
+#include <iostream>
+#include <iterator>
+#include <sstream>
+#include <string>
+
+using namespace boost::multi_index;
+
+/* An MRU (most recently used) list keeps record of the last n
+ * inserted items, listing first the newer ones. Care has to be
+ * taken when a duplicate item is inserted: instead of letting it
+ * appear twice, the MRU list relocates it to the first position.
+ */
+
+template <typename Item>
+class mru_list
+{
+ typedef multi_index_container<
+ Item,
+ indexed_by<
+ sequenced<>,
+ hashed_unique<identity<Item> >
+ >
+ > item_list;
+
+public:
+ typedef Item item_type;
+ typedef typename item_list::iterator iterator;
+
+ mru_list(std::size_t max_num_items_):max_num_items(max_num_items_){}
+
+ void insert(const item_type& item)
+ {
+ std::pair<iterator,bool> p=il.push_front(item);
+
+ if(!p.second){ /* duplicate item */
+ il.relocate(il.begin(),p.first); /* put in front */
+ }
+ else if(il.size()>max_num_items){ /* keep the length <= max_num_items */
+ il.pop_back();
+ }
+ }
+
+ iterator begin(){return il.begin();}
+ iterator end(){return il.end();}
+
+ /* Utilities to save and load the MRU list, internally
+ * based on Boost.Serialization.
+ */
+
+ void save_to_file(const char* file_name)const
+ {
+ std::ofstream ofs(file_name);
+ boost::archive::text_oarchive oa(ofs);
+ oa<<boost::serialization::make_nvp("mru",*this);
+ }
+
+ void load_from_file(const char* file_name)
+ {
+ std::ifstream ifs(file_name);
+ if(ifs){
+ boost::archive::text_iarchive ia(ifs);
+ ia>>boost::serialization::make_nvp("mru",*this);
+ }
+ }
+
+private:
+ item_list il;
+ std::size_t max_num_items;
+
+ /* serialization support */
+
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void serialize(Archive& ar,const unsigned int)
+ {
+ ar&BOOST_SERIALIZATION_NVP(il);
+ ar&BOOST_SERIALIZATION_NVP(max_num_items);
+ }
+};
+
+int main()
+{
+ const char* mru_store="mru_store";
+
+ /* Construct a MRU limited to 10 items and retrieve its
+ * previous contents.
+ */
+
+ mru_list<std::string> mru(10);
+ mru.load_from_file(mru_store);
+
+ /* main loop */
+
+ for(;;){
+ std::cout<<"enter a term: ";
+
+ std::string line;
+ std::getline(std::cin,line);
+ if(line.empty())break;
+
+ std::string term;
+ std::istringstream iss(line);
+ iss>>term;
+ if(term.empty())break;
+
+ mru.insert(term);
+
+ std::cout<<"most recently entered terms:"<<std::endl;
+ std::copy(
+ mru.begin(),mru.end(),
+ std::ostream_iterator<std::string>(std::cout,"\n"));
+ }
+
+ /* persist the MRU list */
+
+ mru.save_to_file(mru_store);
+
+ return 0;
+}