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. 			node* nodeptr(){return _node;}
  80. 		};
  81.  
  82. 		template <class U = iterator>
  83. 		class _reverse_iterator 
  84. 		{
  85. 			node* _node;
  86. 		public:
  87. 			_reverse_iterator() : _node(NULL){}
  88. 			_reverse_iterator(node* n) : _node(n){}
  89. 			_reverse_iterator(const _reverse_iterator& it) : _node(it._node){}
  90. 			T& operator*(){ if(_node)return _node->data; }
  91. 			T* operator->(){ if(_node)return &_node->data; }
  92. 			_reverse_iterator& operator++()
  93. 			{
  94. 				if(_node)
  95. 				{
  96. 					_node = _node->prev;
  97. 				}
  98. 				return *this;
  99. 			}
  100. 			_reverse_iterator operator++(int)
  101. 			{
  102. 				iterator it(*this);
  103. 				--(*this);
  104. 				return it;
  105. 			}
  106. 			_reverse_iterator& operator--()
  107. 			{
  108. 				if(_node)
  109. 				{
  110. 					_node = _node->next;
  111. 				}
  112. 				return *this;
  113. 			}
  114. 			_reverse_iterator& operator--(int)
  115. 			{
  116. 				_reverse_iterator it(*this);
  117. 				--(*this);
  118. 				return it;
  119. 			}
  120. 			bool operator!=(const _reverse_iterator& it) const { return (this->_node != it._node); }
  121.  
  122. 			_reverse_iterator& operator=(const _reverse_iterator& it)
  123. 			{
  124. 				_node = it._node;
  125. 				return *this;
  126. 			}
  127. 		}; typedef _reverse_iterator<> reverse_iterator;
  128.  
  129. 		//constructors
  130. 		list() : _front(NULL), _back(NULL), _size(NULL){}
  131. 		list(unsigned int , const T& t = T());
  132. 		list(const list<T>&);
  133. 		template < class InputIterator >
  134.         list(InputIterator first, InputIterator last);
  135. 		~list();
  136.  
  137. 		//iterators
  138. 		iterator begin();
  139. 		iterator end();
  140. 		reverse_iterator rbegin();
  141. 		reverse_iterator rend();
  142.  
  143. 		//operators
  144. 		list<T>& operator=(const list<T>&);
  145.  
  146. 		//element access
  147. 		T& front();
  148. 		T& back();
  149.  
  150. 		//capacity
  151. 		bool empty() const;
  152. 		unsigned int size() const;
  153. 		unsigned int max_size() const;
  154. 		void resize(unsigned int, const T& t = T());
  155.  
  156. 		//modifiers
  157. 		void push_front(const T&);
  158. 		void pop_front();
  159. 		void push_back(const T&);
  160. 		void pop_back();
  161. 		iterator insert(iterator pos, const T&);
  162. 		void insert(iterator pos, unsigned int size, const T&);
  163. 		template <class InputIterator>
  164. 		void insert(iterator pos, InputIterator first, InputIterator last);
  165. 		iterator erase(iterator pos);
  166. 		iterator erase(iterator first, iterator last);
  167. 		//void swap(list<T>& lst);
  168. 		void clear();
  169. 		//void assign(size_type n, const T& u);
  170. 		//void assign(InputIterator first, InputIterator last);
  171.  
  172. 		//operations
  173. 		//void remove(const T& value);
  174. 		//template <class Predicate>
  175. 		//void remove_if(Predicate pred);
  176. 		//void sort(list<T>& lst);
  177. 		//void merge(list<T>& lst):
  178. 		//void splice(iterator position, list<T,Allocator>& x);
  179. 		//void splice(iterator position, list<T,Allocator>& x, iterator i);
  180. 		//void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
  181. 		//void unique();
  182. 		//template <class BinaryPredicate>
  183. 		//void unique(BinaryPredicate binary_pred);
  184. 		//void reverse();
  185. 	};
  186.  
  187. 	template <class T>
  188. 	typename list<T>::iterator list<T>::begin()
  189. 	{
  190. 		return iterator(_front);
  191. 	}
  192.  
  193. 	template <class T>
  194. 	typename list<T>::iterator list<T>::end()
  195. 	{
  196. 		return iterator(_back->next);
  197. 	}
  198.  
  199. 	template <class T>
  200. 	typename list<T>::reverse_iterator list<T>::rbegin()
  201. 	{
  202. 		return reverse_iterator(_back);
  203. 	}
  204.  
  205. 	template <class T>
  206. 	typename list<T>::reverse_iterator list<T>::rend()
  207. 	{
  208. 		return reverse_iterator(_front->prev);
  209. 	}
  210.  
  211. 	template <class T>
  212. 	list<T>::list(unsigned int sz, const T& t) : _front(NULL), _back(NULL), _size(NULL)
  213. 	{
  214. 		while(_size < sz)
  215. 			push_back(t);
  216. 	}
  217.  
  218. 	template <class T>
  219. 	list<T>::list(const list<T>& lst) : _front(NULL), _back(NULL), _size(NULL)
  220. 	{
  221. 		if(!lst.empty())
  222. 		{
  223. 			node* n = lst._front;			
  224. 			while(n)
  225. 			{
  226. 				push_back(n->data);
  227. 				n = n->next;						
  228. 			}
  229. 		}
  230. 	}
  231.  
  232. 	template <class T>
  233. 	template <class InputIterator>
  234.     list<T>::list(InputIterator first, InputIterator last) : _front(NULL), _back(NULL), _size(NULL)
  235. 	{
  236. 		while(first != last)
  237. 		{
  238. 			push_back(*first);
  239. 			++first;
  240. 		}
  241. 	}
  242.  
  243. 	template <class T>
  244. 	list<T>& list<T>::operator=(const list<T>& lst)
  245. 	{
  246. 		if(this != &lst && !lst.empty())
  247. 		{
  248. 			clear();
  249.  
  250. 			node* n = lst._front;			
  251. 			while(n)
  252. 			{
  253. 				push_back(n->data);
  254. 				n = n->next;						
  255. 			}
  256. 		}
  257. 		return this;
  258. 	}
  259.  
  260. 	template <class T>
  261. 	list<T>::~list()
  262. 	{
  263. 		clear();
  264. 	}
  265.  
  266. 	template <class T>
  267. 	bool list<T>::empty()const {return !_front;}
  268.  
  269. 	template <class T>
  270. 	unsigned int list<T>::size()const{return _size;}
  271.  
  272. 	template <class T>
  273. 	unsigned int list<T>::max_size()const {return std::numeric_limits<T>::max();}
  274.  
  275. 	template <class T>
  276. 	void list<T>::resize(unsigned int sz, const T& t)
  277. 	{
  278. 		while(sz > _size)
  279. 		{
  280. 			push_back(t);
  281. 		}
  282. 	}
  283.  
  284. 	template <class T>
  285. 	T& list<T>::front()
  286. 	{
  287. 		if(_front)
  288. 			return _front->data;
  289. 	}
  290.  
  291. 	template <class T>
  292. 	T& list<T>::back()
  293. 	{
  294. 		if(_back)
  295. 			return _back->data;
  296. 	}
  297.  
  298. 	template <class T>
  299. 	void list<T>::push_front(const T& t)
  300. 	{			
  301. 		node* n = new node(t);
  302.  
  303. 		if(_front)
  304. 		{
  305. 			n->next = _front;
  306. 			_front->prev = n;
  307. 			_front = n;
  308. 		}
  309. 		else
  310. 		{
  311. 			_back = _front = n;
  312. 		}
  313. 		++_size;
  314. 	}
  315.  
  316. 	template <class T>
  317. 	void list<T>::pop_front()
  318. 	{
  319. 		if(front)
  320. 		{
  321. 			node* n = _front->next;
  322. 			delete _front;
  323. 			_front = n;
  324. 			--_size;
  325. 		}		
  326. 	}
  327.  
  328. 	template <class T>
  329. 	void list<T>::push_back(const T& t)
  330. 	{
  331. 		node* n = new node(t);
  332.  
  333. 		if(_back)
  334. 		{
  335. 			n->prev = _back;
  336. 			_back->next = n;
  337. 			_back = n;
  338. 		}
  339. 		else
  340. 		{
  341. 			_front = _back = n;			
  342. 		}
  343. 		++_size;
  344. 	}
  345.  
  346. 	template <class T>
  347. 	void list<T>::pop_back()
  348. 	{
  349. 		if(back)
  350. 		{
  351. 			node* n = _back->prev;
  352. 			delete _back;
  353. 			_back = n;
  354. 			--_size;
  355. 		}		
  356. 	}
  357.  
  358. 	template <class T>
  359. 	typename list<T>::iterator list<T>::insert(typename list<T>::iterator pos, const T& t)
  360. 	{
  361. 		node* n = new node(t);
  362. 		node* c = pos.nodeptr();
  363. 		n->prev = c->prev;
  364. 		n->next = c;
  365. 		c->prev->next = n;
  366. 		c->prev = n;
  367. 		return typename list<T>::iterator(c);
  368. 	}
  369.  
  370. 	template <class T>
  371. 	void list<T>::insert(typename list<T>::iterator pos, unsigned int size, const T& t)
  372. 	{
  373. 		unsigned int i = 0;
  374. 		while(i < size)
  375. 		{
  376. 			pos = insert(pos,t);
  377. 			++i;
  378. 		}
  379. 	}
  380.  
  381. 	template <class T>
  382. 	template <class InputIterator>
  383. 	void list<T>::insert(typename list<T>::iterator pos, InputIterator first, InputIterator last)
  384. 	{
  385. 		while(first != last)
  386. 		{
  387. 			T& t = *first;
  388. 			pos = insert(pos,t);
  389. 			++first;
  390. 		}
  391. 	}
  392.  
  393. 	template <class T>
  394. 	typename list<T>::iterator list<T>::erase(typename list<T>::iterator pos)
  395. 	{
  396. 		node* c = pos.nodeptr();
  397. 		if(c->prev)
  398. 			c->prev->next = c->next;
  399. 		if(c->next)
  400. 			c->next->prev = c->prev;
  401. 		pos = c->next;
  402. 		delete c;
  403. 		return pos;
  404. 	}
  405.  
  406. 	template <class T>
  407. 	typename list<T>::iterator list<T>::erase(typename list<T>::iterator first, typename list<T>::iterator last)
  408. 	{
  409. 		while(first != last)
  410. 		{
  411. 			first = erase(first);
  412. 		}
  413. 		return first;
  414. 	}
  415.  
  416. 	template <class T>
  417. 	void list<T>::clear()
  418. 	{
  419. 		node* n;
  420. 		while(_front)
  421. 		{
  422. 			n = _front->next;
  423. 			delete _front;
  424. 			_front = n;
  425. 			--_size;
  426. 		}
  427. 		_front = _back = NULL;
  428. 	}
  429. }
  430. #endif
  431. #include <iostream>
  432. #include<list>
  433. struct obj
  434. {
  435.     obj():a(0),b(0){}
  436. 	int a;
  437. 	int b;
  438. };
  439. int main()
  440. {	
  441. 	typedef sv::list<int> L;
  442.  
  443. 	L lst;
  444.  
  445. 	for(int i = 0; i < 10; ++i)
  446. 		lst.push_front(i + 1);
  447.  
  448. 	lst.resize(20, 9333);
  449.  
  450. 	if(!lst.empty())
  451. 		std::cout<<"front= " << lst.front()<<" back= "<<lst.back()<<" size= "<<lst.size()<<std::endl;
  452.  
  453. 		L lst2(lst.begin(), lst.end());
  454. 		L lst3 = lst;
  455.  
  456. 	if(!lst2.empty())
  457. 		std::cout<<"front= " << lst2.front()<<" back= "<<lst2.back()<<" size= "<<lst2.size()<<std::endl;
  458.  
  459. 	L::iterator it = lst.begin();
  460. 	++it;
  461. 	std::cout<<"\nlist1"<<std::endl;
  462.  
  463. 	it = lst.erase(it);
  464. 	for(it=lst.begin(); it != lst.end(); ++it)
  465. 		std::cout<<*it<<" ";
  466. 	std::cout<<std::endl;
  467.  
  468. 	std::cout<<"\nlist2"<<std::endl;
  469. 	it=lst2.begin();	
  470. 	++it;
  471.  
  472. 	lst2.insert(it, 7577);
  473. 	lst2.insert(it,5u, 999);
  474. 	lst2.insert(it,lst.begin(),lst.end());
  475.  
  476. 	for(it=lst2.begin(); it != lst2.end(); ++it)
  477. 		std::cout<<*it<<" ";
  478. 	std::cout<<std::endl;
  479.  
  480. 	std::cout<<"\nlist3"<<std::endl;
  481. 	it=lst3.begin();	
  482. 	++it;
  483. 	++it;
  484.  
  485. 	L::iterator it2 = lst3.begin();
  486. 	// std::advance (it2,6);
  487.     for(int i =0; i<6;++i)
  488. 		++it2;
  489.     lst3.erase(it,it2);
  490.  
  491. 	for(it2=lst3.begin(); it2 != lst3.end(); ++it2)
  492. 		std::cout<<*it2<<" ";
  493. 	std::cout<<std::endl;
  494. 	//reverse iterator
  495. 	L::reverse_iterator rit;
  496.  
  497. 	std::cout<<"\nreverse list1"<<std::endl;
  498. 	for(rit=lst.rbegin(); rit != lst.rend(); ++rit)
  499. 		std::cout<<*rit<<" ";
  500.     std::cout<<std::endl;
  501.  
  502. 	//std::cout<<l.max_size()<<std::endl;
  503. 	//std::cout<<lst.max_size()<<std::endl;
  504. }
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

list1
10 8 7 6 5 4 3 2 1 9333 9333 9333 9333 9333 9333 9333 9333 9333 9333 

list2
10 7577 999 999 999 999 999 10 8 7 6 5 4 3 2 1 9333 9333 9333 9333 9333 9333 9333 9333 9333 9333 9 8 7 6 5 4 3 2 1 9333 9333 9333 9333 9333 9333 9333 9333 9333 9333 

list3
10 9 4 3 2 1 9333 9333 9333 9333 9333 9333 9333 9333 9333 9333 

reverse list1
9333 9333 9333 9333 9333 9333 9333 9333 9333 9333 1 2 3 4 5 6 7 8 10
https://ideone.com/76GVqa
language:
C++ (gcc 8.3)
created:
11 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!