fork(1) download
copy 
  1. #include <cassert>
  2. #include <iostream>
  3. #include <type_traits>
  4. #include <utility>
  5. #include <chrono>
  6. #include <set>
  7. #include <map>
  8. #include <vector>
  9. #include <iterator>
  10.  
  11. #define LOOPS 100
  12. #define MAXEL 100000
  13.  
  14. template<typename Type>
  15. class Range{
  16. 	public:
  17. 	typedef std::pair<Type,Type> Pair;
  18. 	typedef std::set<Type> Set;
  19.  
  20. 	Range(const Pair & pair){
  21. 		m_ptr = static_cast<void * >( new Pair(pair) );
  22. 		m_which = 0;
  23. 	}
  24. 	Range(Pair && pair){
  25. 		m_ptr = static_cast<void * >( new Pair( std::move(pair) ) );
  26. 		m_which = 0;
  27. 	}
  28.  
  29.  
  30. 	Range(const Set & set){
  31. 		m_which = 1;
  32. 		m_ptr = static_cast<void * >( new Set(set) );
  33. 	}
  34. 	Range(Set && set){
  35. 		m_which = 1;
  36. 		m_ptr = static_cast<void * >( new Set( std::move(set) ) );
  37. 	}
  38.  
  39.  
  40. 	Range(const Range & r){
  41. 		*this = r;
  42. 	}
  43.  
  44. 	// Move Constructor
  45. 	Range(Range && r){
  46. 		*this = std::move(r);
  47. 	}
  48.  
  49. 	// Move Assigment
  50. 	Range & operator=(Range && r){
  51. 		assert(r.m_ptr);
  52. 		if(m_ptr != r.m_ptr && this != &r ){ // Prevent self-assignment
  53. 			~Range(); // delete resources
  54. 			m_ptr  =  std::move(r.m_ptr);
  55. 			m_which = std::move(r.m_which);
  56. 			r.m_ptr = nullptr;
  57. 			r.m_which = 0;
  58. 		}
  59. 	}
  60.  
  61. 	// Assigment
  62. 	Range & operator=(Range & r){
  63. 		if(m_ptr != r.m_ptr && this != &r ){ // Prevent self-assignment
  64. 			if(r.m_which == 0){
  65. 				if(m_which == 0 && m_ptr){
  66. 					*static_cast<Pair*>(m_ptr) = *static_cast<Pair*>(r.m_ptr); // Copy
  67. 				}
  68. 				m_ptr = static_cast<void * >( new Pair(*static_cast<Pair*>(r.m_ptr))); // Make new and Copy
  69. 			}else if(r.m_which==1){
  70. 				if(m_which == 1 && m_ptr){
  71. 					*static_cast<Set*>(m_ptr) = *static_cast<Set*>(r.m_ptr); // Copy
  72. 				}
  73. 				m_ptr = static_cast<void * >( new Set(*static_cast<Set*>(r.m_ptr)));  // Make new and Copy
  74. 			}
  75. 			m_which = r.m_which;
  76. 		}
  77. 	}
  78.  
  79.  
  80. 	~Range(){
  81. 		if(m_ptr){
  82. 			if(m_which == 0){
  83. 				auto p = static_cast<Pair * >(m_ptr); delete p;
  84. 			}else if(m_which==1){
  85. 				auto p = static_cast<Set * >(m_ptr); delete p;
  86. 			}
  87. 			m_which = 0;
  88. 		}
  89. 	}
  90.  
  91. 	class iterator {
  92.     public:
  93.         iterator():m_r(nullptr),m_cur(0){};
  94.  
  95.         iterator(Range * r, bool atEnd = false):m_r(r) {
  96.         	if(!m_r->m_ptr){
  97. 				m_cur=0;
  98. 				return;
  99.         	}
  100.             if(m_r->m_which == 0){
  101. 				auto p = static_cast<Pair * >(m_r->m_ptr);
  102. 				if(atEnd){
  103. 					m_cur = p->second;
  104. 				}else{
  105. 					m_cur = p->first;
  106. 				}
  107. 			}else{
  108. 				auto p = static_cast<Set * >(m_r->m_ptr);
  109. 				if(atEnd){
  110. 					m_it = p->end();
  111. 				}else{
  112. 					m_it = p->begin();
  113. 				}
  114. 			}
  115.         };
  116.  
  117.         //Delete assignment operator
  118.         iterator & operator=(const iterator&) = delete;
  119.         iterator & operator=(iterator&) = delete;
  120.  
  121.         ~iterator() {
  122.         }
  123.  
  124.         iterator( const iterator & it ): m_r(it.m_r), m_cur(it.m_cur) {
  125.         }
  126.  
  127.         /** pre-increment ++it
  128.         * Allow to iterate over the end of the sequence
  129.         */
  130.         iterator & operator++() {
  131. 	            if(m_r->m_which == 0){
  132. 					++m_cur;
  133. 				}else {
  134. 					++m_it;
  135. 				}
  136.             return *this;
  137.         }
  138.         /** post-increment it++
  139.         *
  140.         */
  141.         iterator operator++(int) {
  142.             iterator it(*this);
  143.             operator++();
  144.             return it;
  145.         }
  146.  
  147.  
  148.         bool operator==(const iterator &rhs) {
  149.             if(m_r->m_which == 0){
  150. 				return m_cur == rhs.m_cur; // Two iterators for differente ranges, might compare equal!
  151. 			}else {
  152. 				return m_it == rhs.m_it;
  153. 			}
  154.  
  155.         }
  156.  
  157.         // Return false if the same!
  158.         bool operator!=(const iterator &rhs) {
  159.             return !(*this==rhs);
  160.         }
  161.  
  162.         Type operator*() {
  163.             if(m_r->m_which == 0){
  164. 				return m_cur ;
  165. 			}else {
  166. 				return *m_it;
  167. 			}
  168.         }
  169.     private:
  170.         Range * m_r;
  171.         typename Set::iterator m_it;
  172.         Type m_cur;
  173.     };
  174.  
  175. 	iterator begin(){
  176. 		return iterator(this);
  177. 	}
  178.  
  179. 	iterator end(){
  180. 		return iterator(this,true);
  181. 	}
  182.  
  183. 	private:
  184. 	unsigned int m_which = 0;
  185. 	void * m_ptr = nullptr;
  186. };
  187.  
  188.  
  189. #define INIT_TIMER auto start = std::chrono::high_resolution_clock::now();
  190. #define START_TIMER  start = std::chrono::high_resolution_clock::now();
  191. #define STOP_TIMER(name)  \
  192.     double count = std::chrono::duration<double,std::milli>(std::chrono::high_resolution_clock::now()-start ).count(); \
  193.     std::cout << "RUNTIME of " << name << ": " << count << " ms " << std::endl;
  194.  
  195. int main(){
  196.  
  197.     std::cout << "Speed Test ============================" << std::endl;
  198.     typedef unsigned int Type;
  199.     std::set<Type> s;
  200.     unsigned int max = 100000;
  201.  
  202.     // Filling vector and set
  203.     std::vector<Type> vec(max);
  204.     for(int j = 0; j< vec.size(); j++) {
  205.         vec[j] = j*j;
  206.     }
  207.     while(s.size()<max){
  208.         s.insert(rand());
  209.     }
  210.     // Making Pair
  211.     std::pair<Type, Type> a(0,max);
  212.  
  213.  
  214.     int loops = LOOPS;
  215.     int n = 0;
  216. 	{
  217.         Range<Type> range(a);
  218.         INIT_TIMER
  219.         START_TIMER
  220.         auto itEnd = range.end();
  221.         for(int i=1; i<loops; i++) {
  222.             for(auto it=range.begin(); it != itEnd; ++it) {
  223.                 n +=  *it*i;
  224.                 //std::cout << *it << std::endl;
  225.             }
  226.         }
  227.         STOP_TIMER("Range: [Pair] ")
  228. 	}
  229. 	{
  230.          Range<Type> range(s);
  231.         INIT_TIMER
  232.         START_TIMER
  233.         auto itEnd = range.end();
  234.         for(int i=1; i<loops; i++) {
  235.             for(auto it=range.begin(); it != itEnd; ++it) {
  236.                 n +=  *it*i;
  237.                 //std::cout << *it << std::endl;
  238.             }
  239.         }
  240.         STOP_TIMER("Range: [Set]")
  241. 	}
  242.  
  243.  
  244.  
  245. 	{
  246.  
  247.         INIT_TIMER
  248.         START_TIMER
  249.         auto s2 = s;
  250.         auto itEnd = s2.end();
  251.         for(int i=1; i<loops; i++) {
  252.             for(auto it=s2.begin(); it != itEnd; ++it) {
  253.                 n +=  *it*i;
  254.                 //std::cout << *it << std::endl;
  255.             }
  256.         }
  257.         STOP_TIMER("std::set")
  258. 	}
  259.  
  260. 	{
  261.         INIT_TIMER
  262.         START_TIMER
  263. 		for(unsigned int i=1; i<loops; ++i) {
  264. 	        for(unsigned int j = 0; j<max; ++j){
  265. 				n+=i*j;
  266. 			}
  267. 		}
  268.         STOP_TIMER("Range: Normal For Loop")
  269. 	}
  270.  
  271.  
  272. }
  273.  
Success #stdin #stdout 0.55s 8096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Speed Test ============================
RUNTIME of Range: [Pair] : 8.68545 ms 
RUNTIME of Range: [Set]: 277.4 ms 
RUNTIME of std::set: 199.237 ms 
RUNTIME of Range: Normal For Loop: 0.000174 ms
https://ideone.com/Mpv4eo
language:
C++14 (gcc 8.3)
created:
9 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!