fork download 
  1. #include <algorithm>
  2. #include <iterator>
  3. #include <vector>
  4.  
  5. template<class iterator> auto structure_dereference_operator(const iterator& r) -> typename std::iterator_traits<iterator>::pointer {return r.operator->();}
  6. template<class type> typename std::iterator_traits<type*>::pointer structure_dereference_operator(const type*& r) {return r;}
  7.  
  8. template <class key_, 
  9.           class mapped_, 
  10.           class traits_ = std::less<key_>,
  11. 		  class undertype_ = std::vector<std::pair<key_,mapped_> >
  12.          >
  13. class associative
  14. {
  15. public:
  16. 	typedef traits_ key_compare;
  17. 	typedef key_ key_type;
  18. 	typedef mapped_ mapped_type;
  19. 	typedef std::pair<const key_type, mapped_type> value_type;
  20. 	typedef typename undertype_::allocator_type allocator_type;
  21. 	typedef typename allocator_type::template rebind<value_type>::other value_allocator_type;
  22. 	typedef typename undertype_::const_iterator const_iterator;
  23.  
  24. 	class value_compare {
  25. 		key_compare pred_;
  26. 	public:
  27. 		inline value_compare(key_compare pred=key_compare()) : pred_(pred) {}
  28. 		inline bool operator()(const value_type& left, const value_type& right) const {return pred_(left.first,right.first);}
  29. 		inline bool operator()(const value_type& left, const key_type& right) const {return pred_(left.first,right);}
  30. 		inline bool operator()(const key_type& left, const value_type& right) const {return pred_(left,right.first);}
  31. 		inline bool operator()(const key_type& left, const key_type& right) const {return pred_(left,right);}
  32. 		inline key_compare key_comp( ) const {return pred_;}
  33. 	};
  34. 	class iterator  {
  35. 	public:       
  36. 		typedef typename value_allocator_type::difference_type difference_type;
  37. 		typedef typename value_allocator_type::value_type value_type;
  38. 		typedef typename value_allocator_type::reference reference;
  39. 		typedef typename value_allocator_type::pointer pointer;
  40. 		typedef std::bidirectional_iterator_tag iterator_category;
  41. 		inline iterator(const typename undertype_::iterator& rhs) : data(rhs) {}
  42. 		inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));}
  43. 		operator const_iterator&() const {return data;}
  44. 	protected:
  45. 		typename undertype_::iterator data;
  46. 	};
  47.  
  48.     template<class input_iterator>
  49.     inline associative(input_iterator first, input_iterator last) : internal_(first, last), comp_() 
  50. 	{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
  51.  
  52. 	inline iterator find(const key_type& key) {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
  53.     inline const_iterator find(const key_type& key) const {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
  54.  
  55. protected:
  56. 	undertype_ internal_;
  57. 	value_compare comp_;
  58. };
  59.  
  60. #include <cstdlib>
  61. #include <ctime>
  62. #include <fstream>
  63. #include <iomanip>
  64. #include <iostream>
  65. #include <map>
  66.  
  67. #ifdef _DEBUG
  68. #define WARMUP_TIME_MILLISECONDS 1
  69. #define TEST_TIME_MILLISECONDS 9
  70. #else
  71. #define WARMUP_TIME_MILLISECONDS 10
  72. #define TEST_TIME_MILLISECONDS 400
  73. #endif
  74.  
  75. template<unsigned int size>
  76. struct payload {
  77. 	int data[size/4];
  78. 	payload() {data[0]=rand()*RAND_MAX+rand();}
  79. 	bool operator==(const payload& rhs) const {return data[0]==rhs.data[0];}
  80. 	bool operator<(const payload& rhs) const {return data[0]<rhs.data[0];}
  81. };
  82.  
  83. template<class load, class container>
  84. void test_internal(const std::vector<std::pair<load, load>>& data, const char* classname, const char* payloadname) {
  85. 	clock_t beg,end,elapsed,freq;
  86. 	unsigned int count=0;
  87. 	bool timed=false;
  88. 	freq = CLOCKS_PER_SEC;
  89.  
  90. 	std::vector<std::pair<load, load>> shuffled(data.begin(), data.end());
  91. 	std::random_shuffle(shuffled.begin(), shuffled.end());
  92. 	std::vector<std::pair<load, load>> sorted(data.begin(), data.end());
  93. 	std::sort(sorted.begin(), sorted.end());
  94.  
  95. 	std::cout << payloadname << ' ' << std::setw(4) << data.size() << ' ' << classname << ' ';
  96. 	timed = false;
  97. 	elapsed = 0;
  98. 	{
  99. 	    container a(data.begin(), data.end());
  100. 		do {
  101. 			beg = clock();
  102. 			auto i=a.find(shuffled[count%data.size()].first);
  103. 			end = clock();
  104. 			elapsed += end-beg;
  105.    			if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
  106. 				elapsed =0;
  107. 				count=0;
  108. 				timed = true;
  109. 			}
  110. 			++count;
  111. 		} while(elapsed<TEST_TIME_MILLISECONDS);
  112. 	}
  113. 	std::cout << std::setw(9) << count << '\n';
  114. }
  115.  
  116. template<class load>
  117. void test(const std::vector<std::pair<load, load>> &data, const char* payload_name) {
  118. 	std::vector<std::pair<load, load>> use(data.begin(), data.begin()+8);
  119. 	for( ; ; ) {
  120. 		test_internal<load, std::map   <load,load>>(use, "std::map", payload_name);
  121. 		test_internal<load, associative<load,load,std::less<load>,std::vector<std::pair<load,load>>>>(use, "astv/vec", payload_name);
  122. 		if (use.size()<1024)
  123. 			use.insert(use.end(), data.begin()+use.size()*1ull, data.begin()+use.size()*2ull);
  124. 		else if (use.size() != data.size())
  125. 			use.insert(use.end(), data.begin()+use.size(), data.end());
  126. 		else break;
  127. 	}
  128. }
  129.  
  130. int main() {
  131. 	test(std::vector<std::pair<payload<  4>,payload<  4>>>(2000), "payload<  4>");
  132. 	test(std::vector<std::pair<payload<  8>,payload<  8>>>(2000), "payload<  8>");
  133. 	test(std::vector<std::pair<payload< 16>,payload< 16>>>(2000), "payload< 16>");
  134. 	test(std::vector<std::pair<payload< 32>,payload< 32>>>(2000), "payload< 32>");
  135. 	test(std::vector<std::pair<payload< 64>,payload< 64>>>(2000), "payload< 64>");
  136. 	test(std::vector<std::pair<payload<128>,payload<128>>>(2000), "payload<128>");
  137.  
  138. 	return 0;
  139. }
  140.  
Success #stdin #stdout 4.47s 3548KB
comments (?)
stdin 
Standard input is empty
stdout 
payload<  4>    8 std::map     33599
payload<  4>    8 astv/vec     18834
payload<  4>   16 std::map     22176
payload<  4>   16 astv/vec     32884
payload<  4>   32 std::map     60337
payload<  4>   32 astv/vec      2994
payload<  4>   64 std::map     18328
payload<  4>   64 astv/vec     56509
payload<  4>  128 std::map     40379
payload<  4>  128 astv/vec     39685
payload<  4>  256 std::map     19003
payload<  4>  256 astv/vec     13880
payload<  4>  512 std::map     36029
payload<  4>  512 astv/vec     72882
payload<  4> 1024 std::map     38000
payload<  4> 1024 astv/vec     21224
payload<  4> 2000 std::map     20498
payload<  4> 2000 astv/vec     43237
payload<  8>    8 std::map     50547
payload<  8>    8 astv/vec     16165
payload<  8>   16 std::map     51889
payload<  8>   16 astv/vec     39787
payload<  8>   32 std::map     17533
payload<  8>   32 astv/vec      5623
payload<  8>   64 std::map     17828
payload<  8>   64 astv/vec      1460
payload<  8>  128 std::map     17643
payload<  8>  128 astv/vec     39168
payload<  8>  256 std::map     23735
payload<  8>  256 astv/vec     12991
payload<  8>  512 std::map     51787
payload<  8>  512 astv/vec      7220
payload<  8> 1024 std::map     38081
payload<  8> 1024 astv/vec      7759
payload<  8> 2000 std::map     35414
payload<  8> 2000 astv/vec     37628
payload< 16>    8 std::map     16674
payload< 16>    8 astv/vec     14736
payload< 16>   16 std::map     54363
payload< 16>   16 astv/vec     17580
payload< 16>   32 std::map     57727
payload< 16>   32 astv/vec     21364
payload< 16>   64 std::map     21711
payload< 16>   64 astv/vec      3590
payload< 16>  128 std::map     21913
payload< 16>  128 astv/vec     44745
payload< 16>  256 std::map     14510
payload< 16>  256 astv/vec     28358
payload< 16>  512 std::map     38299
payload< 16>  512 astv/vec     11352
payload< 16> 1024 std::map     58018
payload< 16> 1024 astv/vec     29524
payload< 16> 2000 std::map     34784
payload< 16> 2000 astv/vec     15695
payload< 32>    8 std::map     40986
payload< 32>    8 astv/vec     18771
payload< 32>   16 std::map     16305
payload< 32>   16 astv/vec     24076
payload< 32>   32 std::map     16483
payload< 32>   32 astv/vec      3688
payload< 32>   64 std::map     56859
payload< 32>   64 astv/vec     33015
payload< 32>  128 std::map     25408
payload< 32>  128 astv/vec     11563
payload< 32>  256 std::map     55746
payload< 32>  256 astv/vec     20071
payload< 32>  512 std::map     35143
payload< 32>  512 astv/vec     41944
payload< 32> 1024 std::map     28021
payload< 32> 1024 astv/vec     54433
payload< 32> 2000 std::map     35346
payload< 32> 2000 astv/vec     24254
payload< 64>    8 std::map     15495
payload< 64>    8 astv/vec     18337
payload< 64>   16 std::map     10669
payload< 64>   16 astv/vec     17765
payload< 64>   32 std::map     16545
payload< 64>   32 astv/vec     13361
payload< 64>   64 std::map     20873
payload< 64>   64 astv/vec      2897
payload< 64>  128 std::map     51171
payload< 64>  128 astv/vec     38736
payload< 64>  256 std::map     33707
payload< 64>  256 astv/vec     74476
payload< 64>  512 std::map     17517
payload< 64>  512 astv/vec     71373
payload< 64> 1024 std::map      2956
payload< 64> 1024 astv/vec     35336
payload< 64> 2000 std::map     18962
payload< 64> 2000 astv/vec     67859
payload<128>    8 std::map      1991
payload<128>    8 astv/vec     18178
payload<128>   16 std::map      6908
payload<128>   16 astv/vec     62143
payload<128>   32 std::map     14767
payload<128>   32 astv/vec      7237
payload<128>   64 std::map      1469
payload<128>   64 astv/vec     33151
payload<128>  128 std::map     19062
payload<128>  128 astv/vec     18513
payload<128>  256 std::map      4838
payload<128>  256 astv/vec     16624
payload<128>  512 std::map     22279
payload<128>  512 astv/vec     18993
payload<128> 1024 std::map     16973
payload<128> 1024 astv/vec     14686
payload<128> 2000 std::map     50912
payload<128> 2000 astv/vec     21192
https://ideone.com/Ufn7r
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!