fork download
copy 
  1. #include <iostream>
  2.  
  3. template <typename KEY, typename VALUE>
  4. class SkipListNode
  5. {
  6. public:
  7.     typedef SkipListNode<KEY, VALUE> NodeType;
  8.  
  9.     SkipListNode()
  10.     : right(nullptr)
  11.     , down(nullptr)
  12.     {}
  13.  
  14.     NodeType* right;
  15.     NodeType* down;
  16.     KEY       first;
  17.     VALUE     second;
  18. };
  19.  
  20. template <typename KEY, typename VALUE>
  21. class SkipList
  22. {
  23. private:
  24.     typedef SkipListNode<KEY, VALUE> NodeType;
  25.  
  26. public:
  27.     typedef const NodeType* const_iterator;
  28.     typedef KEY             Key;
  29.     typedef VALUE           Value;
  30.  
  31.     SkipList()
  32.     : d_topLeft(nullptr)
  33.     , d_bottomLeft(nullptr)
  34.     , d_bottomRight(nullptr)
  35.     {}
  36.  
  37.     const_iterator begin() const { return d_bottomLeft; }
  38.     const_iterator end()   const { return d_bottomRight; }
  39.  
  40.     void insert(const Key& key, const Value& value);
  41.  
  42. private:
  43.     NodeType* d_topLeft;
  44.     NodeType* d_bottomLeft;
  45.     NodeType* d_bottomRight;
  46. };
  47.  
  48. template <typename KEY, typename VALUE>
  49. void SkipList<KEY, VALUE>::insert(const KEY& key, const VALUE& value)
  50. {
  51. 	NodeType* node = new NodeType();
  52. 	node->first = key;
  53. 	node->second = value;
  54.  
  55. 	if (!d_topLeft) {
  56. 		d_topLeft = node;
  57. 	}
  58. }
  59.  
  60. template <typename List>
  61. void printList(const List& list)
  62. {
  63. 	for (typename List::const_iterator it = list.begin();
  64. 	     it != list.end();
  65. 	     ++it) {
  66. 		std::cout << "[ " << it->first << ", " << it->second << " ] ";
  67. 	}
  68.  
  69. 	std::cout << "\n";
  70. }
  71.  
  72. void insertAndIterate()
  73. {
  74. 	SkipList<int, int> list;
  75. 	list.insert(2, 5);
  76. 	printList(list);
  77. }
  78.  
  79. int main() {
  80. 	insertAndIterate();
  81.  
  82. 	return 0;
  83. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/cteuwa
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
42 days 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!