fork download 
  1. // basic setup for a useable doubly linked list.
  2. //
  3. // some of this may seem like a pain initially, but some of the decisions
  4. // made here can make things easier down the road. e.g.:
  5. //
  6. // decoupling linked list data and user data.
  7. // defining iterators, especially one capable of interacting with the STL.
  8. // using an object rather than a pointer for the head node.
  9. // using a circular list rather than terminating with NULL.
  10. //
  11. // this omits a lot, but should be a fairly decent base to build on.
  12.  
  13. #include <algorithm>
  14. #include <iterator>
  15.  
  16. // ListNodeBase
  17. // basic linked list data and operations.
  18. struct ListNodeBase
  19. {
  20. 	ListNodeBase* next;
  21. 	ListNodeBase* prev;
  22.  
  23. 	// setup as circular by default.
  24. 	ListNodeBase()
  25. 		: next(this), prev(this) {}
  26. 	void reset()
  27. 	{ next = prev = this; }
  28.  
  29. 	static void link(ListNodeBase* position, ListNodeBase* x);
  30. 	static ListNodeBase* unlink(ListNodeBase* position);
  31. 	static void swap(ListNodeBase* a, ListNodeBase* b);
  32. };
  33.  
  34. void ListNodeBase::link(ListNodeBase* position, ListNodeBase* x)
  35. {
  36. 	x->next = position;
  37. 	x->prev = position->prev;
  38. 	position->prev->next = x;
  39. 	position->prev = x;
  40. }
  41.  
  42. ListNodeBase* ListNodeBase::unlink(ListNodeBase* position)
  43. {
  44. 	position->next->prev = position->prev;
  45. 	position->prev->next = position->next;
  46. 	return position->next;
  47. }
  48.  
  49. void ListNodeBase::swap(ListNodeBase* a, ListNodeBase* b)
  50. {
  51. 	ListNodeBase* anext = a->next;
  52. 	ListNodeBase* aprev = a->prev;
  53. 	ListNodeBase* bnext = b->next;
  54. 	ListNodeBase* bprev = b->prev;
  55.  
  56. 	anext->prev = aprev->next = b;
  57. 	bnext->prev = bprev->next = a;
  58. 	std::iter_swap(a, b);
  59. }
  60.  
  61. // ListNode
  62. // append user data to link list node.
  63. template<typename Tp>
  64. struct ListNode : public ListNodeBase
  65. {
  66. 	Tp data;
  67. 	// @todo support parameter packs.
  68. 	ListNode(const Tp& x)
  69. 		: data(x) {}
  70. };
  71.  
  72. // ListIterator
  73. // user interface for linked list traversal and access.
  74. template<typename Tp>
  75. struct ListIterator
  76. {
  77. 	// set standard typedefs (enable use of STL functions).
  78. 	typedef std::bidirectional_iterator_tag iterator_category;
  79. 	typedef std::ptrdiff_t	difference_type;
  80. 	typedef Tp				value_type;
  81. 	typedef Tp*				pointer;
  82. 	typedef Tp&				reference;
  83.  
  84. 	ListIterator(ListNodeBase* initial = nullptr)
  85. 		: m_base(initial) {}
  86.  
  87. 	reference operator*()
  88. 	{ return base()->data; }
  89. 	pointer operator->()
  90. 	{ return std::addressof(operator*()); }
  91.  
  92. 	ListIterator& operator++()
  93. 	{ m_base = m_base->next; return *this; }
  94. 	ListIterator& operator--()
  95. 	{ m_base = m_base->prev; return *this; }
  96.  
  97. 	ListIterator operator++(int)
  98. 	{ ListIterator temp = *this; ++*this; return temp; }
  99. 	ListIterator operator--(int)
  100. 	{ ListIterator temp = *this; --*this; return temp; }
  101.  
  102. 	bool operator==(const ListIterator& other) const
  103. 	{ return m_base == other.m_base; }
  104. 	bool operator!=(const ListIterator& other) const
  105. 	{ return !(*this == other); }
  106.  
  107. 	// downcast to user type.
  108. 	ListNode<Tp>* base()
  109. 	{ return static_cast<ListNode<Tp>*>(m_base); }
  110. private:
  111. 	ListNodeBase* m_base;
  112. };
  113.  
  114. // ListIterator (non-member)
  115. // @note uncommon extension for bidirectional iterators.
  116. template<typename Tp>
  117. inline ListIterator<Tp> operator+(ListIterator<Tp> i,
  118. 		typename ListIterator<Tp>::difference_type c)
  119. {
  120. 	std::advance(i, c);
  121. 	return i;
  122. }
  123.  
  124. // List
  125. // @todo add more methods.
  126. template<typename Tp>
  127. struct List
  128. {
  129. 	// @todo fill in standard typedefs.
  130. 	typedef ListIterator<Tp> iterator;
  131. 	typedef Tp   value_type;
  132.  
  133. 	~List()
  134. 	{ clear(); }
  135.  
  136. 	List() = default;
  137. 	List(const List& other)
  138. 	{ std::copy(other.begin(), other.end(), std::back_inserter(*this)); }
  139.  
  140. 	List(List&& other)
  141. 	{ swap(other); }
  142. 	List& operator=(List other)
  143. 	{ swap(other); return *this; }
  144.  
  145. 	iterator begin()
  146. 	{ return iterator(m_head.next); }
  147. 	iterator end()
  148. 	{ return iterator(&m_head); }	
  149.  
  150. 	// @todo movable and emplace variations.
  151. 	void insert(iterator position, const Tp& x)
  152. 	{ ListNodeBase::link(position.base(), new ListNode<Tp>(x)); }
  153. 	void push_front(const Tp& x)
  154. 	{ insert(begin(), x); }
  155. 	void push_back(const Tp& x)
  156. 	{ insert(end(), x); }
  157.  
  158. 	// @todo build pop front/back from erase.	
  159. 	iterator erase(iterator position);
  160. 	iterator erase(iterator first, iterator last);
  161.  
  162. 	void clear()
  163. 	{ erase(begin(), end()); }
  164. 	void swap(List& other)
  165. 	{ ListNodeBase::swap(&m_head, &other.m_head); }
  166.  
  167. 	// size is O(n), but it's supposed to be O(1) since C++11.
  168. 	std::size_t size() const
  169. 	{ return static_cast<std::size_t>(std::distance(begin(), end())); }
  170. 	bool empty() const
  171. 	{ return begin() == end(); }
  172. private:
  173. 	// we can get away with this as long as we don't violate the
  174. 	// logical-constness. better - implement const_iterator type.
  175. 	iterator begin() const
  176. 	{ return iterator(const_cast<ListNodeBase*>(m_head.next)); }
  177. 	iterator end() const
  178. 	{ return iterator(const_cast<ListNodeBase*>(&m_head)); }
  179.  
  180. 	// this is POD type; list initialization cannot fail.
  181. 	ListNodeBase m_head;
  182. };
  183.  
  184. template<typename Tp>
  185. typename List<Tp>::iterator List<Tp>::erase(iterator position)
  186. {
  187. 	ListNode<Tp>* current = position.base();
  188. 	ListNodeBase* next = ListNodeBase::unlink(current);
  189. 	delete current;
  190. 	return iterator(next);
  191. }
  192.  
  193. template<typename Tp>
  194. typename List<Tp>::iterator List<Tp>::erase(iterator first, iterator last)
  195. {
  196. 	while ( first != last )
  197. 		first = erase(first);
  198. 	return first;
  199. }
  200.  
  201. // Testing
  202. #include <chrono>
  203. #include <iostream>
  204. #include <cassert>
  205.  
  206. int main(int argc, char* argv[])
  207. {
  208. 	int size; std::cin >> size;
  209. 	List<int> list, temp;
  210.  
  211. 	using clock = std::chrono::high_resolution_clock;
  212. 	clock::time_point start;
  213. 	std::chrono::duration<double> elapsed;
  214.  
  215. 	// insert.
  216. 	std::cout << "Test insert .. " << std::flush;
  217. 	start = clock::now();
  218. 	for ( int i = 0; i < size; i++ )
  219. 		list.push_back(i);
  220. 	elapsed = clock::now() - start;
  221. 	assert(list.size() == size);
  222. 	{
  223. 		int value = 0;
  224. 		for ( auto i = list.begin(); i != list.end(); i++, value++ )
  225. 			assert(*i == value);
  226. 	}
  227. 	std::cout << "Okay. Elapsed: " << elapsed.count() << std::endl;
  228.  
  229. 	// copy.
  230. 	std::cout << "Test copy .. " << std::flush;
  231. 	start = clock::now();
  232. 	temp = list;
  233. 	elapsed = clock::now() - start;
  234. 	assert(list.size() == size);
  235. 	assert(temp.size() == size);
  236. 	assert(std::equal(list.begin(), list.end(), temp.begin()));
  237. 	std::cout << "Okay. Elapsed: " << elapsed.count() << std::endl;
  238.  
  239. 	// clear/erase.
  240. 	std::cout << "Test erase .. " << std::flush;
  241. 	start = clock::now();
  242. 	list.clear();
  243. 	elapsed = clock::now() - start;
  244. 	assert(list.empty());
  245. 	assert(temp.size() == size);
  246. 	std::cout << "Okay. Elapsed: " << elapsed.count() << std::endl;
  247.  
  248. 	std::cout << "Test move .. " << std::flush;
  249. 	start = clock::now();
  250. 	list = std::move(temp);
  251. 	elapsed = clock::now() - start;
  252. 	assert(list.size() == size);
  253. 	assert(temp.empty());
  254. 	std::cout << "Okay. Elapsed: " << elapsed.count() << std::endl;
  255. 	list.clear();
  256.  
  257. 	// generate some output (?).
  258. 	size = 10;
  259. 	for ( int i = 0; i < size; i++ )
  260. 		list.push_back(i);
  261. 	auto mid = list.begin() + size/2;
  262. 	std::cout << "\n1st: ";
  263. 	for ( auto i = list.begin(); i != mid; ++i )
  264. 		std::cout << *i << ' ';
  265. 	std::cout << "\n2nd: ";
  266. 	for ( auto i = mid; i != list.end(); ++i )
  267. 		std::cout << *i << ' ';
  268. 	std::cout << "\nall: ";
  269. 	for ( auto v : list )
  270. 		std::cout << v << ' ';
  271. 	std::cout << "\nall rotated(" << size/2 << "): ";
  272. 	std::rotate(list.begin(), mid, list.end());
  273. 	for ( auto v : list )
  274. 		std::cout << v << ' ';
  275. 	std::cout << std::endl;
  276. 	return 0;
  277. }
Success #stdin #stdout 0.82s 315904KB
comments ()
stdin 
10000000
stdout 
Test insert .. Okay. Elapsed: 0.228882
Test copy .. Okay. Elapsed: 0.229033
Test erase .. Okay. Elapsed: 0.132944
Test move .. Okay. Elapsed: 4.05e-07

1st: 0 1 2 3 4 
2nd: 5 6 7 8 9 
all: 0 1 2 3 4 5 6 7 8 9 
all rotated(5): 5 6 7 8 9 0 1 2 3 4
https://ideone.com/a9Nsmj
language:
C++14 (gcc 8.3)
created:
8 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!