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/bench/bench_set.hpp b/bench/bench_set.hpp
new file mode 100644
index 0000000..4af500c
--- /dev/null
+++ b/bench/bench_set.hpp
@@ -0,0 +1,479 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2013-2014. 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.
+//
+//////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_CONTAINER_BENCH_BENCH_SET_HPP
+#define BOOST_CONTAINER_BENCH_BENCH_SET_HPP
+
+#include <iostream>
+#include <boost/timer/timer.hpp>
+#include <algorithm> //sort
+#include <exception>
+#include <sstream>
+#include <iomanip>
+#include <boost/container/vector.hpp>
+#include <boost/container/string.hpp>
+
+using boost::timer::cpu_timer;
+using boost::timer::cpu_times;
+using boost::timer::nanosecond_type;
+
+static const std::size_t NElements = 1000;
+
+#ifdef NDEBUG
+static const std::size_t NIter = 250;
+#else
+static const std::size_t NIter = 25;
+#endif
+
+void compare_times(cpu_times time_numerator, cpu_times time_denominator){
+ std::cout << ((double)time_numerator.wall/(double)time_denominator.wall) << std::endl;
+ std::cout << "----------------------------------------------" << '\n' << std::endl;
+}
+
+template< class RandomIt >
+void random_shuffle( RandomIt first, RandomIt last )
+{
+ typedef typename boost::container::iterator_traits<RandomIt>::difference_type difference_type;
+ difference_type n = last - first;
+ for (difference_type i = n-1; i > 0; --i) {
+ difference_type j = std::rand() % (i+1);
+ if(j != i) {
+ boost::adl_move_swap(first[i], first[j]);
+ }
+ }
+}
+
+boost::container::vector<int> sorted_unique_range_int;
+boost::container::vector<int> sorted_range_int;
+boost::container::vector<int> random_unique_range_int;
+boost::container::vector<int> random_range_int;
+
+void fill_range_ints()
+{
+ //sorted_unique_range_int
+ sorted_unique_range_int.resize(NElements);
+ for(std::size_t i = 0, max = sorted_unique_range_int.size(); i != max; ++i){
+ sorted_unique_range_int[i] = static_cast<int>(i);
+ }
+ //sorted_range_int
+ sorted_range_int = sorted_unique_range_int;
+ sorted_range_int.insert(sorted_range_int.end(), sorted_unique_range_int.begin(), sorted_unique_range_int.end());
+ std::sort(sorted_range_int.begin(), sorted_range_int.end());
+
+ //random_range_int
+ std::srand(0);
+ random_range_int.assign(sorted_range_int.begin(), sorted_range_int.end());
+ ::random_shuffle(random_range_int.begin(), random_range_int.end());
+ //random_unique_range_int
+ std::srand(0);
+ random_unique_range_int.assign(sorted_unique_range_int.begin(), sorted_unique_range_int.end());
+ ::random_shuffle(random_unique_range_int.begin(), random_unique_range_int.end());
+}
+
+boost::container::vector<boost::container::string> sorted_unique_range_string;
+boost::container::vector<boost::container::string> sorted_range_string;
+boost::container::vector<boost::container::string> random_unique_range_string;
+boost::container::vector<boost::container::string> random_range_string;
+
+void fill_range_strings()
+{
+ boost::container::string model_s;
+ model_s.append(sizeof(boost::container::string), '*');
+
+ //sorted_unique_range_int
+ sorted_unique_range_string.resize(NElements);
+ std::stringstream sstr;
+
+ for(std::size_t i = 0, max = sorted_unique_range_string.size(); i != max; ++i){
+ sstr.str(std::string());
+ sstr << std::setfill('0') << std::setw(10) << i;
+ sorted_unique_range_string[i] = model_s;
+ const std::string &s = sstr.str();
+ sorted_unique_range_string[i].append(s.begin(), s.end());
+ }
+ //sorted_range_string
+ sorted_range_string = sorted_unique_range_string;
+ sorted_range_string.insert(sorted_range_string.end(), sorted_unique_range_string.begin(), sorted_unique_range_string.end());
+ std::sort(sorted_range_string.begin(), sorted_range_string.end());
+
+ //random_range_string
+ std::srand(0);
+ random_range_string.assign(sorted_range_string.begin(), sorted_range_string.end());
+ ::random_shuffle(random_range_string.begin(), random_range_string.end());
+ //random_unique_range_string
+ std::srand(0);
+ random_unique_range_string.assign(sorted_unique_range_string.begin(), sorted_unique_range_string.end());
+ ::random_shuffle(random_unique_range_string.begin(), random_unique_range_string.end());
+}
+
+template<class T>
+struct range_provider;
+
+template<>
+struct range_provider<int>
+{
+ typedef boost::container::vector<int> type;
+
+ static type &sorted_unique()
+ { return sorted_unique_range_int; }
+
+ static type &sorted()
+ { return sorted_range_int; }
+
+ static type &random_unique()
+ { return random_unique_range_int; }
+
+ static type &random()
+ { return random_range_int; }
+};
+
+template<>
+struct range_provider<boost::container::string>
+{
+ typedef boost::container::vector<boost::container::string> type;
+
+ static type &sorted_unique()
+ { return sorted_unique_range_string; }
+
+ static type &sorted()
+ { return sorted_range_string; }
+
+ static type &random_unique()
+ { return random_unique_range_string; }
+
+ static type &random()
+ { return random_range_string; }
+};
+
+template<typename C>
+cpu_times copy_destroy_time(boost::container::vector<typename C::value_type> &unique_range)
+{
+ cpu_timer copy_timer, assign_timer, destroy_timer;
+
+ cpu_timer total_time;
+
+ for(std::size_t i = 0; i != NIter; ++i){
+ {
+ C c(unique_range.begin(), unique_range.end());
+ total_time.resume();
+ copy_timer.resume();
+ C caux(c);
+ copy_timer.stop();
+ assign_timer.resume();
+ c = caux;
+ assign_timer.stop();
+ destroy_timer.resume();
+ }
+ destroy_timer.stop();
+ total_time.stop();
+ }
+ total_time.stop();
+
+ std::cout << " Copy sorted range " << boost::timer::format(copy_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Assign sorted range " << boost::timer::format(assign_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Destroy " << boost::timer::format(destroy_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Total time = " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws\n") << std::endl;
+ return total_time.elapsed();
+}
+
+template<typename C>
+cpu_times construct_time( boost::container::vector<typename C::value_type> &unique_range
+ , boost::container::vector<typename C::value_type> &range
+ , const char *RangeType)
+{
+ cpu_timer sur_timer, sr_timer;
+
+ cpu_timer total_time;
+
+ for(std::size_t i = 0; i != NIter; ++i){
+ {
+ sur_timer.resume();
+ total_time.resume();
+ C c(unique_range.begin(), unique_range.end());
+ sur_timer.stop();
+ total_time.stop();
+ }
+ {
+ total_time.resume();
+ sr_timer.resume();
+ C c(range.begin(), range.end());
+ sr_timer.stop();
+ total_time.stop();
+ }
+ }
+
+ std::cout << " Construct " << RangeType << " unique_range " << boost::timer::format(sur_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Construct " << RangeType << " range " << boost::timer::format(sr_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Total time = " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws\n") << std::endl;
+ return total_time.elapsed();
+}
+
+template<typename C>
+cpu_times insert_time( boost::container::vector<typename C::value_type> &unique_range
+ , boost::container::vector<typename C::value_type> &range
+ , const char *RangeType)
+{
+ cpu_timer ur_timer,r_timer;
+ ur_timer.stop();r_timer.stop();
+
+ cpu_timer total_time;
+ total_time.resume();
+
+ for(std::size_t i = 0; i != NIter; ++i){
+ {
+ total_time.resume();
+ ur_timer.resume();
+ C c;
+ c.insert(unique_range.begin(), unique_range.end());
+ ur_timer.stop();
+ total_time.stop();
+ }
+ {
+ total_time.resume();
+ r_timer.resume();
+ C c;
+ c.insert(range.begin(), range.end());
+ r_timer.stop();
+ total_time.stop();
+ }
+ }
+
+ std::cout << " Insert " << RangeType << " unique_range " << boost::timer::format(ur_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Insert " << RangeType << " range " << boost::timer::format(r_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Total time = " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws\n") << std::endl;
+ return total_time.elapsed();
+}
+
+template<typename Iterator>
+bool check_not_end(boost::container::vector<Iterator> &iterators, Iterator itend, std::size_t number_of_ends = 0)
+{
+ std::size_t end_count = 0;
+ for(std::size_t i = 0, max = iterators.size(); i != max; ++i){
+ if(iterators[i] == itend && (++end_count > number_of_ends) )
+ return false;
+ }
+ return true;
+}
+
+template<typename Iterator>
+bool check_all_not_empty(boost::container::vector< std::pair<Iterator, Iterator > > &iterator_pairs)
+{
+ for(std::size_t i = 0, max = iterator_pairs.size(); i != max; ++i){
+ if(iterator_pairs[i].first == iterator_pairs[i].second)
+ return false;
+ }
+ return true;
+}
+
+template<typename C>
+cpu_times search_time(boost::container::vector<typename C::value_type> &unique_range, const char *RangeType)
+{
+ cpu_timer find_timer, lower_timer, upper_timer, equal_range_timer, count_timer;
+
+ C c(unique_range.begin(), unique_range.end());
+
+ cpu_timer total_time;
+ total_time.resume();
+
+ boost::container::vector<typename C::iterator> v_it(NElements);
+ boost::container::vector< std::pair<typename C::iterator, typename C::iterator> > v_itp(NElements);
+
+ for(std::size_t i = 0; i != NIter; ++i){
+ //Find
+ {
+ find_timer.resume();
+ for(std::size_t rep = 0; rep != 2; ++rep)
+ for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
+ v_it[i] = c.find(unique_range[i]);
+ }
+ find_timer.stop();
+ if(!check_not_end(v_it, c.end())){
+ std::cout << "ERROR! find all elements not found" << std::endl;
+ }
+ }
+ //Lower
+ {
+ lower_timer.resume();
+ for(std::size_t rep = 0; rep != 2; ++rep)
+ for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
+ v_it[i] = c.lower_bound(unique_range[i]);
+ }
+ lower_timer.stop();
+ if(!check_not_end(v_it, c.end())){
+ std::cout << "ERROR! lower_bound all elements not found" << std::endl;
+ }
+ }
+ //Upper
+ {
+ upper_timer.resume();
+ for(std::size_t rep = 0; rep != 2; ++rep)
+ for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
+ v_it[i] = c.upper_bound(unique_range[i]);
+ }
+ upper_timer.stop();
+ if(!check_not_end(v_it, c.end(), 1u)){
+ std::cout << "ERROR! upper_bound all elements not found" << std::endl;
+ }
+ }
+ //Equal
+ {
+ equal_range_timer.resume();
+ for(std::size_t rep = 0; rep != 2; ++rep)
+ for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
+ v_itp[i] = c.equal_range(unique_range[i]);
+ }
+ equal_range_timer.stop();
+ if(!check_all_not_empty(v_itp)){
+ std::cout << "ERROR! equal_range all elements not found" << std::endl;
+ }
+ }
+ //Count
+ {
+ std::size_t count = 0;
+ count_timer.resume();
+ for(std::size_t rep = 0; rep != 2; ++rep)
+ for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
+ count += c.count(unique_range[i]);
+ }
+ count_timer.stop();
+ if(count/2 != c.size()){
+ std::cout << "ERROR! count all elements not found" << std::endl;
+ }
+ }
+ }
+ total_time.stop();
+
+ std::cout << " Find " << RangeType << " " << boost::timer::format(find_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Lower Bound " << RangeType << " " << boost::timer::format(lower_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Upper Bound " << RangeType << " " << boost::timer::format(upper_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Equal Range " << RangeType << " " << boost::timer::format(equal_range_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Count " << RangeType << " " << boost::timer::format(count_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Total time = " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws\n") << std::endl;
+ return total_time.elapsed();
+}
+
+template<typename C>
+void extensions_time(boost::container::vector<typename C::value_type> &sorted_unique_range)
+{
+ cpu_timer sur_timer,sur_opt_timer;
+ sur_timer.stop();sur_opt_timer.stop();
+
+ for(std::size_t i = 0; i != NIter; ++i){
+ {
+ sur_timer.resume();
+ C c(sorted_unique_range.begin(), sorted_unique_range.end());
+ sur_timer.stop();
+ }
+ {
+ sur_opt_timer.resume();
+ C c(boost::container::ordered_unique_range, sorted_unique_range.begin(), sorted_unique_range.end());
+ sur_opt_timer.stop();
+ }
+
+ }
+ std::cout << " Construct sorted_unique_range " << boost::timer::format(sur_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << " Construct sorted_unique_range (extension) " << boost::timer::format(sur_opt_timer.elapsed(), boost::timer::default_places, "%ws\n");
+ std::cout << "Extension/Standard: ";
+ compare_times(sur_opt_timer.elapsed(), sur_timer.elapsed());
+}
+
+template<class BoostClass, class StdClass>
+void launch_tests(const char *BoostContName, const char *StdContName)
+{
+ typedef range_provider<typename BoostClass::value_type> get_range_t;
+ try {
+ std::cout << "**********************************************" << '\n';
+ std::cout << "**********************************************" << '\n';
+ std::cout << '\n';
+ std::cout << BoostContName << " .VS " << StdContName << '\n';
+ std::cout << '\n';
+ std::cout << "**********************************************" << '\n';
+ std::cout << "**********************************************" << '\n' << std::endl;
+ {
+ std::cout << "Copy/Assign/Destroy benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = copy_destroy_time< BoostClass >(get_range_t::sorted_unique());
+
+ std::cout << "Copy/Assign/Destroy benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = copy_destroy_time< StdClass >(get_range_t::sorted_unique());
+
+ std::cout << BoostContName << "/" << StdContName << ": ";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Ordered construct benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = construct_time< BoostClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
+
+ std::cout << "Ordered construct benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = construct_time< StdClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");;
+
+ std::cout << BoostContName << "/" << StdContName << ": ";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Random construct benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = construct_time< BoostClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
+
+ std::cout << "Random construct benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = construct_time< StdClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");;
+
+ std::cout << BoostContName << "/" << StdContName << ": ";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Ordered Insert benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = insert_time< BoostClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
+
+ std::cout << "Ordered Insert benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = insert_time< StdClass >(get_range_t::sorted_unique(), get_range_t::sorted(), "(ord)");
+
+ std::cout << BoostContName << "/" << StdContName << ": ";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Random Insert benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = insert_time< BoostClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
+
+ std::cout << "Random Insert benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = insert_time< StdClass >(get_range_t::random_unique(), get_range_t::random(), "(rnd)");
+
+ std::cout << BoostContName << "/" << StdContName << ": ";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Ordered Search benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = search_time< BoostClass >(get_range_t::sorted_unique(), "(ord)");
+
+ std::cout << "Ordered Search benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = search_time< StdClass >(get_range_t::sorted_unique(), "(ord)");
+
+ std::cout << BoostContName << "/" << StdContName << ": ";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Random Search benchmark:" << BoostContName << std::endl;
+ cpu_times boost_set_time = search_time< BoostClass >(get_range_t::random_unique(), "(rnd)");
+
+ std::cout << "Random Search benchmark:" << StdContName << std::endl;
+ cpu_times std_set_time = search_time< StdClass >(get_range_t::random_unique(), "(rnd)");
+
+ std::cout << BoostContName << "/" << StdContName << ": ";
+ compare_times(boost_set_time, std_set_time);
+ }
+ {
+ std::cout << "Extensions benchmark:" << BoostContName << std::endl;
+ extensions_time< BoostClass >(get_range_t::sorted_unique());
+ }
+
+ }catch(std::exception e){
+ std::cout << e.what();
+ }
+}
+
+#endif //#ifndef BOOST_CONTAINER_BENCH_BENCH_SET_HPP