fork download
copy 
  1. #ifndef ASSOCIATIVE_H
  2. #define ASSOCIATIVE_H
  3. #include <algorithm>
  4. #include <functional>
  5. #include <iterator>
  6. #include <stdexcept>
  7. #include <type_traits>
  8. #include <vector>
  9.  
  10. template<class iterator> auto structure_dereference_operator(const iterator& r) -> typename std::iterator_traits<iterator>::pointer {return r.operator->();}
  11. template<class type> typename std::iterator_traits<type*>::pointer structure_dereference_operator(const type*& r) {return r;}
  12.  
  13. #pragma warning(push)
  14. #pragma warning(disable : 4820)  //warning C4820: 'associative<key_,mapped_>' : '3' bytes padding added after data member 'associative<key_,mapped_>::comp_'
  15. //http://msdn.microsoft.com/en-us/library/xdayte4c.aspx
  16. // carefully designed to also work on a linked list.  Not that you should, because that would be silly.
  17. template <class key_, 
  18.           class mapped_, 
  19.           class traits_ = std::less<key_>,
  20. 		  class undertype_ = std::vector<std::pair<key_,mapped_> >
  21.          >
  22. class associative
  23. {
  24. public:
  25. 	typedef traits_ key_compare;
  26. 	typedef key_ key_type;
  27. 	typedef mapped_ mapped_type;
  28. 	typedef std::pair<const key_type, mapped_type> value_type;
  29. 	typedef typename undertype_::allocator_type allocator_type;
  30. 	typedef typename allocator_type::template rebind<value_type>::other value_allocator_type;
  31. 	typedef typename undertype_::const_iterator const_iterator;
  32. 	typedef typename value_allocator_type::const_pointer const_pointer;
  33. 	typedef typename value_allocator_type::const_reference const_reference;
  34. 	typedef typename undertype_::const_reverse_iterator const_reverse_iterator;
  35. 	typedef typename value_allocator_type::difference_type difference_type;
  36. 	typedef typename value_allocator_type::pointer pointer;
  37. 	typedef typename value_allocator_type::reference reference;
  38. 	typedef typename undertype_::size_type size_type;
  39. 	static_assert(std::is_same<typename undertype_::value_type, std::pair<key_,mapped_> >::value, "container::value_type must be std::pair<key_,mapped_>");
  40. 	static_assert(std::is_same<typename undertype_::reference, typename allocator_type::reference>::value, "container::reference must be allocator_type::reference");
  41. 	static_assert(std::is_same<typename undertype_::pointer, typename allocator_type::pointer>::value, "container::pointer must be allocator_type::pointer");
  42. 	class value_compare {
  43. 		key_compare pred_;
  44. 	public:
  45. 		inline value_compare(key_compare pred=key_compare()) : pred_(pred) {}
  46. 		inline bool operator()(const value_type& left, const value_type& right) const {return pred_(left.first,right.first);}
  47. 		inline bool operator()(const value_type& left, const key_type& right) const {return pred_(left.first,right);}
  48. 		inline bool operator()(const key_type& left, const value_type& right) const {return pred_(left,right.first);}
  49. 		inline bool operator()(const key_type& left, const key_type& right) const {return pred_(left,right);}
  50. 		inline key_compare key_comp( ) const {return pred_;}
  51. 	};
  52. 	class iterator  {
  53. 	public:       
  54. 		typedef typename value_allocator_type::difference_type difference_type;
  55. 		typedef typename value_allocator_type::value_type value_type;
  56. 		typedef typename value_allocator_type::reference reference;
  57. 		typedef typename value_allocator_type::pointer pointer;
  58. 		typedef std::bidirectional_iterator_tag iterator_category;
  59. 		inline iterator() : data() {}
  60. 		inline iterator(const iterator& rhs) : data(rhs.data) {}
  61. 		inline iterator(const typename undertype_::iterator& rhs) : data(rhs) {}
  62. 		inline iterator& operator=(const iterator& rhs) {data=rhs.data;}
  63. 		inline iterator& operator=(const typename undertype_::iterator& rhs) {data=rhs;}
  64. 		inline bool operator==(const iterator& rhs) const {return data==rhs.data;}
  65. 		inline bool operator!=(const iterator& rhs) const {return data==rhs.data;} 
  66. 		inline iterator& operator++() {++data; return *this;}
  67. 		inline iterator operator++(int) {return iterator(data++);}
  68. 		inline iterator& operator--() {--data; return *this;}
  69. 		inline iterator operator--(int) {return iterator(data--);}
  70. 		inline reference operator*() const { return reinterpret_cast<reference>(*data);}
  71. 		inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));}
  72. 	protected:
  73. 		typename undertype_::iterator data;
  74. 	};
  75. 	typedef std::reverse_iterator<iterator> reverse_iterator;
  76.  
  77. 	inline associative() : internal_(), comp_() {}
  78. 	explicit associative(const key_compare& traits) : internal_(), comp_(traits) {}
  79.     inline associative(const key_compare& traits, const allocator_type& allocator) :internal_(allocator), comp_(traits) {}
  80.     inline associative(const associative& rhs) : internal_(rhs.internal_), comp_(rhs.comp_) {}
  81.     inline associative(associative&& rhs) : internal_(std::move(rhs.internal_)), comp_(std::move(rhs.comp_)) {}
  82.     template<class input_iterator>
  83.     inline associative(input_iterator first, input_iterator last) : internal_(first, last), comp_() 
  84. 	{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
  85.     template<class input_iterator>
  86.     inline associative(input_iterator first, input_iterator last, const key_compare& traits) : internal_(first, last, traits), comp_(traits) 
  87. 	{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
  88.     template<class input_iterator>
  89.     inline associative(input_iterator first, input_iterator last, const key_compare& traits, const allocator_type& allocator) : internal_(first, last, allocator), comp_(traits) 
  90. 	{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
  91. 	inline ~associative() {}
  92.  
  93. 	inline associative& operator=(const associative& right){internal_=right.internal_; comp_=right.comp_;}
  94.     inline associative& operator=(associative&& right){internal_=std::move(right.internal_); comp_=std::move(right.comp_);}
  95. 	inline const_iterator begin() const {return internal_.begin();}
  96.     inline iterator begin() {return internal_.begin();}
  97. 	inline const_iterator cbegin() const {return internal_.cbegin();}
  98.     inline const_iterator end() const {return internal_.end();}
  99.     inline iterator end() {return internal_.end();}
  100. 	inline const_iterator cend() const {return internal_.cend();} 
  101.     inline const_reverse_iterator rbegin() const {return internal_.rbegin();}
  102.     inline reverse_iterator rbegin() {return internal_.rbegin();}
  103. 	inline const_reverse_iterator crbegin() const {return internal_.crbegin();} 
  104.     inline const_reverse_iterator rend() const {return internal_.rend();}  
  105.     inline reverse_iterator rend() {return internal_.rend();}  
  106. 	inline const_reverse_iterator crend() const {return internal_.crend();}  
  107. 	inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {return std::equal_range(internal_.begin(), internal_.end(), key, comp_);}
  108.     inline std::pair<iterator, iterator> equal_range(const key_type& key) {return std::equal_range(internal_.begin(), internal_.end(), key, comp_);}
  109. 	inline iterator lower_bound(const key_type& key) 
  110. 	{return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
  111.     inline const_iterator lower_bound(const key_type& key) const {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
  112. 	inline iterator upper_bound(const key_type& key) {return std::upper_bound(internal_.begin(), internal_.end(), key, comp_);}
  113. 	inline iterator upper_bound(const key_type& key, iterator lower) {
  114. 		while(++lower!=internal_.end()&&comp_(key,lower->first))
  115. 			;
  116. 		return lower;
  117. 	}
  118.     inline const_iterator upper_bound(const key_type& key) const {return std::upper_bound(internal_.begin(), internal_.end(), key, comp_);}
  119. 	inline const_iterator upper_bound(const key_type& key, const_iterator lower) const {
  120. 		while(++lower!=internal_.end()&&comp_(key,lower->first))
  121. 			;
  122. 		return lower;
  123. 	}
  124.  
  125. 	mapped_type& at(const key_type& key) {
  126. 		iterator i = internal_.lower_bound(key);
  127. 		if (i == internal_.end() || comp_(i->first,key) || comp_(key, i->first))
  128. 			throw std::out_of_range("invalid associative<K, T> key");
  129. 		return i->second;
  130. 	}
  131.     const mapped_type& at(const key_type& key) const{
  132. 		iterator i = internal_.lower_bound(key);
  133. 		if (i == internal_.end() || comp_(i->first,key) || comp_(key, i->first))
  134. 			throw std::out_of_range("invalid associative<K, T> key");
  135. 		return i->second;
  136. 	}
  137. 	inline size_type count(const key_type& key) const {
  138. 		auto range = std::equal_range(internal_.begin(), internal_.end(), key, comp_);
  139. 		return size_type(std::distance(range.first, range.second));
  140. 	}
  141. 	template<class rhs_type> 
  142. 	inline std::pair<iterator, bool> emplace(rhs_type&& rhs) {return emplace_(lower_bound(rhs.first), std::move(rhs));}
  143. 	template<class rhs_type> 
  144. 	std::pair<iterator, bool> emplace_hint(const_iterator where, rhs_type&& rhs) {
  145. 		if (where==internal_.end()) { return emplace_(lower_bound(rhs.first), std::move(rhs));}
  146. 		if (comp_(where->first,rhs.first)) { return emplace_(lower_bound(rhs.first), std::move(rhs));}
  147. 		const_iterator n=where;
  148. 		++n;
  149. 		if(n==internal_.end() || comp(n, rhs.first))  { return emplace_(lower_bound(rhs.first), std::move(rhs));}
  150. 		return emplace_(where, std::move(rhs));
  151. 	}
  152. 	inline iterator erase(iterator where) {return internal_.erase(where);}
  153.     inline iterator erase(iterator first, iterator last) {return internal_.erase(first, last);}
  154.     inline size_type erase(const key_type& key) {auto r=count(key); internal_.erase(std::lower_bound(internal_.begin(), internal_.end(), key, comp_)); return r;}
  155. 	template<class predicate>
  156.     inline iterator remove_if(predicate pred) {internal_.erase(std::remove_if(internal_.begin(),internal_.end(),pred), internal_.end());}
  157. 	inline iterator find(const key_type& key) {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
  158.     inline const_iterator find(const key_type& key) const {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
  159. 	inline std::pair<iterator, bool> insert(const value_type& rhs) {return insert_(lower_bound(rhs.first), rhs);}
  160.     iterator insert(const_iterator where, const value_type& rhs) {
  161. 		if (where==internal_.end()) { return internal_.insert(lower_bound(rhs.first), rhs);}
  162. 		if (comp_(where->first,rhs.first)) { return internal_.insert(lower_bound(rhs.first), rhs);}
  163. 		const_iterator n=where;
  164. 		++n;
  165. 		if(n==internal_.end() || comp(n, rhs.first))  { return internal_.insert(lower_bound(rhs.first), rhs);}
  166. 		return internal_.insert(where, rhs);
  167. 	}
  168.     template<class input_iterator>
  169. 	void insert(input_iterator first, input_iterator last) {
  170. 		int s = internal_.size();
  171. 		while(first!=last) 
  172. 			internal_.insert(internal_.end(),*(first++));
  173. 		iterator mid(internal_.begin());
  174. 		std::advance(mid, s);
  175. 		std::inplace_merge(internal_.begin(), mid, internal_.end());
  176. 	}
  177.     template<class rhs_type>
  178.     inline std::pair<iterator, bool> insert(rhs_type&& rhs) {return emplace_(lower_bound(rhs.first), std::move(rhs));}
  179.     template<class rhs_type>
  180.     inline iterator insert(const_iterator where, rhs_type&& rhs) {return emplace(where, std::move(rhs));}
  181. 	inline mapped_type& operator[](const key_type& key) {return emplace(value_type(key, mapped_type())).first->second;}
  182. 	inline mapped_type& operator[](const key_type&& key) {return emplace(value_type(std::move(key), mapped_type())).first->second;}
  183. 	inline mapped_type& operator[](const key_type& key) const {return at(key);}
  184.  
  185. 	inline void clear() {internal_.clear();}
  186. 	inline bool empty() const {return internal_.empty();}
  187. 	inline size_type size( ) const {return internal_.size();}
  188. 	inline void swap(associative& rhs) {internal_.swap(rhs.internal_); std::swap(comp_,rhs.comp_);}
  189. 	inline friend void swap(associative& left, associative& right) {left.swap(right);}
  190.  
  191. 	inline allocator_type get_allocator() const {return internal_.get_allocator();}
  192. 	inline key_compare key_comp() const{return comp_.key_comp();}
  193. 	inline value_compare value_comp() const{return comp_;}
  194. 	inline size_type max_size() const{return internal_.max_size();}
  195.  
  196. 	inline friend bool operator==(const associative& left, const associative& right) {return std::equal(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), left.comp_);}
  197. 	inline friend bool operator!=(const associative& left, const associative& right) {return !std::equal(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), left.comp_);}
  198. 	inline friend bool operator< (const associative& left, const associative& right) {return std::lexicographical_compare(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), right.internal_.end(), left.comp_);}
  199. 	inline friend bool operator<=(const associative& left, const associative& right) {return std::lexicographical_compare(right.internal_.begin(), right.internal_.end(), left.internal_.begin(), left.internal_.end(), left.comp_);}
  200. 	inline friend bool operator> (const associative& left, const associative& right) {return !std::lexicographical_compare(right.internal_.begin(), right.internal_.end(), left.internal_.begin(), left.internal_.end(), left.comp_);}
  201. 	inline friend bool operator>=(const associative& left, const associative& right) {return !std::lexicographical_compare(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), right.internal_.end(), left.comp_);}
  202.  
  203. protected:
  204. 	undertype_ internal_;
  205. 	value_compare comp_;
  206.  
  207. 	template<class rhs_type> 
  208. 	std::pair<iterator,bool> emplace_(iterator where, rhs_type&& rhs) {
  209. 		if (where==internal_.end())
  210. 			return std::make_pair(internal_.emplace(where, std::move(rhs)), true);
  211. 		if (comp_(*where, rhs))
  212. 			return std::make_pair(where, true);
  213. 		return std::make_pair(internal_.emplace(where, std::move(rhs)), true);
  214. 	}
  215. 	template<class rhs_type> 
  216. 	std::pair<iterator,bool> insert_(iterator where, const rhs_type& rhs) {
  217. 		if (where==internal_.end())
  218. 			return std::make_pair(internal_.insert(where, rhs), true);
  219. 		if (comp_(*where, rhs))
  220. 			return std::make_pair(where, true);
  221. 		return std::make_pair(internal_.insert(where, rhs), true);
  222. 	}
  223. };
  224. #pragma warning(pop)
  225. namespace std {
  226. template<class key_, class mapped_, class traits_, class undertype_> 
  227. 	inline void swap(associative <key_, mapped_, traits_, undertype_>& left, associative <key_, mapped_, traits_, undertype_>& right)
  228. 	{left.swap(right);}
  229. };
  230.  
  231. #endif //ASSOCIATIVE_H
  232.  
  233.  
  234.  
  235.  
  236.  
  237. #include <cstdlib>
  238. #include <ctime>
  239. #include <fstream>
  240. #include <iomanip>
  241. #include <iostream>
  242. #include <iterator>
  243. #include <list>
  244. #include <map>
  245. #include <string>
  246. #include <vector>
  247.  
  248. #ifdef _DEBUG
  249. #define WARMUP_TIME_MILLISECONDS 1
  250. #define TEST_TIME_MILLISECONDS 9
  251. #else
  252. #define WARMUP_TIME_MILLISECONDS 10
  253. #define TEST_TIME_MILLISECONDS 450
  254. #endif
  255.  
  256. template<unsigned int size>
  257. struct payload {
  258. 	int data[size/4];
  259. 	payload() {data[0]=rand();}
  260. 	bool operator==(const payload& rhs) const {return data[0]==rhs.data[0];}
  261. 	bool operator<(const payload& rhs) const {return data[0]<rhs.data[0];}
  262. };
  263.  
  264. template<class payload, class container>
  265. void test_internal(const std::vector<std::pair<payload, payload>>& data, const char* classname, const char* payloadname) {
  266. 	clock_t beg,end,elapsed,freq;
  267. 	unsigned int count=0;
  268. 	bool timed=false;
  269. 	freq = CLOCKS_PER_SEC;
  270.  
  271. 	std::vector<std::pair<payload, payload>> shuffled(data.begin(), data.end());
  272. 	std::random_shuffle(shuffled.begin(), shuffled.end());
  273. 	std::vector<std::pair<payload, payload>> sorted(data.begin(), data.end());
  274. 	std::sort(sorted.begin(), sorted.end());
  275.  
  276. 	timed = false;
  277. 	elapsed = 0;
  278. 	std::cout << payloadname << ' ' << std::setw(4) << data.size() << ' ' << classname << ' ';
  279.     do {
  280. 		beg = clock();
  281. 	    container a(data.begin(), data.end());
  282. 	    end = clock();
  283. 		elapsed += end-beg;
  284.    	    if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
  285. 			elapsed =0;
  286. 			count=0;
  287.             timed = true;
  288. 	    }
  289. 		++count;
  290. 	} while(elapsed<TEST_TIME_MILLISECONDS);
  291. 	std::cout << std::setw(9) << count << ' ';
  292.  
  293. 	timed = false;
  294. 	elapsed = 0;
  295. 	{
  296. 	    container a(data.begin(), data.end());
  297. 		do {
  298. 			beg = clock();
  299. 			auto i=a.find(shuffled[count%data.size()].first);
  300. 			end = clock();
  301. 			elapsed += end-beg;
  302.    			if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
  303. 				elapsed =0;
  304. 				count=0;
  305. 				timed = true;
  306. 			}
  307. 			++count;
  308. 		} while(elapsed<TEST_TIME_MILLISECONDS);
  309. 	}
  310. 	std::cout << std::setw(9) << count << ' ';
  311.  
  312. 	timed = false;
  313. 	elapsed =0;
  314. 	{
  315. 		do {
  316. 			container a(data.begin(), data.end());
  317. 			beg = clock();
  318. 			for(unsigned int i=0; i<shuffled.size(); ++i)
  319. 				a.erase(shuffled[i].first);
  320. 			end = clock();
  321. 			elapsed += end-beg;
  322.    			if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
  323. 				elapsed =0;
  324. 				count=0;
  325. 				timed = true;
  326. 			}
  327. 			++count;
  328. 		} while(elapsed<TEST_TIME_MILLISECONDS);
  329. 	}
  330. 	std::cout << std::setw(9) << count << '\n';
  331. }
  332.  
  333. template<class payload>
  334. void test(const std::vector<std::pair<payload, payload>> &data, const char* payload_name) {
  335. 	std::vector<std::pair<payload, payload>> use(data.begin(), data.begin()+8);
  336. 	for( ; ; ) {
  337. 		test_internal<payload, std::map   <payload,payload>>(use, "std::map", payload_name);
  338. 		test_internal<payload, associative<payload,payload,std::less<payload>,std::vector<std::pair<payload,payload>>>>(use, "astv/vec", payload_name);
  339. 		if (use.size()<1024)
  340. 			use.insert(use.end(), data.begin()+use.size()*1ull, data.begin()+use.size()*2ull);
  341. 		else if (use.size() != data.size())
  342. 			use.insert(use.end(), data.begin()+use.size(), data.end());
  343. 		else break;
  344. 	}
  345. }
  346.  
  347. int main() {
  348. 	typedef associative<char,char,std::less<char>,std::list<std::pair<char,char>>> compile_but_dont_use;
  349. 	//std::vector<std::pair<std::string,std::string>> dynamic_data;
  350. 	////dynamic_data.reserve(2000);
  351. 	//{
  352. 	//	std::ifstream i("F:/Code/Contests/About53/2000words.txt");
  353. 	//	std::string line;
  354. 	//	for(;dynamic_data.size()<2000 && i>>line;)
  355. 	//		dynamic_data.push_back(std::make_pair(line, line));
  356. 	//	std::random_shuffle(dynamic_data.begin(), dynamic_data.end());
  357. 	//}
  358. 	std::cout << "bigger counts are best       inserts   lookups    erases\n";
  359. 	//test(dynamic_data,                                            "std::string ");
  360. 	//test(std::vector<std::pair<payload<  4>,payload<  4>>>(2000), "payload<  4>");
  361. 	test(std::vector<std::pair<payload<  8>,payload<  8>>>(2000), "payload<  8>");
  362. 	test(std::vector<std::pair<payload< 16>,payload< 16>>>(2000), "payload< 16>");
  363. 	test(std::vector<std::pair<payload< 32>,payload< 32>>>(2000), "payload< 32>");
  364. 	test(std::vector<std::pair<payload< 64>,payload< 64>>>(2000), "payload< 64>");
  365. 	test(std::vector<std::pair<payload<128>,payload<128>>>(2000), "payload<128>");
  366.  
  367. 	return 0;
  368. }
  369.  
Success #stdin #stdout 9.78s 3552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
bigger counts are best       inserts   lookups    erases
payload<  8>    8 std::map     21073     16052     15397
payload<  8>    8 astv/vec     39524     13495     17678
payload<  8>   16 std::map     28588     19473     17572
payload<  8>   16 astv/vec      5726     20006      3026
payload<  8>   32 std::map     11059     28316      9747
payload<  8>   32 astv/vec     13352     13136      6124
payload<  8>   64 std::map      5211     82406      7999
payload<  8>   64 astv/vec     30583     36850      1074
payload<  8>  128 std::map      4250     17837      2604
payload<  8>  128 astv/vec     11855     24373       340
payload<  8>  256 std::map      1980     15699      3443
payload<  8>  256 astv/vec      3860     14904       111
payload<  8>  512 std::map      1248     23648       585
payload<  8>  512 astv/vec      3210     19812        58
payload<  8> 1024 std::map       577     34441       913
payload<  8> 1024 astv/vec      1841     21397         8
payload<  8> 2000 std::map       298      1568       303
payload<  8> 2000 astv/vec      1097     17120         3
payload< 16>    8 std::map     27718     38763     11559
payload< 16>    8 astv/vec     28214     27633      8320
payload< 16>   16 std::map     17358      8749      5921
payload< 16>   16 astv/vec      4558     18905      6446
payload< 16>   32 std::map     11311     31213     11984
payload< 16>   32 astv/vec     28443     22836      2495
payload< 16>   64 std::map      4979      8749      3680
payload< 16>   64 astv/vec     24020     20120       820
payload< 16>  128 std::map      3933     20265      2447
payload< 16>  128 astv/vec      2410     33166       253
payload< 16>  256 std::map      1931     49411      1029
payload< 16>  256 astv/vec      3253     16879        72
payload< 16>  512 std::map       936     16893      1149
payload< 16>  512 astv/vec      1900     66748        20
payload< 16> 1024 std::map       491     37897       842
payload< 16> 1024 astv/vec       847     22063         5
payload< 16> 2000 std::map       260     21466       620
payload< 16> 2000 astv/vec       620     15970         2
payload< 32>    8 std::map       994     25774     54839
payload< 32>    8 astv/vec     68280     76845      9581
payload< 32>   16 std::map      1282     18708     19404
payload< 32>   16 astv/vec      1031     55059      6618
payload< 32>   32 std::map     16814     16870      7973
payload< 32>   32 astv/vec     14240     33380      2089
payload< 32>   64 std::map      1538     50890     10579
payload< 32>   64 astv/vec      6455     38312       542
payload< 32>  128 std::map      5960     24589      1761
payload< 32>  128 astv/vec      3854     21370       140
payload< 32>  256 std::map      1454     18457      6039
payload< 32>  256 astv/vec      2603     56827        39
payload< 32>  512 std::map       774     37756       981
payload< 32>  512 astv/vec       954      8847        10
payload< 32> 1024 std::map       374    114518       495
payload< 32> 1024 astv/vec       419     70923         3
payload< 32> 2000 std::map       197     54806       133
payload< 32> 2000 astv/vec       340     19378         2
payload< 64>    8 std::map      2743      1549     49261
payload< 64>    8 astv/vec     16586     33224     10589
payload< 64>   16 std::map      6519     14561      8548
payload< 64>   16 astv/vec     13565     38891      6132
payload< 64>   32 std::map      3960     32398     15104
payload< 64>   32 astv/vec      2758     84630       964
payload< 64>   64 std::map      4285     32098     17677
payload< 64>   64 astv/vec      1937     12287       287
payload< 64>  128 std::map      1380     17222      4977
payload< 64>  128 astv/vec      2009     15384        78
payload< 64>  256 std::map      1129     17505       863
payload< 64>  256 astv/vec      1133     19852        23
payload< 64>  512 std::map       604     12294      1594
payload< 64>  512 astv/vec       411     22459         6
payload< 64> 1024 std::map       254      5794       580
payload< 64> 1024 astv/vec       239     45372         2
payload< 64> 2000 std::map       132     16761        90
payload< 64> 2000 astv/vec       159     14006         2
payload<128>    8 std::map      4698    127712     18273
payload<128>    8 astv/vec     12739     66562      9264
payload<128>   16 std::map      5269     34339      9770
payload<128>   16 astv/vec      5249     13696      1358
payload<128>   32 std::map      4435      2933     15647
payload<128>   32 astv/vec      3877     73054       429
payload<128>   64 std::map      2069     19975      1883
payload<128>   64 astv/vec      2260     16991       106
payload<128>  128 std::map      1257     34666      6025
payload<128>  128 astv/vec      1123     17108        56
payload<128>  256 std::map       567      7800      3319
payload<128>  256 astv/vec       483    114836         8
payload<128>  512 std::map       298     20910       768
payload<128>  512 astv/vec       248      8815         3
payload<128> 1024 std::map       149     43726       126
payload<128> 1024 astv/vec       117     57967         2
payload<128> 2000 std::map        77     43398        63
payload<128> 2000 astv/vec        52     21720         2
https://ideone.com/G9ZNs
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
public

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!