fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <memory>
  4.  
  5. template<class T, template<class> class shared_ptr = std::shared_ptr>
  6. struct Node {
  7. 	using shared_ptr_t = shared_ptr<Node<T>>;
  8.  
  9. 	shared_ptr_t next;
  10. 	T value;
  11.  
  12. 	Node(shared_ptr_t n, const T& v) {
  13. 		value = v;
  14. 		next = n;
  15. 	}
  16. };
  17.  
  18. // iterator
  19. template<class T>
  20. class iterator {
  21. public:
  22. 	using shared_ptr_t = typename Node<T>::shared_ptr_t;
  23. 	using node_t = Node<T>;
  24.  
  25. 	iterator(shared_ptr_t node) {
  26. 		m_node = node;
  27. 	}
  28. 	bool operator==(const iterator& it) const { return m_node == it.m_node; }
  29. 	bool operator!=(const iterator& it) const { return !(it == *this); }
  30.  
  31. 	bool valid() const {
  32. 		return bool(m_node);
  33. 	}
  34. 	T& operator*() const {
  35. 		return m_node->value;
  36. 	}
  37. 	shared_ptr_t node() const {
  38. 		return m_node;
  39. 	}
  40. 	void insert(const T& value) const {
  41. 		if(m_node) {
  42. 			m_node->next = std::make_shared<node_t>(m_node->next, value);
  43. 		} else {
  44. 			throw std::logic_error{"iterator can't insert first element"};
  45. 		}
  46. 	}
  47. 	shared_ptr_t next(const iterator& it) const {
  48. 		return std::exchange(m_node->next, it.m_node);
  49. 	}
  50.  
  51. 	iterator& operator++() {
  52. 		m_node = m_node->next;
  53. 		return *this;
  54. 	}
  55. 	iterator& advance(int dist) {
  56. 		while(dist-- > 0 && m_node) {
  57. 			++(*this);
  58. 		}
  59. 		return *this;
  60. 	}
  61. 	void swap(iterator& it) {
  62. 		std::swap(m_node, it.m_node);
  63. 	}
  64.  
  65. 	template<class>
  66. 	friend class List;
  67.  
  68. private:
  69. 	shared_ptr_t m_node;
  70. };
  71.  
  72. template<class T>
  73. class List {
  74. public:
  75. 	using shared_ptr_t = typename Node<T>::shared_ptr_t;
  76. 	using iterator_t = iterator<T>;
  77. 	using node_t = Node<T>;
  78.  
  79. 	List() = default;
  80. 	explicit List(const List& list) {
  81. 		this->operator=(list);
  82. 	}
  83. 	explicit List(List&& list) {
  84. 		this->operator=(std::forward(list));
  85. 	}
  86. 	explicit List(iterator_t&& fwd_it, size_t explicit_size = 0) {
  87. 		m_size = explicit_size;
  88. 		m_root = std::exchange(fwd_it.m_node, nullptr);
  89.  
  90. 		if(!m_size) {
  91. 			for(auto it = begin(); it.valid(); ++it) {
  92. 				++m_size;
  93. 			}
  94. 		}
  95. 	}
  96. 	explicit List(const iterator_t& begin, const iterator_t& end = iterator_t{nullptr}) {
  97. 		auto it = begin;
  98. 		while(it.valid() && it != end) {
  99. 			push_back(*it);
  100. 			++it;
  101. 		}
  102. 	}
  103.  
  104. 	List<T>& operator=(const List& list) {
  105. 		clear();
  106. 		for(auto& el: list) {
  107. 			push_back(el);
  108. 		}
  109.  
  110. 		m_size = list.size();
  111. 		return *this;
  112. 	}
  113. 	List<T>& operator=(List&& list) {
  114. 		m_root = std::exchange(list.m_root, nullptr);
  115. 		m_size = std::exchange(list.m_size, 0);
  116. 		return *this;
  117. 	}
  118.  
  119. 	size_t size() const {
  120. 		return m_size;
  121. 	}
  122.  
  123. 	void insert(const size_t idx, const T& value) {
  124. 		bound_check(bound_check_type::GREATER, "List<T>::insert(idx)", idx);
  125.  
  126. 		auto it = begin();
  127.  
  128. 		if(idx != 0) {
  129. 			it.advance(static_cast<int>(idx) - 1);
  130. 			it.insert(value);
  131. 		} else {
  132. 			m_root = std::make_shared<node_t>(it.node(), value);
  133. 		}
  134.  
  135. 		++m_size;
  136. 	}
  137. 	void push_back(const T& val) {
  138. 		insert(m_size, val);
  139. 	}
  140. 	void push_front(const T& val) {
  141. 		insert(0, val);
  142. 	}
  143.  
  144. 	void erase(const size_t idx) {
  145. 		bound_check(bound_check_type::GREATER_EQUAL, "List<T>::erase(idx)", idx);
  146.  
  147. 		auto it = begin();
  148. 		it.advance(static_cast<int>(idx - 1));
  149.  
  150. 		if(idx != 0) {
  151. 			auto it_fwd = it;
  152. 			it_fwd.advance(2);
  153. 			it.next(it_fwd);
  154. 		} else {
  155. 			it.advance(1);
  156. 			m_root = it.node();
  157. 		}
  158.  
  159. 		--m_size;
  160. 	}
  161. 	void pop_back() {
  162. 		erase(m_size - 1);
  163. 	}
  164. 	void pop_front() {
  165. 		erase(0);
  166. 	}
  167.  
  168. 	void clear() {
  169. 		m_root = nullptr;
  170. 		m_size = 0;
  171. 	}
  172.  
  173. 	T& operator[](size_t idx) {
  174. 		bound_check(bound_check_type::GREATER_EQUAL, "List<T>::operator[](idx)", idx);
  175. 		return *begin().advance(idx);
  176. 	}
  177.  
  178. 	const T& operator[](size_t idx) const {
  179. 		bound_check(bound_check_type::GREATER_EQUAL, "List<T>::operator[](idx) const", idx);
  180. 		return *begin().advance(idx);
  181. 	}
  182.  
  183. 	iterator_t begin() const {
  184. 		return iterator_t{m_root};
  185. 	}
  186. 	static iterator_t end() {
  187. 		return iterator_t{nullptr};
  188. 	}
  189.  
  190. private:
  191. 	enum class bound_check_type {
  192. 		GREATER, GREATER_EQUAL
  193. 	};
  194. 	void bound_check(bound_check_type type, std::string func, size_t idx) {
  195. 		if(idx > size() || (type == bound_check_type::GREATER_EQUAL && idx == size())) {
  196. 			throw std::logic_error{func + ": idx >" + (type == bound_check_type::GREATER ? "" : "=") + " size"};
  197. 		}
  198. 	}
  199.  
  200. 	shared_ptr_t m_root = nullptr;
  201. 	size_t m_size = 0;
  202. };
  203.  
  204. auto list_iterator() {
  205. 	List<int> l;
  206. 	l.push_back(20);
  207. 	l.push_back(15);
  208. 	l.push_back(8); //Eeek
  209. 	l.push_back(10);
  210. 	l.push_back(5);
  211.  
  212. 	l.erase(2); //Fix
  213.  
  214. 	return l.begin();
  215. }
  216.  
  217. int main() {
  218. 	auto it = list_iterator();
  219.  
  220. 	std::cout << "=========\n";
  221. 	List<int> l(std::move(it));
  222. 	l.pop_back();
  223. 	l.pop_front();
  224. 	// Now l should contain (15, 10).
  225.  
  226. 	std::transform(l.begin(), l.end(), l.begin(), [](int v) {return v * 2;}); //Multiply all values by two
  227.  
  228. 	// Hopefully prints 30 and 20.
  229. 	for(auto el: l) {
  230. 		std::cout << el << std::endl;
  231. 	}
  232.  
  233. 	return 0;
  234. }
  235.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=========
30
20
https://ideone.com/O6VD3N
language:
C++14 (clang 8.0)
created:
6 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!