fork download
copy 
  1. /**
  2. *    Sean Vogel
  3. *	11 -28 -2012
  4. *	Just a linked list
  5. */
  6. #ifndef SV_LINK_LIST
  7. #define SV_LINK_LIST
  8. #ifndef NULL
  9. 	#define NULL 0
  10. #endif
  11. #include <limits>
  12.  
  13. namespace sv
  14. {
  15. 	template <class T>
  16. 	class list
  17. 	{
  18. 		class node
  19. 		{	
  20. 		public:
  21. 			node *prev,
  22. 				*next;
  23.  
  24. 			T data;
  25.  
  26. 			node() : prev(NULL), next(NULL), data(NULL){}
  27. 			node(const T& t) : prev(NULL), next(NULL), data(t){}
  28. 		};
  29.  
  30. 		node *_front,
  31. 			*_back;
  32. 		unsigned int _size;
  33.  
  34. 	public:
  35. 		class iterator
  36. 		{
  37. 			node* _node;
  38. 		public:
  39. 			iterator() : _node(NULL){}
  40. 			iterator(node* n) : _node(n){}
  41. 			iterator(const iterator& it) : _node(it._node){}
  42. 			T& operator*(){ if(_node)return _node->data; }
  43. 			T& operator->(){ if(_node)return _node->data; }
  44. 			iterator& operator++()
  45. 			{
  46. 				if(_node)
  47. 				{
  48. 					_node = _node->next;
  49. 				}
  50. 				return *this;
  51. 			}
  52. 			iterator operator++(int)
  53. 			{
  54. 				iterator it(*this);
  55. 				++(*this);
  56. 				return it;
  57. 			}
  58. 			iterator& operator--()
  59. 			{
  60. 				if(_node)
  61. 				{
  62. 					_node = _node->prev;
  63. 				}
  64. 				return *this;
  65. 			}
  66. 			iterator& operator--(int)
  67. 			{
  68. 				iterator it(*this);
  69. 				--(*this);
  70. 				return it;
  71. 			}
  72. 			bool operator!=(const iterator& it) const { return (this->_node != it._node); }
  73.  
  74. 			iterator& operator=(const iterator& it)
  75. 			{
  76. 				_node = it._node;
  77. 				return *this;
  78. 			}
  79. 		};
  80.  
  81. 		template <class U = iterator>
  82. 		class _reverse_iterator 
  83. 		{
  84. 			node* _node;
  85. 		public:
  86. 			_reverse_iterator() : _node(NULL){}
  87. 			_reverse_iterator(node* n) : _node(n){}
  88. 			_reverse_iterator(const _reverse_iterator& it) : _node(it._node){}
  89. 			T& operator*(){ if(_node)return _node->data; }
  90. 			T& operator->(){ if(_node)return _node->data; }
  91. 			_reverse_iterator& operator++()
  92. 			{
  93. 				if(_node)
  94. 				{
  95. 					_node = _node->prev;
  96. 				}
  97. 				return *this;
  98. 			}
  99. 			_reverse_iterator operator++(int)
  100. 			{
  101. 				iterator it(*this);
  102. 				--(*this);
  103. 				return it;
  104. 			}
  105. 			_reverse_iterator& operator--()
  106. 			{
  107. 				if(_node)
  108. 				{
  109. 					_node = _node->next;
  110. 				}
  111. 				return *this;
  112. 			}
  113. 			_reverse_iterator& operator--(int)
  114. 			{
  115. 				_reverse_iterator it(*this);
  116. 				--(*this);
  117. 				return it;
  118. 			}
  119. 			bool operator!=(const _reverse_iterator& it) const { return (this->_node != it._node); }
  120.  
  121. 			_reverse_iterator& operator=(const _reverse_iterator& it)
  122. 			{
  123. 				_node = it._node;
  124. 				return *this;
  125. 			}
  126. 		}; typedef _reverse_iterator<> reverse_iterator;
  127.  
  128. 		//constructors
  129. 		list() : _front(NULL), _back(NULL), _size(NULL){}
  130. 		list(unsigned int , const T& t = T()){}
  131. 		list(const list<T>&);
  132. 		template < class InputIterator >
  133.         list(InputIterator first, InputIterator last);
  134. 		~list();
  135.  
  136. 		//iterators
  137. 		iterator begin();
  138. 		iterator end();
  139. 		reverse_iterator rbegin();
  140. 		reverse_iterator rend();
  141.  
  142. 		//operators
  143. 		list<T>& operator=(const list<T>&);
  144.  
  145. 		//element access
  146. 		T& front();
  147. 		T& back();
  148.  
  149. 		//capacity
  150. 		bool empty() const;
  151. 		unsigned int size() const;
  152. 		unsigned int max_size() const;
  153. 		void resize(unsigned int, const T& t = T());
  154.  
  155. 		//modifiers
  156. 		void push_front(const T&);
  157. 		void pop_front();
  158. 		void push_back(const T&);
  159. 		void pop_back();
  160. 		//iterator insert(iterator pos, const T&);
  161. 		//void insert(iterator pos, unsigned int size, const T&);
  162. 		//void insert(iterator position, InputIterator first, InputIterator last);
  163. 		//iterator erase(iterator position);
  164. 		//iterator erase(iterator first, iterator last);
  165. 		//void swap(list<T>& lst);
  166. 		void clear();
  167. 		//void assign(size_type n, const T& u);
  168. 		//void assign(InputIterator first, InputIterator last);
  169.  
  170. 		//operations
  171. 		//void remove(const T& value);
  172. 		//template <class Predicate>
  173. 		//void remove_if(Predicate pred);
  174. 		//void sort(list<T>& lst);
  175. 		//void merge(list<T>& lst):
  176. 		//void splice(iterator position, list<T,Allocator>& x);
  177. 		//void splice(iterator position, list<T,Allocator>& x, iterator i);
  178. 		//void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
  179. 		//void unique();
  180. 		//template <class BinaryPredicate>
  181. 		//void unique(BinaryPredicate binary_pred);
  182. 		//void reverse();
  183. 	};
  184.  
  185. 	template <class T>
  186. 	typename list<T>::iterator list<T>::begin()
  187. 	{
  188. 		return iterator(_front);
  189. 	}
  190.  
  191. 	template <class T>
  192. 	typename list<T>::iterator list<T>::end()
  193. 	{
  194. 		return iterator(_back->next);
  195. 	}
  196.  
  197. 	template <class T>
  198. 	typename list<T>::reverse_iterator list<T>::rbegin()
  199. 	{
  200. 		return reverse_iterator(_back);
  201. 	}
  202.  
  203. 	template <class T>
  204. 	typename list<T>::reverse_iterator list<T>::rend()
  205. 	{
  206. 		return reverse_iterator(_front->prev);
  207. 	}
  208.  
  209. 	template <class T>
  210. 	list<T>::list(const list<T>& lst) : _front(NULL), _back(NULL), _size(NULL)
  211. 	{
  212. 		if(!lst.empty())
  213. 		{
  214. 			node* n = lst._front;			
  215. 			while(n)
  216. 			{
  217. 				push_back(n->data);
  218. 				n = n->next;						
  219. 			}
  220. 		}
  221. 	}
  222.  
  223. 	template <class T>
  224. 	list<T>& list<T>::operator=(const list<T>& lst)
  225. 	{
  226. 		if(this != &lst && !lst.empty())
  227. 		{
  228. 			clear();
  229.  
  230. 			node* n = lst._front;			
  231. 			while(n)
  232. 			{
  233. 				push_back(n->data);
  234. 				n = n->next;						
  235. 			}
  236. 		}
  237. 		return this;
  238. 	}
  239.  
  240. 	template <class T>
  241. 	list<T>::~list()
  242. 	{
  243. 		clear();
  244. 	}
  245.  
  246. 	template <class T>
  247. 	bool list<T>::empty()const {return !_front;}
  248.  
  249. 	template <class T>
  250. 	unsigned int list<T>::size()const{return _size;}
  251.  
  252. 	template <class T>
  253. 	unsigned int list<T>::max_size()const {return std::numeric_limits<T>::max();}
  254.  
  255. 	template <class T>
  256. 	void list<T>::resize(unsigned int sz, const T& t)
  257. 	{
  258. 		while(sz > _size)
  259. 		{
  260. 			push_back(t);
  261. 		}
  262. 	}
  263.  
  264. 	template <class T>
  265. 	T& list<T>::front()
  266. 	{
  267. 		if(_front)
  268. 			return _front->data;
  269. 	}
  270.  
  271. 	template <class T>
  272. 	T& list<T>::back()
  273. 	{
  274. 		if(_back)
  275. 			return _back->data;
  276. 	}
  277.  
  278. 	template <class T>
  279. 	void list<T>::push_front(const T& t)
  280. 	{			
  281. 		node* n = new node(t);
  282.  
  283. 		if(_front)
  284. 		{
  285. 			n->next = _front;
  286. 			_front->prev = n;
  287. 			_front = n;
  288. 		}
  289. 		else
  290. 		{
  291. 			_back = _front = n;
  292. 		}
  293. 		++_size;
  294. 	}
  295.  
  296. 	template <class T>
  297. 	void list<T>::pop_front()
  298. 	{
  299. 		if(front)
  300. 		{
  301. 			node* n = _front->next;
  302. 			delete _front;
  303. 			_front = n;
  304. 			--_size;
  305. 		}		
  306. 	}
  307.  
  308. 	template <class T>
  309. 	void list<T>::push_back(const T& t)
  310. 	{
  311. 		node* n = new node(t);
  312.  
  313. 		if(_back)
  314. 		{
  315. 			n->prev = _back;
  316. 			_back->next = n;
  317. 			_back = n;
  318. 		}
  319. 		else
  320. 		{
  321. 			_front = _back = n;			
  322. 		}
  323. 		++_size;
  324. 	}
  325.  
  326. 	template <class T>
  327. 	void list<T>::pop_back()
  328. 	{
  329. 		if(back)
  330. 		{
  331. 			node* n = _back->prev;
  332. 			delete _back;
  333. 			_back = n;
  334. 			--_size;
  335. 		}		
  336. 	}
  337.  
  338. 	template <class T>
  339. 	void list<T>::clear()
  340. 	{
  341. 		node* n;
  342. 		while(_front)
  343. 		{
  344. 			n = _front->next;
  345. 			delete _front;
  346. 			_front = n;
  347. 			--_size;
  348. 		}
  349. 		_front = _back = NULL;
  350. 	}
  351. }
  352. #endif
  353. #include <iostream>
  354. #include<list>
  355. int main()
  356. {
  357.     std::list<int> l;
  358. 	sv::list<int> l2;
  359. 	typedef sv::list<int> L;
  360.  
  361. 	L lst;
  362. 	for(int i = 0; i < 10; ++i)
  363. 		lst.push_front(i + 1);
  364. 	lst.resize(20, 9333);
  365. 	if(!lst.empty())
  366. 		std::cout<<"front= " << lst.front()<<" back= "<<lst.back()<<" size= "<<lst.size()<<std::endl;
  367. 	{
  368. 	L lst2 = lst;
  369. 	if(!lst2.empty())
  370. 		std::cout<<"front= " << lst2.front()<<" back= "<<lst2.back()<<" size= "<<lst2.size()<<std::endl;
  371. 	}
  372. 	L::iterator it;
  373. 	for(it=lst.begin(); it != lst.end(); ++it)
  374. 		std::cout<<*it<<std::endl;
  375. 	//reverse iterator
  376. 	L::reverse_iterator rit;
  377. 	std::cout<<"reverse"<<std::endl;
  378. 	for(rit=lst.rbegin(); rit != lst.rend(); ++rit)
  379. 		std::cout<<*rit<<std::endl;
  380. 	//std::cout<<l.max_size()<<std::endl;
  381. 	//std::cout<<lst.max_size()<<std::endl;
  382. }
Success #stdin #stdout 0.01s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
front= 10 back= 9333 size= 20
front= 10 back= 9333 size= 20
10
9
8
7
6
5
4
3
2
1
9333
9333
9333
9333
9333
9333
9333
9333
9333
9333
reverse
9333
9333
9333
9333
9333
9333
9333
9333
9333
9333
1
2
3
4
5
6
7
8
9
10
https://ideone.com/lN6NSA
language:
C++ (gcc 8.3)
created:
12 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!