fork download 
  1. #include <iostream>
  2.  
  3.  
  4. /* Node */
  5.  
  6. template <class Elem>
  7. struct Link
  8. {
  9. 	Link();
  10. 	Link (Link<Elem>* s, Link<Elem>* p, const Elem& v);
  11. 	Link (const Link<Elem>& src);
  12.  
  13. 	Link<Elem>& operator= (const Link<Elem>& src);
  14. 	bool operator== (const Link<Elem>& src);
  15. 	bool operator!= (const Link<Elem>& src);
  16.  
  17. 	void swap(Link<Elem>& src);
  18.  
  19. 	Link* succ;
  20. 	Link* prev;
  21. 	Elem val;
  22. };
  23.  
  24. //-----------------------------------------------------------------------------
  25.  
  26. template <class Elem>
  27. Link<Elem>::Link()
  28. 	: succ(nullptr), prev(nullptr), val(Elem())
  29. {
  30.  
  31. }
  32.  
  33. //-----------------------------------------------------------------------------
  34.  
  35. template <class Elem>
  36. Link<Elem>::Link (Link<Elem>* s, Link<Elem>* p, const Elem& v)
  37. 	: succ(s), prev(p), val(v)
  38. {
  39.  
  40. }
  41.  
  42. //-----------------------------------------------------------------------------
  43.  
  44. template <class Elem>
  45. Link<Elem>::Link (const Link<Elem>& src)
  46. 	: succ(src.succ), prev(src.prev), val(src.val)
  47. {
  48.  
  49. }
  50.  
  51. //-----------------------------------------------------------------------------
  52.  
  53. template <class Elem>
  54. Link<Elem>& Link<Elem>::operator= (const Link<Elem>& src)
  55. {
  56. 	Link<Elem> temp(src);
  57. 	swap(*this, temp);
  58. 	return *this;
  59. }
  60.  
  61. //-----------------------------------------------------------------------------
  62.  
  63. template <class Elem>
  64. bool Link<Elem>::operator== (const Link<Elem>& src)
  65. {
  66. 	return succ = src.succ && prev = src.prev;
  67. }
  68.  
  69. //-----------------------------------------------------------------------------
  70.  
  71. template <class Elem>
  72. bool Link<Elem>::operator!= (const Link<Elem>& src)
  73. {
  74. 	return !(*this == src);
  75. }
  76.  
  77. //-----------------------------------------------------------------------------
  78.  
  79. template <class Elem>
  80. void Link<Elem>::swap(Link<Elem>& src)
  81. {
  82. 	std::swap(prev, src.prev);
  83. 	std::swap(succ, src.succ);
  84. 	std::swap(val, src.val);
  85. }
  86.  
  87. //-----------------------------------------------------------------------------
  88.  
  89. template<class Elem>
  90. void swap(Link<Elem>& lhs, Link<Elem>& rhs)
  91. {
  92. 	lhs.swap(rhs);
  93. }
  94.  
  95. /* Doubly Linked List */
  96. //----------------------------------------------------------------------------
  97.  
  98. template <class Elem>
  99. class List
  100. {
  101. public:
  102. 	class iterator;
  103.  
  104. 	List();
  105.  
  106. 	iterator begin() { return iterator(first, first, last); }
  107. 	iterator end() { return iterator(last, first, last); }
  108.  
  109. 	void push_front(const Elem& v);
  110.  
  111. 	Elem& front();
  112.  
  113. 	size_t size(); 
  114. 	void print();
  115.  
  116. private:
  117. 	Link<Elem> *first;
  118. 	Link<Elem> *last;
  119. };
  120.  
  121. //-----------------------------------------------------------------------------
  122.  
  123. template<class Elem>
  124. List<Elem>::List()
  125. 	: first(new Link<Elem>()), last(first)
  126. {
  127.  
  128. }
  129.  
  130. //-----------------------------------------------------------------------------
  131.  
  132. template<class Elem>
  133. void List<Elem>::push_front(const Elem& v)
  134. { 
  135. 	first = new Link<Elem>(first, nullptr, v); 
  136. }
  137.  
  138. //-----------------------------------------------------------------------------
  139.  
  140. template<class Elem>
  141. Elem& List<Elem>::front()
  142. {
  143. 	return first->val; 
  144. }
  145.  
  146. //-----------------------------------------------------------------------------
  147.  
  148. template<class Elem>
  149. size_t List<Elem>::size() 
  150. {
  151. 	size_t count = 0;
  152. 	for (iterator p = begin(); p != end(); ++p)
  153. 	{
  154. 		++count;	 
  155. 	}
  156. 	return count;
  157. }
  158.  
  159. //-----------------------------------------------------------------------------
  160.  
  161. template<class Elem>
  162. void List<Elem>::print()
  163. {
  164. 	for (iterator p = begin(); p != end(); ++p)
  165. 	{
  166. 		std::cout << *p <<' ';	 
  167. 	}
  168. }
  169.  
  170. //-----------------------------------------------------------------------------
  171.  
  172. /* a range-checked bidirectional iterator */
  173. template <class Elem>
  174. class List<Elem>::iterator
  175. {
  176. public:
  177. 	iterator();											// default constructor
  178. 	iterator(Link<Elem>* c, Link<Elem>* b, Link<Elem>* e);					
  179. 	iterator(const iterator& src);						// copy constructor
  180. 	iterator operator= (const iterator& src);			// copy assignment 
  181.  
  182. 	iterator& operator++();								// incrementations
  183. 	iterator operator++(int);							// postfix
  184. 	iterator& operator--();								// decrementations
  185. 	iterator operator--(int);							// postfix
  186.  
  187. 	Elem& operator*();									// dereferenceable lvalue
  188. 	const Elem& operator*() const;						// dereferenceable rvalue
  189.  
  190. 	bool operator== (const iterator& b) const;			// equality comparisons
  191. 	bool operator!= (const iterator& b) const;
  192.  
  193. 	void swap(iterator& src);
  194.  
  195. private:
  196. 	Link<Elem>* curr;
  197. 	Link<Elem>* begin;
  198. 	Link<Elem>* end;
  199. };
  200.  
  201. //-----------------------------------------------------------------------------
  202.  
  203. template<class Elem>
  204. List<Elem>::iterator::iterator()
  205. 	: curr(nullptr), begin(nullptr), end(nullptr)
  206. {
  207.  
  208. }
  209.  
  210. //-----------------------------------------------------------------------------
  211.  
  212. template<class Elem>
  213. List<Elem>::iterator::iterator(Link<Elem>* p, Link<Elem>* b, Link<Elem>* e)
  214. 	: curr(p), begin(b), end(e)
  215. {
  216.  
  217. }
  218.  
  219. //-----------------------------------------------------------------------------
  220.  
  221. template<class Elem>
  222. List<Elem>::iterator::iterator(const iterator& src)
  223. 	: curr(src.curr), begin(src.begin), end(src.end)
  224. {
  225.  
  226. }
  227.  
  228. //-----------------------------------------------------------------------------
  229.  
  230. template<class Elem>
  231. typename List<Elem>::iterator List<Elem>::iterator::operator= (const iterator& src)
  232. {
  233. 	iterator temp(src);
  234. 	this->swap(temp);
  235. 	return *this;
  236. }
  237.  
  238. //-----------------------------------------------------------------------------
  239.  
  240. template<class Elem>
  241. typename List<Elem>::iterator& List<Elem>::iterator::operator++()
  242. {
  243. 	if (curr == end)
  244. 	{
  245. 		throw std::out_of_range("List<Elem>::iterator::operator++(): out of range!\n");
  246. 	}
  247.  
  248. 	curr = curr->succ;
  249.  
  250. 	return *this; 
  251. }
  252.  
  253. //-----------------------------------------------------------------------------
  254.  
  255. template<class Elem>
  256. typename List<Elem>::iterator List<Elem>::iterator::operator++(int)
  257. {
  258. 	if (curr == end)
  259. 	{
  260. 		throw std::out_of_range("List<Elem>::iterator::operator++(): out of range!\n");
  261. 	}
  262.  
  263. 	Link<Elem>* old = curr;
  264. 	curr = curr->succ;
  265. 	return old; 
  266. }
  267.  
  268. //-----------------------------------------------------------------------------
  269.  
  270. template<class Elem>
  271. typename List<Elem>::iterator& List<Elem>::iterator::operator--()
  272. { 
  273. 	if (curr == begin)
  274. 	{
  275. 		throw std::out_of_range("List<Elem>::iterator::operator--(): out of range!\n");
  276. 	}
  277.  
  278. 	curr = curr->prev;
  279.  
  280. 	return *this; 
  281. }
  282.  
  283. //-----------------------------------------------------------------------------
  284.  
  285. template<class Elem>
  286. typename List<Elem>::iterator List<Elem>::iterator::operator--(int)
  287. { 
  288. 	if (curr == begin)
  289. 	{
  290. 		throw std::out_of_range("List<Elem>::iterator::operator--(): out of range!\n");
  291. 	}
  292.  
  293. 	iterator old(*this);
  294. 	curr = curr->prev;	
  295. 	return old; 
  296. }
  297.  
  298. //-----------------------------------------------------------------------------
  299.  
  300. template<class Elem>
  301. Elem& List<Elem>::iterator::operator*() 
  302. { 
  303. 	return curr->val; 
  304. }	
  305.  
  306. //-----------------------------------------------------------------------------
  307.  
  308. template<class Elem>
  309. const Elem& List<Elem>::iterator::operator*() const
  310. { 
  311. 	return curr->val;
  312. }
  313.  
  314. //-----------------------------------------------------------------------------
  315.  
  316. template<class Elem>
  317. bool List<Elem>::iterator::operator== (const iterator& b) const
  318. { 
  319. 	return curr == b.curr; 
  320. } 
  321.  
  322. //-----------------------------------------------------------------------------
  323.  
  324. template<class Elem>
  325. bool List<Elem>::iterator::operator!= (const iterator& b) const
  326. { 
  327. 	return curr != b.curr; 
  328. }
  329.  
  330. //-----------------------------------------------------------------------------
  331.  
  332. template<class Elem>
  333. void List<Elem>::iterator::swap(iterator& src)
  334. {
  335. 	std::swap(curr, src.curr); 
  336. 	std::swap(begin, src.begin);
  337. 	std::swap(end, src.end);
  338. }
  339.  
  340. //-----------------------------------------------------------------------------
  341.  
  342. template<class Elem>
  343. void swap(typename List<Elem>::iterator& lhs, typename List<Elem>::iterator& rhs)
  344. {
  345. 	lhs.swap(rhs);
  346. }
  347.  
  348. /* simple test for iterator */ 
  349.  
  350. int main() 
  351. {
  352. 	List<int> l;
  353. 		l.push_front(1);
  354. 		l.push_front(2);
  355. 		l.push_front(3);
  356. 		l.push_front(4);
  357. 		l.push_front(5);
  358.  
  359. 		// defualt constructor, copy assignment
  360. 		List<int>::iterator p = l.begin();
  361.  
  362. 		// write dereferencing 
  363. 		*p = 100;
  364.  
  365. 		// incrementation, read dereferencing
  366. 		List<int>::iterator i;
  367. 		for (i = l.begin(); i != l.end(); ++i)
  368. 		{
  369. 			std::cout << *i <<' ';
  370. 		}
  371.  
  372. 		if (i == l.end() && i != l.begin())
  373. 		{
  374. 			std::cout <<"\ncomparison correct!\n";
  375. 		}
  376.  
  377. 		// postfix and prefix decrementation; maintain dereferenceability
  378. 	    /*
  379. 		List<int>::iterator ii = l.end();
  380. 			ii--;
  381. 		for (; ii != l.begin(); ii--)
  382. 		{
  383. 			std::cout << *ii <<' ';
  384. 		} 
  385. 		*/
  386. 	return 0;
  387. }
  388.  
  389.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin 
Standard input is empty
stdout 
100 4 3 2 1 
comparison correct!
https://ideone.com/hX4Bfe
language:
C++ (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!