fork download
copy 
  1. #ifndef ASSOCIATIVE_H
  2. #define ASSOCIATIVE_H
  3. #pragma once
  4. #include <algorithm>
  5. #include <cassert>
  6. #include <functional>
  7. #include <iterator>
  8. #include <stdexcept>
  9. #include <type_traits>
  10. #include <vector>
  11.  
  12. template<class iterator> inline auto structure_dereference_operator(const iterator& r) -> typename std::iterator_traits<iterator>::pointer {return r.operator->();}
  13. template<class type> inline typename std::iterator_traits<type*>::pointer structure_dereference_operator(const type*& r) {return r;}
  14.  
  15. #pragma warning(push)
  16. #pragma warning(disable : 4820)  //warning C4820: 'associative<key_,mapped_>' : '3' bytes padding added after data member 'associative<key_,mapped_>::comp_'
  17. //http://msdn.microsoft.com/en-us/library/xdayte4c.aspx
  18. // carefully designed to also work on a linked list.  Not that you should, because that would be silly.
  19. template <class key_, 
  20.           class mapped_, 
  21.           class traits_ = std::less<key_>,
  22. 		  class undertype_ = std::vector<std::pair<key_,mapped_> >
  23.          >
  24. class associative
  25. {
  26. public:
  27. 	typedef traits_ key_compare;
  28. 	typedef key_ key_type;
  29. 	typedef mapped_ mapped_type;
  30. 	typedef std::pair<const key_type, mapped_type> value_type;
  31. 	typedef typename undertype_::allocator_type allocator_type;
  32. 	typedef typename allocator_type::template rebind<value_type>::other value_allocator_type;
  33. 	typedef typename undertype_::const_iterator const_iterator;
  34. 	typedef typename value_allocator_type::const_pointer const_pointer;
  35. 	typedef typename value_allocator_type::const_reference const_reference;
  36. 	typedef typename undertype_::const_reverse_iterator const_reverse_iterator;
  37. 	typedef typename value_allocator_type::difference_type difference_type;
  38. 	typedef typename value_allocator_type::pointer pointer;
  39. 	typedef typename value_allocator_type::reference reference;
  40. 	typedef typename undertype_::size_type size_type;
  41. 	typedef typename undertype_::iterator underiter;
  42. 	typedef typename undertype_::const_iterator underciter;
  43. 	typedef typename undertype_::reverse_iterator underriter;
  44. 	typedef std::pair<key_type, mapped_type> undertype;
  45. 	static_assert(std::is_same<typename undertype_::value_type, undertype >::value, "container::value_type must be std::pair<key_,mapped_>");
  46. 	static_assert(std::is_same<typename undertype_::reference, typename allocator_type::reference>::value, "container::reference must be allocator_type::reference");
  47. 	static_assert(std::is_same<typename undertype_::pointer, typename allocator_type::pointer>::value, "container::pointer must be allocator_type::pointer");
  48. 	class value_compare {
  49. 		key_compare pred_;
  50. 	public:
  51. 		inline value_compare(key_compare pred=key_compare()) : pred_(pred) {}
  52.         template <typename L, typename R>
  53.         inline bool operator()(const L& left, const R& right) const { return pred_(left.first,right.first); }
  54.         template <typename L>
  55.         inline bool operator()(const L& left, const key_type& right) const { return pred_(left.first,right); }
  56.         template <typename R>
  57.         inline bool operator()(const key_type& left, const R& right) const { return pred_(left,right.first); }
  58.         inline bool operator()(const key_type& left, const key_type& right) const { return pred_(left,right); }
  59. 		inline key_compare key_comp( ) const {return pred_;}
  60. 	};
  61. 	class iterator  {
  62. 	public:       
  63. 		friend class associative<key_,mapped_,traits_,undertype_>;
  64.  
  65. 		typedef typename value_allocator_type::difference_type difference_type;
  66. 		typedef typename value_allocator_type::value_type value_type;
  67. 		typedef typename value_allocator_type::reference reference;
  68. 		typedef typename value_allocator_type::pointer pointer;
  69. 		typedef std::bidirectional_iterator_tag iterator_category;
  70.  
  71. 		inline iterator() : data() {}
  72. 		inline iterator(const iterator& rhs) : data(rhs.data) {}
  73. 		inline iterator& operator=(const iterator& rhs) {data=rhs.data; return *this;}
  74. 		inline bool operator==(const iterator& rhs) const {return data==rhs.data;}
  75. 		inline bool operator!=(const iterator& rhs) const {return data!=rhs.data;} 
  76. 		inline iterator& operator++() {++data; return *this;}
  77. 		inline iterator operator++(int) {return iterator(data++);}
  78. 		inline iterator& operator--() {--data; return *this;}
  79. 		inline iterator operator--(int) {return iterator(data--);}
  80. 		inline reference operator*() const { return reinterpret_cast<reference>(*data);} //cant const_cast half of a pair
  81. 		inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));} //cant const_cast half of a pair
  82. 		inline operator const_iterator&() {return data;}
  83. 	protected:
  84. 		explicit inline iterator(const underiter& rhs) : data(rhs) {}
  85. 		underiter data;
  86. 	};
  87. 	class reverse_iterator  {
  88. 	public:       
  89. 		friend class associative<key_,mapped_,traits_,undertype_>;
  90.  
  91. 		typedef typename value_allocator_type::difference_type difference_type;
  92. 		typedef typename value_allocator_type::value_type value_type;
  93. 		typedef typename value_allocator_type::reference reference;
  94. 		typedef typename value_allocator_type::pointer pointer;
  95. 		typedef std::bidirectional_iterator_tag iterator_category;
  96.  
  97. 		inline reverse_iterator() : data() {}
  98. 		inline reverse_iterator(const reverse_iterator& rhs) : data(rhs.data) {}
  99. 		inline reverse_iterator& operator=(const reverse_iterator& rhs) {data=rhs.data; return *this;}
  100. 		inline bool operator==(const reverse_iterator& rhs) const {return data==rhs.data;}
  101. 		inline bool operator!=(const reverse_iterator& rhs) const {return data!=rhs.data;} 
  102. 		inline reverse_iterator& operator++() {++data; return *this;}
  103. 		inline reverse_iterator operator++(int) {return reverse_iterator(data++);}
  104. 		inline reverse_iterator& operator--() {--data; return *this;}
  105. 		inline reverse_iterator operator--(int) {return reverse_iterator(data--);}
  106. 		inline reference operator*() const { return reinterpret_cast<reference>(*data);} //cant const_cast half of a pair
  107. 		inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));} //cant const_cast half of a pair
  108. 		inline operator underriter&() {return data;}
  109. 	protected:
  110. 		explicit inline reverse_iterator(const underriter& rhs) : data(rhs) {}
  111. 		underriter data;
  112. 	};
  113.  
  114. 	inline associative() : internal_(), comp_() {}
  115. 	explicit associative(const key_compare& traits) : internal_(), comp_(traits) {}
  116.     inline associative(const key_compare& traits, const allocator_type& allocator) :internal_(allocator), comp_(traits) {}
  117.     inline associative(const associative& rhs) : internal_(rhs.internal_), comp_(rhs.comp_) {}
  118.     inline associative(associative&& rhs) : internal_(std::move(rhs.internal_)), comp_(std::move(rhs.comp_)) {}
  119.     template<class input_iterator>
  120.     inline associative(input_iterator first, input_iterator last) : internal_(first, last), comp_() 
  121. 	{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
  122.     template<class input_iterator>
  123.     inline associative(input_iterator first, input_iterator last, const key_compare& traits) : internal_(first, last, traits), comp_(traits) 
  124. 	{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
  125.     template<class input_iterator>
  126.     inline associative(input_iterator first, input_iterator last, const key_compare& traits, const allocator_type& allocator) : internal_(first, last, allocator), comp_(traits) 
  127. 	{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
  128. 	inline ~associative() {}
  129.  
  130. 	//TODO assign from different underlying type
  131. 	inline associative& operator=(const associative& right){internal_=right.internal_; comp_=right.comp_; return *this;}
  132.     inline associative& operator=(associative&& right){internal_=std::move(right.internal_); comp_=std::move(right.comp_); return *this;}
  133. 	inline const_iterator begin() const {return internal_.begin();}
  134.     inline iterator begin() {return iterator(internal_.begin());}
  135. 	inline const_iterator cbegin() const {return internal_.cbegin();}
  136.     inline const_iterator end() const {return internal_.end();}
  137.     inline iterator end() {return iterator(internal_.end());}
  138. 	inline const_iterator cend() const {return internal_.cend();} 
  139.     inline const_reverse_iterator rbegin() const {return internal_.rbegin();}
  140.     inline reverse_iterator rbegin() {return reverse_iterator(internal_.rbegin());}
  141. 	inline const_reverse_iterator crbegin() const {return internal_.crbegin();} 
  142.     inline const_reverse_iterator rend() const {return internal_.rend();}  
  143.     inline reverse_iterator rend() {return reverse_iterator(internal_.rend());}  
  144. 	inline const_reverse_iterator crend() const {return internal_.crend();}  
  145. 	inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {return std::equal_range(internal_.begin(), internal_.end(), key, comp_);}
  146.     inline std::pair<iterator, iterator> equal_range(const key_type& key) {
  147. 		auto i = std::equal_range(internal_.begin(), internal_.end(), key, comp_);
  148. 		return std::pair<iterator, iterator>(iterator(i.first), iterator(i.second));
  149. 	}
  150. 	inline iterator lower_bound(const key_type& key) {return iterator(std::lower_bound(internal_.begin(), internal_.end(), key, comp_));}
  151.     inline const_iterator lower_bound(const key_type& key) const {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
  152. 	inline iterator upper_bound(const key_type& key) {return iterator(std::upper_bound(internal_.begin(), internal_.end(), key, comp_));}
  153.     inline const_iterator upper_bound(const key_type& key) const {return std::upper_bound(internal_.begin(), internal_.end(), key, comp_);}
  154.  
  155. 	inline mapped_type& at(const key_type& key) {
  156. 		underiter i = std::lower_bound(internal_.begin(), internal_.end(), key, comp_);
  157. 		if (i==internal_.end() || comp_(key,*i))
  158. 			throw std::out_of_range("invalid associative<K, T> key");
  159. 		return i->second;
  160. 	}
  161.     inline const mapped_type& at(const key_type& key) const {
  162. 		underciter i = std::lower_bound(internal_.begin(), internal_.end(), key, comp_);
  163. 		if (i==internal_.end() || comp_(key,*i))
  164. 			throw std::out_of_range("invalid associative<K, T> key");
  165. 		return i->second;
  166. 	}
  167. 	inline size_type count(const key_type& key) const {
  168. 		underciter i = std::lower_bound(internal_.begin(), internal_.end(), key, comp_);
  169. 		return (i==internal_.end() || comp_(key,*i) ? 0u : 1u);
  170. 	}
  171. 	template<class rhs_type> 
  172. 	inline std::pair<iterator, bool> emplace(rhs_type&& rhs) {
  173. 		underiter i = std::lower_bound(internal_.begin(), internal_.end(), rhs, comp_);
  174. 		if (i==internal_.end() || comp_(rhs,*i))
  175. 			return std::pair<iterator,bool>(iterator(internal_.emplace(i, std::move(rhs))), true);
  176. 		else {
  177. 			*i = std::move(rhs);
  178. 			return std::pair<iterator,bool>(iterator(i), false);
  179. 		}
  180. 	}
  181. 	template<class rhs_type> 
  182. 	std::pair<iterator, bool> emplace_hint(const_iterator where, rhs_type&& rhs) {
  183. 		//TODO fix insert back
  184. 		if (where==internal_.end()) { return std::pair<iterator,bool>(iterator(internal_.emplace(where, std::move(rhs))), true);}
  185. 		if (!comp_(rhs,*where)) { return emplace(std::move(rhs));}
  186. 		if (where == internal_.begin()) {return std::pair<iterator,bool>(iterator(internal_.emplace(where, std::move(rhs))), true);}
  187. 		const_iterator n=where;
  188. 		--n;
  189. 		if(comp_(rhs,n))  { return emplace(std::move(rhs));}
  190. 		return std::pair<iterator,bool>(iterator(internal_.emplace(where, std::move(rhs))), true);
  191. 	}
  192. 	inline iterator erase(iterator where) {return iterator(internal_.erase(where));}
  193.     inline iterator erase(iterator first, iterator last) {return iterator(internal_.erase(first, last));}
  194.     inline size_type erase(const key_type& key) {
  195. 		underiter i = std::lower_bound(internal_.begin(), internal_.end(), key, comp_);
  196. 		if (i==internal_.end() || comp_(key,*i))
  197. 			return 0;
  198. 		internal_.erase(i);
  199. 		return 1;
  200. 	}
  201. 	template<class predicate>
  202.     inline iterator remove_if(predicate pred) {iterator(internal_.erase(std::remove_if(internal_.begin(),internal_.end(),pred), internal_.end()));}
  203. 	inline iterator find(const key_type& key) {
  204. 		underiter i = std::lower_bound(internal_.begin(), internal_.end(), key, comp_);
  205. 		return iterator((i==internal_.end() || comp_(key,*i)) ? internal_.end() : i);
  206. 	}
  207.     inline const_iterator find(const key_type& key) const {
  208. 		underciter i = std::lower_bound(internal_.begin(), internal_.end(), key, comp_);
  209. 		return const_iterator((i==internal_.end() || comp_(key,*i)) ? internal_.end() : i);
  210. 	}
  211. 	inline std::pair<iterator, bool> insert(const value_type& rhs) {
  212. 		underiter i = std::lower_bound(internal_.begin(), internal_.end(), rhs, comp_);
  213. 		if (i==internal_.end() || comp_(rhs,*i)) 
  214. 			return std::pair<iterator, bool>(iterator(internal_.emplace(i, std::move(rhs))), true);
  215. 		else {
  216. 			*i = std::move(rhs);
  217. 			return std::pair<iterator, bool>(iterator(i), false);
  218. 		}
  219. 	}
  220.     iterator insert(const_iterator where, const value_type& rhs) {
  221. 		//TODO fix insert back
  222. 		if (where==internal_.end()) { return iterator(internal_.insert(where, rhs));}
  223. 		if (!comp_(rhs,*where)) { return insert(rhs).first;}
  224. 		if (where == internal_.begin()) {return iterator(internal_.insert(where, rhs));}
  225. 		underciter n=where;
  226. 		--n;
  227. 		if(comp_(rhs,*n))  { return insert(rhs).first;}
  228. 		return iterator(internal_.insert(where, rhs));
  229. 	}
  230.     template<class input_iterator>
  231. 	void insert(input_iterator first, input_iterator last) {
  232. 		int s = std::distance(first, last);
  233. 		while(first!=last) 
  234. 			internal_.insert(internal_.end(),*(first++));
  235. 		iterator mid(internal_.end());
  236. 		std::advance(mid, -s);
  237. 		std::inplace_merge(internal_.begin(), mid, internal_.end());
  238. 	}
  239.     template<class rhs_type>
  240.     inline std::pair<iterator, bool> insert(rhs_type&& rhs) {return emplace(std::move(rhs));}
  241.     template<class rhs_type>
  242.     inline iterator insert(const_iterator where, rhs_type&& rhs) {return emplace(where, std::move(rhs));}
  243. 	inline mapped_type& operator[](const key_type& key) {return insert(value_type(key, mapped_type())).first->second;}
  244. 	inline mapped_type& operator[](const key_type&& key) {return emplace(value_type(std::move(key), mapped_type())).first->second;}
  245. 	inline const mapped_type& operator[](const key_type& key) const {return at(key);}
  246.  
  247. 	inline void clear() {internal_.clear();}
  248. 	inline bool empty() const {return internal_.empty();}
  249. 	inline size_type size( ) const {return internal_.size();}
  250. 	inline void swap(associative& rhs) {internal_.swap(rhs.internal_); std::swap(comp_,rhs.comp_);}
  251. 	inline friend void swap(associative& left, associative& right) {left.swap(right);}
  252.  
  253. 	inline allocator_type get_allocator() const {return internal_.get_allocator();}
  254. 	inline key_compare key_comp() const{return comp_.key_comp();}
  255. 	inline value_compare value_comp() const{return comp_;}
  256. 	inline size_type max_size() const{return internal_.max_size();}
  257.  
  258. 	inline friend bool operator==(const associative& left, const associative& right) {return std::equal(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), left.comp_);}
  259. 	inline friend bool operator!=(const associative& left, const associative& right) {return !std::equal(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), left.comp_);}
  260. 	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_);}
  261. 	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_);}
  262. 	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_);}
  263. 	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_);}
  264.  
  265. protected:
  266. 	undertype_ internal_;
  267. 	value_compare comp_;
  268. };
  269. #pragma warning(pop)
  270. namespace std {
  271. template<class key_, class mapped_, class traits_, class undertype_> 
  272. 	inline void swap(associative <key_, mapped_, traits_, undertype_>& left, associative <key_, mapped_, traits_, undertype_>& right)
  273. 	{left.swap(right);}
  274. };
  275.  
  276. #endif //ASSOCIATIVE_H
  277.  
  278.  
  279. #include <cassert>
  280. #include <cstdlib>
  281. #include <ctime>
  282. #include <deque>
  283. #include <fstream>
  284. #include <iomanip>
  285. #include <iostream>
  286. #include <iterator>
  287. #include <list>
  288. #include <map>
  289. #include <string>
  290. #include <vector>
  291.  
  292.  
  293. #ifdef _DEBUG
  294. #define WARMUP_TIME_MILLISECONDS 1
  295. #define TEST_TIME_MILLISECONDS 9
  296. #else
  297. #define WARMUP_TIME_MILLISECONDS 100
  298. #define TEST_TIME_MILLISECONDS 900
  299. #endif
  300.  
  301. template<unsigned int size>
  302. struct payload {
  303. static unsigned int copycount;
  304. 	int data[size/4];
  305. 	payload() {data[0]=rand()*RAND_MAX+rand();}
  306. #ifdef _DEBUG
  307. 	payload(const payload& r) {
  308. 		memcpy(data, r.data, sizeof(data)); 
  309. 		++copycount;
  310. 	}
  311. 	payload& operator=(const payload& r) {
  312. 		memcpy(data, r.data, sizeof(data)); 
  313. 		++copycount;
  314. 		return *this;
  315. 	}
  316. #endif
  317. 	bool operator==(const payload& rhs) const {return data[0]==rhs.data[0];}
  318. 	bool operator<(const payload& rhs) const {return data[0]<rhs.data[0];}
  319. };
  320.  
  321. template<unsigned int size>
  322. unsigned int payload<size>::copycount;
  323.  
  324. template<class payload, class container>
  325. void test_internal(const std::vector<std::pair<payload, payload>>& data, const char* classname, const char* payloadname) {
  326. 	clock_t beg,end,elapsed,freq;
  327. 	unsigned int count=0;
  328. 	bool timed=false;
  329. 	freq = CLOCKS_PER_SEC;
  330.  
  331. 	std::vector<std::pair<payload, payload>> shuffled(data.begin(), data.end());
  332. 	std::random_shuffle(shuffled.begin(), shuffled.end());
  333. 	std::vector<std::pair<payload, payload>> sorted(data.begin(), data.end());
  334. 	std::sort(sorted.begin(), sorted.end());
  335.  
  336. 	std::cout << payloadname << ' ' << std::setw(4) << data.size() << ' ' << classname << ' ';
  337.  
  338. 	timed = false;
  339. 	elapsed = 0;
  340. 	count = 0;
  341.     do {
  342. 		beg = clock();
  343. 	    container a(data.begin(), data.end());
  344. 	    end = clock();
  345. 		//assert(data.size()==a.size()); //meh, duplicates
  346. 		elapsed += end-beg;
  347.    	    if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
  348. 			elapsed =0;
  349. 			count=0;
  350.             timed = true;
  351. 	    }
  352. 		++count;
  353. 	} while(elapsed<TEST_TIME_MILLISECONDS);
  354. 	std::cout << std::setw(9) << count << ' ';
  355.  
  356. 	timed = false;
  357. 	elapsed = 0;
  358. 	count = 0;
  359. 	{
  360. 	    container a(data.begin(), data.end());
  361. 		do {
  362. 			beg = clock();
  363. 			auto i=a.find(shuffled[count%data.size()].first);
  364. 			end = clock();
  365. 			assert(i != a.end());
  366. 			assert(i->second == shuffled[count%data.size()].second);
  367. 			elapsed += end-beg;
  368.    			if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
  369. 				elapsed =0;
  370. 				count=0;
  371. 				timed = true;
  372. 			}
  373. 			++count;
  374. 		} while(elapsed<TEST_TIME_MILLISECONDS);
  375. 	}
  376. 	std::cout << std::setw(9) << count << ' ';
  377.  
  378. 	timed = false;
  379. 	elapsed =0;
  380. 	count = 0;
  381. 	{
  382. 		do {
  383. 			container a(data.begin(), data.end());
  384. 			beg = clock();
  385. 			for(unsigned int i=0; i<shuffled.size(); ++i)
  386. 				a.erase(shuffled[i].first);
  387. 			end = clock();
  388. 			assert(a.size()==0);
  389. 			elapsed += end-beg;
  390.    			if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
  391. 				elapsed =0;
  392. 				count=0;
  393. 				timed = true;
  394. 			}
  395. 			++count;
  396. 		} while(elapsed<TEST_TIME_MILLISECONDS);
  397. 	}
  398. 	std::cout << std::setw(9) << count << '\n';
  399. }
  400.  
  401. template<class payload>
  402. void test(const std::vector<std::pair<payload, payload>> &data, const char* payload_name) {
  403. 	std::vector<std::pair<payload, payload>> use(data.begin(), data.begin()+8);
  404. 	for( ; ; ) {
  405. 		test_internal<payload, std::map   <payload,payload>>(use, "std::map", payload_name);
  406. 		test_internal<payload, associative<payload,payload,std::less<payload>,std::vector<std::pair<payload,payload>>>>(use, "astv/vec", payload_name);
  407. 		if (use.size()<1024)
  408. 			use.insert(use.end(), data.begin()+use.size()*1ull, data.begin()+use.size()*2ull);
  409. 		else if (use.size() != data.size())
  410. 			use.insert(use.end(), data.begin()+use.size(), data.end());
  411. 		else break;
  412. 	}
  413. }
  414.  
  415. //template associative<payload<  4>,payload<  4>,std::less<payload<  4>>,std::list<std::pair<payload<  4>,payload<  4>>>>;
  416. //template associative<payload<  4>,payload<  4>,std::less<payload<  4>>,std::vector<std::pair<payload<  4>,payload<  4>>>>;
  417. //template associative<payload<  4>,payload<  4>,std::less<payload<  4>>,std::deque<std::pair<payload<  4>,payload<  4>>>>;
  418.  
  419. int main() {
  420. 	std::vector<std::pair<std::string,std::string>> dynamic_data;
  421. 	dynamic_data.reserve(2000);
  422. 	{
  423. 		std::ifstream i("F:/Code/Contests/About53/2000words.txt");
  424. 		std::string line;
  425. 		for(;dynamic_data.size()<2000 && i>>line;)
  426. 			dynamic_data.push_back(std::make_pair(line, line));
  427. 		std::random_shuffle(dynamic_data.begin(), dynamic_data.end());
  428. 	}
  429. 	std::cout << "bigger counts are best       inserts   lookups    erases\n";
  430. #ifndef _DEBUG
  431. 	//test(dynamic_data,                                            "std::string ");
  432. #endif
  433. 	test(std::vector<std::pair<payload<  4>,payload<  4>>>(2000), "payload<  4>");
  434. #ifndef _DEBUG
  435. 	test(std::vector<std::pair<payload<  8>,payload<  8>>>(2000), "payload<  8>");
  436. 	test(std::vector<std::pair<payload< 16>,payload< 16>>>(2000), "payload< 16>");
  437. 	test(std::vector<std::pair<payload< 32>,payload< 32>>>(2000), "payload< 32>");
  438. 	test(std::vector<std::pair<payload< 64>,payload< 64>>>(2000), "payload< 64>");
  439. 	test(std::vector<std::pair<payload<128>,payload<128>>>(2000), "payload<128>");
  440. #endif
  441.  
  442. 	return 0;
  443. }
  444.  
Success #stdin #stdout 11.23s 3588KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
bigger counts are best       inserts   lookups    erases
payload<  4>    8 std::map      8494     17249     47028
payload<  4>    8 astv/vec     42582     19462     14806
payload<  4>   16 std::map     15568     10325      9060
payload<  4>   16 astv/vec     24749     21012     24487
payload<  4>   32 std::map      9917     38030     16270
payload<  4>   32 astv/vec     13417     22852     17366
payload<  4>   64 std::map      5754     18885      2808
payload<  4>   64 astv/vec     15152     19403      2064
payload<  4>  128 std::map      3695     20100      2146
payload<  4>  128 astv/vec      2395     35118       674
payload<  4>  256 std::map      2221     18474      1959
payload<  4>  256 astv/vec      4709      1495       193
payload<  4>  512 std::map      1312     17628       484
payload<  4>  512 astv/vec      4137     16362        54
payload<  4> 1024 std::map       561     14299       251
payload<  4> 1024 astv/vec      2288     34326        14
payload<  4> 2000 std::map       282     15347       381
payload<  4> 2000 astv/vec      1182     11001         5
payload<  8>    8 std::map      4374     18729      3929
payload<  8>    8 astv/vec     30304     33950     42982
payload<  8>   16 std::map     10339     99773     12961
payload<  8>   16 astv/vec     17259     55153      8403
payload<  8>   32 std::map      6216     33145      5230
payload<  8>   32 astv/vec     23706      1005      5415
payload<  8>   64 std::map      3760     31764     21009
payload<  8>   64 astv/vec      6305     18032      1250
payload<  8>  128 std::map      3863     55696      2514
payload<  8>  128 astv/vec      4678     36670       452
payload<  8>  256 std::map      1948     31258       542
payload<  8>  256 astv/vec      2765     14004       118
payload<  8>  512 std::map      1005      5053      1132
payload<  8>  512 astv/vec      2942     59692        32
payload<  8> 1024 std::map       524     16027       872
payload<  8> 1024 astv/vec      1609     14941         9
payload<  8> 2000 std::map       265     56575       159
payload<  8> 2000 astv/vec       977     28793         3
payload< 16>    8 std::map     27065     17193      7565
payload< 16>    8 astv/vec     37219     49197     15760
payload< 16>   16 std::map     16394     15111     13320
payload< 16>   16 astv/vec      2249     71921      9059
payload< 16>   32 std::map     11392     77381     11646
payload< 16>   32 astv/vec     21609     23815      3349
payload< 16>   64 std::map      5715     22497      4762
payload< 16>   64 astv/vec     12629     36212      2144
payload< 16>  128 std::map      3080     50989      6386
payload< 16>  128 astv/vec      3353     14692       285
payload< 16>  256 std::map      1753     20602      1154
payload< 16>  256 astv/vec      3738     16916        78
payload< 16>  512 std::map       942      4329      1114
payload< 16>  512 astv/vec      2274     18988        22
payload< 16> 1024 std::map       505     16270       557
payload< 16> 1024 astv/vec       851     33415         6
payload< 16> 2000 std::map       254      7113       153
payload< 16> 2000 astv/vec       631     72038         2
payload< 32>    8 std::map      3971      4715     34892
payload< 32>    8 astv/vec     13915     54379      7940
payload< 32>   16 std::map     12542     15863     18958
payload< 32>   16 astv/vec     19548     16818     17402
payload< 32>   32 std::map      7549     23324      5961
payload< 32>   32 astv/vec     15453     13121      3819
payload< 32>   64 std::map      5609     24209     12724
payload< 32>   64 astv/vec     23553     19046       595
payload< 32>  128 std::map      2859     53808     11252
payload< 32>  128 astv/vec      3451     91899       159
payload< 32>  256 std::map      1661     16499      1970
payload< 32>  256 astv/vec      1914     13582        40
payload< 32>  512 std::map       764     21648       483
payload< 32>  512 astv/vec      1016     20307        14
payload< 32> 1024 std::map       427     15562       269
payload< 32> 1024 astv/vec       458     14862         3
payload< 32> 2000 std::map       200     19842       498
payload< 32> 2000 astv/vec       330     16860         2
payload< 64>    8 std::map     16715     89995     13932
payload< 64>    8 astv/vec     17797     17877     20986
payload< 64>   16 std::map     22304     38568     24309
payload< 64>   16 astv/vec      2462     42727      8591
payload< 64>   32 std::map      5090     16806      3448
payload< 64>   32 astv/vec      6037     25141      1028
payload< 64>   64 std::map      4494     26550     14032
payload< 64>   64 astv/vec      3315     18400       592
payload< 64>  128 std::map      2035     17014      4756
payload< 64>  128 astv/vec      2158     55235        85
payload< 64>  256 std::map      1186     57490       806
payload< 64>  256 astv/vec      2331     17922        21
payload< 64>  512 std::map       566     14786      1596
payload< 64>  512 astv/vec       430     21539         6
payload< 64> 1024 std::map       300     74636      1183
payload< 64> 1024 astv/vec       212     87165         2
payload< 64> 2000 std::map       157     15873       102
payload< 64> 2000 astv/vec       138     14635         2
payload<128>    8 std::map     21277     38666     29917
payload<128>    8 astv/vec     13444     39191      3669
payload<128>   16 std::map     18789     10309      5385
payload<128>   16 astv/vec      7639     55992      2875
payload<128>   32 std::map      3955     31880      6741
payload<128>   32 astv/vec      2232     19284       380
payload<128>   64 std::map      1967     56004      3801
payload<128>   64 astv/vec       430     18027       108
payload<128>  128 std::map      1350     16793      3908
payload<128>  128 astv/vec      1066     19316        27
payload<128>  256 std::map       499     91383       455
payload<128>  256 astv/vec       503     13186         8
payload<128>  512 std::map       287     47965       476
payload<128>  512 astv/vec       257     58059         2
payload<128> 1024 std::map       153     21026       250
payload<128> 1024 astv/vec       126     25431         2
payload<128> 2000 std::map        79     14709       192
payload<128> 2000 astv/vec        63      8600         2
https://ideone.com/MQr0Z
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!