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