• ＜STL标准库中对stack、queue、priority_queue及反向迭代器的模拟实现＞——《C++初阶》

    目录

    1.模拟实现stack：

    2. 模拟实现queue

    3.模拟实现priority_queue:

    4.反向迭代器 ：

    4.1  ReverseIterator.h:

    4.2  list的反向迭代器：

    4.3  vector的反向迭代器： 

     4.4 test.cpp:

    后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！                                                                 ——By 作者：新晓·故知

    对于STL标准库中stack、queue、priority_queue及反向迭代器的模拟实现，简单实现常用函数接口，了解并学习迭代器的适配以及反向迭代器用到的迭代器萃取技术，模拟实现综合性高，这里只进行学习了解，具体可参见STL源码。

    1.模拟实现stack：

    简单实现常用函数接口:push、pop、top、size、empty等，附用deque等。

    （1）stack.h:

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. using namespace std;
    8. namespace my
    9. {
    10. 	template<class T, class Container = deque>
    11. 	class stack
    12. 	{
    13. 	public:
    14. 		void push(const T& x)
    15. 		{
    16. 			_con.push_back(x);
    17. 		}
    18. 		void pop()
    19. 		{
    20. 			_con.pop_back();
    21. 		}
    22. 		const T& top()
    23. 		{
    24. 			return _con.back();
    25. 		}
    26. 		size_t size()
    27. 		{
    28. 			return _con.size();
    29. 		}
    30. 		bool empty()
    31. 		{
    32. 			return _con.empty();
    33. 		}
    34. 	private:
    35. 		Container _con;
    36. 	};
    37. }

    （2）test.cpp:

    1. #include"Stack.h"
    2.  
    3. void test_stack()
    4. {
    5. 	my::stack<int> s;                      //附用std::deque
    6. 	//my::stack> s;  //附用std::vector
    7. 	//my::stack> s;    //附用std::list
    8. 	//my::stack s;       //附用std::string,数据过大会存在截断数据丢失
    9.  
    10. 	s.push(1);
    11. 	s.push(2);
    12. 	s.push(3);
    13. 	s.push(4);
    14. 	s.push(500);
    15.  
    16. 	while (!s.empty())
    17. 	{
    18. 		cout << s.top() << " ";
    19. 		s.pop();
    20. 	}
    21. 	cout << endl;
    22. }
    23. int main()
    24. {
    25. 	test_stack();
    26.  
    27. 	return 0;
    28. }

    1. #include
    2. namespace byte
    3. {
    4. 	template<class T, class Con = deque>
    5. 	//template>
    6. 	//template>
    7. 	class stack
    8. 	{
    9. 	public:
    10. 		stack() {}
    11. 		void push(const T& x) { _c.push_back(x); }
    12. 		void pop() { _c.pop_back(); }
    13. 		T& top() { return _c.back(); }
    14. 		const T& top()const { return _c.back(); }
    15. 		size_t size()const { return _c.size(); }
    16. 		bool empty()const { return _c.empty(); }
    17. 	private:
    18. 		Con _c;
    19. 	};
    20. }

    2. 模拟实现queue

     简单实现常用函数接口:push、pop、front、back、size、empty等，附用deque、list等。

    （1）Queue.h:

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. using namespace std;
    9.  
    10. namespace my
    11. {
    12. 	template<class T,class Container =deque>
    13. 	class queue
    14. 	{
    15. 	public:
    16. 		void push(const T& x)
    17. 		{
    18. 			_con.push_back(x);
    19. 		}
    20. 		void pop()
    21. 		{
    22. 			_con.pop_front();
    23. 		}
    24. 		const T& front()
    25. 		{
    26. 			return _con.front();
    27. 		}
    28. 		const T& back()
    29. 		{
    30. 			return _con.back();
    31. 		}
    32. 		size_t size()
    33. 		{
    34. 			return _con.size();
    35. 		}
    36. 		bool empty()
    37. 		{
    38. 			return _con.empty();
    39. 		}
    40. 	private:
    41. 		Container _con;
    42.  
    43. 	};
    44.  
    45. }

    （2）test.cpp:

    1. #include"Queue.h"
    2. void test_queue()
    3. {
    4. 	my::queue<int> q;                    //附用std::deque
    5. 	//my::queue> q;  //附用std::list
    6. 	
    7. 	q.push(1);
    8. 	q.push(2);
    9. 	q.push(3);
    10. 	q.push(4);
    11.  
    12. 	while (!q.empty())
    13. 	{
    14. 		cout << q.front() << " ";
    15. 		q.pop();
    16. 	}
    17. 	cout << endl;
    18. }
    19. int main()
    20. {
    21. 	test_queue();
    22. 	return 0;
    23. }

    1.  
    2. #include
    3. #include 
    4. namespace byte
    5. {
    6. 	template<class T, class Con = deque>
    7. 	//template>
    8. 	class queue
    9. 	{
    10. 	public:
    11. 		queue() {}
    12. 		void push(const T& x) { _c.push_back(x); }
    13. 		void pop() { _c.pop_front(); }
    14. 		T& back() { return _c.back(); }
    15. 		const T& back()const { return _c.back(); }
    16. 		T& front() { return _c.front(); }
    17. 		const T& front()const { return _c.front(); }
    18. 		size_t size()const { return _c.size(); }
    19. 		bool empty()const { return _c.empty(); }
    20. 	private:
    21. 		Con _c;
    22. 	};
    23. }

    3.模拟实现priority_queue:

    简单实现常用函数接口:push、pop、top、size、empty等，附用deque等。对于priority_queue模拟实现，还涉及仿函数less 、greater调整优先级，建立堆以及堆的调整，综合性高。

    （1）priority_queue:

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9.  
    10. using namespace std;
    11.  
    12. //仿函数版1
    13. //namespace my
    14. //{
    15. //	A
    16. //	仿函数/函数对象  --对象可以像调用函数一样去使用
    17. //	//struct less
    18. //	//{
    19. //	//	bool operator()(int x, int y)
    20. //	//	{
    21. //	//		return x < y;
    22. //	//	}
    23. //	//};
    24. //
    25. //	//可比较不同类型，int，double等
    26. //	//仿函数less 
    27. //	template
    28. //	struct less
    29. //	{
    30. //		bool operator()(const T& x, const T& y) const
    31. //		{
    32. //			return x < y;
    33. //		}
    34. //	};
    35. //	//仿函数greater
    36. //	template
    37. //	struct greater
    38. //	{
    39. //		bool operator()(const T& x, const T& y) const
    40. //		{
    41. //			return x > y;
    42. //		}
    43. //	};
    44. //	//仿函数可以替代函数指针
    45. //	
    46. //	//优先级队列： 大堆用<   小堆用>
    47. //	template,class Compare=less>
    48. //	class priority_queue
    49. //	{
    50. //	public:
    51. //		void AdjustUp(int child)
    52. //		{
    53. //			Compare comFunc;
    54. //			int parent = (child - 1) / 2;
    55. //			while (child > 0)
    56. //			{
    57. //				//if (_con[parent] < _con[child])
    58. //				if(comFunc(_con[parent], _con[child]))   //if (comFunc.operator()(_con[parent], _con[child]))
    59. //				{
    60. //					swap(_con[parent], _con[child]);
    61. //					child = parent;
    62. //					parent = (child - 1) / 2;
    63. //				}
    64. //				else
    65. //				{
    66. //					break;
    67. //				}
    68. //			}
    69. //		}
    70. //		void push(const T& x)
    71. //		{
    72. //			_con.push_back(x);
    73. //			AdjustUp(_con.size() - 1);
    74. //
    75. //		}
    76. //		void AdjustDown(int parent)
    77. //		{
    78. //			Compare comFunc;
    79. //
    80. //			size_t child = parent * 2 + 1;
    81. //			while (child<_con.size())
    82. //			{
    83. //				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
    84. //				if (child + 1 < _con.size() &&comFunc(_con[child], _con[child + 1]))
    85. //				{
    86. //					++child;
    87. //				}
    88. //				//if (_con[parent]<_con[child])	
    89. //				if (comFunc(_con[parent] ,_con[child]))
    90. //				{
    91. //					swap(_con[parent], _con[child]);
    92. //					parent = child;
    93. //					child = parent * 2 + 1;
    94. //				}
    95. //				else
    96. //				{
    97. //					break;
    98. //				}
    99. //			}
    100. //		}
    101. //		void pop()
    102. //		{
    103. //			assert(!_con.empty());
    104. //			swap(_con[0], _con[_con.size() - 1]);
    105. //			_con.pop_back();
    106. //
    107. //			AdjustDown(0);
    108. //		}
    109. //		const T& top()
    110. //		{
    111. //			return _con[0];
    112. //		}
    113. //		size_t size()
    114. //		{
    115. //			return _con.size();
    116. //		}
    117. //		bool empty()
    118. //		{
    119. //			return _con.empty();
    120. //		}
    121. //	private:
    122. //		Container _con;
    123. //	};
    124. //}
    125.  
    126.  
    127. 函数指针版
    128. //namespace my
    129. //{
    130. //	bool ComIntLess(int x1, int x2)
    131. //	{
    132. //		return x1 > x2;
    133. //	}
    134. //	//仿函数less 
    135. //	template
    136. //	struct less
    137. //	{
    138. //		bool operator()(const T& x, const T& y) const
    139. //		{
    140. //			return x < y;
    141. //		}
    142. //	};
    143. //	//仿函数greater
    144. //	template
    145. //	struct greater
    146. //	{
    147. //		bool operator()(const T& x, const T& y) const
    148. //		{
    149. //			return x > y;
    150. //		}
    151. //	};
    152. //	
    153. //	//template, class Compare = less>
    154. //	template, class Compare = less>
    155. //
    156. //	class priority_queue
    157. //	{
    158. //	public:
    159. //		priority_queue(const Compare& comFunc = Compare())
    160. //			:_comFunc(comFunc)
    161. //			
    162. //		{}
    163. //		void AdjustUp(int child)
    164. //		{
    165. //			//Compare comFunc;
    166. //			int parent = (child - 1) / 2;
    167. //			while (child > 0)
    168. //			{
    169. //				//if (_con[parent] < _con[child])
    170. //				if (_comFunc(_con[parent], _con[child]))   //if (comFunc.operator()(_con[parent], _con[child]))
    171. //				{
    172. //					swap(_con[parent], _con[child]);
    173. //					child = parent;
    174. //					parent = (child - 1) / 2;
    175. //				}
    176. //				else
    177. //				{
    178. //					break;
    179. //				}
    180. //			}
    181. //		}
    182. //		void push(const T& x)
    183. //		{
    184. //			_con.push_back(x);
    185. //			AdjustUp(_con.size() - 1);
    186. //
    187. //		}
    188. //		void AdjustDown(int parent)
    189. //		{
    190. //			Compare comFunc;
    191. //
    192. //			size_t child = parent * 2 + 1;
    193. //			while (child < _con.size())
    194. //			{
    195. //				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
    196. //				if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1]))
    197. //				{
    198. //					++child;
    199. //				}
    200. //				//if (_con[parent]<_con[child])	
    201. //				if (_comFunc(_con[parent], _con[child]))
    202. //				{
    203. //					swap(_con[parent], _con[child]);
    204. //					parent = child;
    205. //					child = parent * 2 + 1;
    206. //				}
    207. //				else
    208. //				{
    209. //					break;
    210. //				}
    211. //			}
    212. //		}
    213. //		void pop()
    214. //		{
    215. //			assert(!_con.empty());
    216. //			swap(_con[0], _con[_con.size() - 1]);
    217. //			_con.pop_back();
    218. //
    219. //			AdjustDown(0);
    220. //		}
    221. //		const T& top()
    222. //		{
    223. //			return _con[0];
    224. //		}
    225. //		size_t size()
    226. //		{
    227. //			return _con.size();
    228. //		}
    229. //		bool empty()
    230. //		{
    231. //			return _con.empty();
    232. //		}
    233. //	private:
    234. //		Compare _comFunc;
    235. //		Container _con;
    236. //	};
    237. //}
    238.  
    239. //仿函数版2
    240. namespace my
    241. {
    242. 	A
    243. 	仿函数/函数对象  --对象可以像调用函数一样去使用
    244. 	//struct less
    245. 	//{
    246. 	//	bool operator()(int x, int y)
    247. 	//	{
    248. 	//		return x < y;
    249. 	//	}
    250. 	//};
    251.  
    252. 	//可比较不同类型，int，double等
    253. 	//仿函数less 
    254. 	template<class T>
    255. 	struct less
    256. 	{
    257. 		bool operator()(const T& x, const T& y) const
    258. 		{
    259. 			return x < y;
    260. 		}
    261. 	};
    262. 	//仿函数greater
    263. 	template<class T>
    264. 	struct greater
    265. 	{
    266. 		bool operator()(const T& x, const T& y) const
    267. 		{
    268. 			return x > y;
    269. 		}
    270. 	};
    271. 	//仿函数可以替代函数指针
    272.  
    273. 	//优先级队列： 大堆用<   小堆用>
    274. 	template<class T, class Container = vector, class Compare = less>
    275. 	class priority_queue
    276. 	{
    277. 	public:
    278. 		priority_queue(const Compare& comFunc = Compare())
    279. 				:_comFunc(comFunc)
    280. 		{}
    281.  
    282. 		template <class InputIterator>
    283. 		priority_queue(InputIterator first, InputIterator last,
    284. 			const Compare& comFunc = Compare())
    285. 			:_comFunc(comFunc)
    286. 		{
    287. 			while (first != last)
    288. 			{
    289. 				_con.push_back(*first);
    290. 				++first;
    291.  
    292. 			}
    293. 			//建堆（倒着建）
    294. 			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
    295. 			{
    296. 				AdjustDown(i);
    297. 			}
    298. 		}
    299. 		void AdjustUp(int child)
    300. 		{
    301. 			Compare comFunc;
    302. 			int parent = (child - 1) / 2;
    303. 			while (child > 0)
    304. 			{
    305. 				//if (_con[parent] < _con[child])
    306. 				if (comFunc(_con[parent], _con[child]))   //if (comFunc.operator()(_con[parent], _con[child]))
    307. 				{
    308. 					swap(_con[parent], _con[child]);
    309. 					child = parent;
    310. 					parent = (child - 1) / 2;
    311. 				}
    312. 				else
    313. 				{
    314. 					break;
    315. 				}
    316. 			}
    317. 		}
    318. 		void push(const T& x)
    319. 		{
    320. 			_con.push_back(x);
    321. 			AdjustUp(_con.size() - 1);
    322.  
    323. 		}
    324. 		void AdjustDown(int parent)
    325. 		{
    326. 			Compare comFunc;
    327.  
    328. 			size_t child = parent * 2 + 1;
    329. 			while (child < _con.size())
    330. 			{
    331. 				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
    332. 				if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]))
    333. 				{
    334. 					++child;
    335. 				}
    336. 				//if (_con[parent]<_con[child])	
    337. 				if (comFunc(_con[parent], _con[child]))
    338. 				{
    339. 					swap(_con[parent], _con[child]);
    340. 					parent = child;
    341. 					child = parent * 2 + 1;
    342. 				}
    343. 				else
    344. 				{
    345. 					break;
    346. 				}
    347. 			}
    348. 		}
    349. 		void pop()
    350. 		{
    351. 			assert(!_con.empty());
    352. 			swap(_con[0], _con[_con.size() - 1]);
    353. 			_con.pop_back();
    354.  
    355. 			AdjustDown(0);
    356. 		}
    357. 		const T& top()
    358. 		{
    359. 			return _con[0];
    360. 		}
    361. 		size_t size()
    362. 		{
    363. 			return _con.size();
    364. 		}
    365. 		bool empty()
    366. 		{
    367. 			return _con.empty();
    368. 		}
    369. 	private:
    370. 		Compare _comFunc;
    371. 		Container _con;
    372. 	};
    373. }

    （2）test.cpp:

    1. #include"priority_queue.h"
    2.  
    3. //仿函数版1测试
    4. //void test_priority_queue()
    5. //{
    6. //	//问题：优先级队列（priority_queue）默认大的优先级高，但传的是less仿函数<，底层是一个大堆
    7. //	//如果想切换成小的优先级高，则传greater仿函数，底层是一个小堆，
    8. //	//这种设计是反过来的，设计有些违反常规
    9. //	//my::priority_queue pq;  //默认是大堆 less比较<
    10. //	my::priority_queue, my::greater> pq;  //greater 仿函数，默认小的优先级高，这里为小堆
    11. //	pq.push(6);
    12. //	pq.push(4);
    13. //	pq.push(7);
    14. //	pq.push(3);
    15. //	pq.push(1);
    16. //	pq.push(9);
    17. //	while (!pq.empty())
    18. //	{
    19. //		cout << pq.top() << " ";
    20. //		pq.pop();
    21. //	}
    22. //	cout << endl;
    23. //}
    24. //仿函数less测试
    25. //这个测试对应于A
    26. void test_less_function()
    27. {
    28. 	my::less LessCom;  
    29. 	cout << LessCom(6, 9) << endl;  //lessCom是一个less对象，less是仿函数，
    30. }
    31.  
    32. 仿函数less测试
    33. 这个测试对应于templ
    34. //void test_function()
    35. //{
    36. //	//可比较不同类型，int，double等
    37. //	my::less LessCom;  
    38. //	cout << LessCom(6, 9) << endl;         //LessCom是less的对象，虽然看着像函数调用，但其实是对象
    39. //
    40. //	my::greater GreaterCom;
    41. //	cout << GreaterCom(1.1, 5.4) << endl;
    42. //}
    43. //int main()
    44. //{
    45. //	test_priority_queue();
    46. //	//test_less_function();
    47. //	//test_function();
    48. //	return 0;
    49. //}
    50.  
    51.  
    52. //函数指针版测试
    53. //void test_priority_queue()
    54. //{
    55. //	bool my::ComIntLess(int x1, int x2);
    56. //	//my::priority_queue pq;
    57. //	//my::priority_queue, my::greater> pq;
    58. //	my::priority_queue, bool(*)(int,int)> pq(my::ComIntLess);  //函数名当做函数指针传过去
    59. //	pq.push(6);
    60. //	pq.push(4);
    61. //	pq.push(7);
    62. //	pq.push(3);
    63. //	pq.push(1);
    64. //	pq.push(9);
    65. //	while (!pq.empty())
    66. //	{
    67. //		cout << pq.top() << " ";
    68. //		pq.pop();
    69. //	}
    70. //	cout << endl;
    71. //
    72. //}
    73. //
    74. //
    75. //int main()
    76. //{
    77. //	test_priority_queue();
    78. //	return 0;
    79. //}
    80.  
    81. //仿函数版2测试
    82. void test_priority_queue1()
    83. {
    84. 	//问题：优先级队列（priority_queue）默认大的优先级高，但传的是less仿函数<，底层是一个大堆
    85. 	//如果想切换成小的优先级高，则传greater仿函数，底层是一个小堆，
    86. 	//这种设计是反过来的，设计有些违反常规
    87. 	//my::priority_queue pq;  //默认是大堆 less比较<
    88. 	my::priority_queue<int, std::vector<int>, my::greater<int>> pq;  //greater 仿函数，默认小的优先级高，这里为小堆
    89. 	pq.push(6);
    90. 	pq.push(4);
    91. 	pq.push(7);
    92. 	pq.push(3);
    93. 	pq.push(1);
    94. 	pq.push(9);
    95. 	while (!pq.empty())
    96. 	{
    97. 		cout << pq.top() << " ";
    98. 		pq.pop();
    99. 	}
    100. 	cout << endl;
    101. }
    102.  
    103.  
    104. void test_function1()
    105. {
    106. 	//std::vector v;
    107. 	//v.push_back(3);
    108. 	//v.push_back(6);
    109. 	//v.push_back(9);
    110. 	//v.push_back(1);
    111. 	//v.push_back(5);
    112. 	//v.push_back(2);
    113. 	//for (auto e : v)
    114. 	//{
    115. 	//	cout << e << " ";
    116. 	//}
    117. 	//cout << endl;
    118. 	//std::sort(v.begin(), v.end());               //默认升序，但调用less仿函数,与priority_queue 的仿函数顺序不一样
    119. 	//for (auto e : v)
    120. 	//{
    121. 	//	cout << e << " ";
    122. 	//}
    123. 	//cout << endl;
    124. 	//std::sort(v.begin(), v.end(),greater());  //降序，但调用greater仿函数，与priority_queue 的仿函数顺序不一样
    125. 	//for (auto e : v)								//这里greater传的是匿名对象
    126. 	//{
    127. 	//	cout << e << " ";
    128. 	//}
    129. 	//cout << endl;
    130.  
    131. 	//给数组排序
    132. 	//指向数组的原生指针，本身就是天然的迭代器
    133. 	int a[6] = { 2,7,5,9,6,3 };
    134. 	for (auto e : a)								
    135. 	{
    136. 		cout << e << " ";
    137. 	}
    138. 	cout << endl;
    139. 	std::sort(a, a + 6);  //默认升序
    140. 	for (auto e : a)								
    141. 	{
    142. 		cout << e << " ";
    143. 	}
    144. 	cout << endl;
    145. 	std::sort(a, a + 6, greater<int>()); //降序，这里greater传的是匿名对象,
    146. 	for (auto e : a)								
    147. 	{
    148. 		cout << e << " ";
    149. 	}
    150. 	cout << endl;
    151. }
    152.  
    153. //struct Goods
    154. //{
    155. //	/*bool operator<(const Goods& g)const
    156. //	{
    157. //		return _price < g._price;
    158. //	}*/
    159. //	// 多种方式比较，运算符重载就不适用，可以使用仿函数
    160. //
    161. //	string _name;
    162. //	double _price;
    163. //	size_t _saleNum;
    164. //	
    165. //};
    166. 输入输出流运算符重载
    167. //std::ostream& operator<<(std::ostream& out, const Goods& g)
    168. //{
    169. //	out << g._name <<"  " << g._price <<"  " << g._saleNum << endl;
    170. //	return out;
    171. //}
    172. //std::istream& operator>>(std::istream& in,  Goods& g)
    173. //{
    174. //	in>> g._name >> g._price >> g._saleNum;
    175. //	return in;
    176. //}
    177. //struct LessPrice
    178. //{
    179. //	bool operator()(const Goods& g1,const Goods& g2)const
    180. //	{
    181. //		return g1._price < g2._price;
    182. //	}
    183. //
    184. //};
    185. //struct GreaterPrice
    186. //{
    187. //	bool operator()(const Goods& g1, const Goods& g2)const
    188. //	{
    189. //		return g1._price > g2._price;
    190. //	}
    191. //};
    192. //
    193. //struct LessSaleNum
    194. //{
    195. //	bool operator()(const Goods& g1, const Goods& g2)const
    196. //	{
    197. //		return g1._saleNum 
    198. //	}
    199. //};
    200. //struct GreaterSaleNum
    201. //{
    202. //	bool operator()(const Goods& g1, const Goods& g2)const
    203. //	{
    204. //		return g1._saleNum > g2._saleNum;
    205. //	}
    206. //};
    207. //
    208. //void test_function2()
    209. //{
    210. //	Goods gds[] = { { "苹果", 2.1 ,100}, { "香蕉", 3 ,211}, { "橙子", 2.2,200 }, {"菠萝", 1.5,190} };
    211. //	sort(gds, gds + sizeof(gds) / sizeof(gds[0]),LessPrice());
    212. //	for (auto e : gds)
    213. //	{
    214. //		cout << e;
    215. //	}
    216. //	cout << endl;
    217. //	sort(gds, gds + sizeof(gds) / sizeof(gds[0]), GreaterPrice());
    218. //	for (auto e : gds)
    219. //	{
    220. //		cout << e;
    221. //	}
    222. //	cout << endl;
    223. //	sort(gds, gds + sizeof(gds) / sizeof(gds[0]), LessSaleNum());
    224. //	for (auto e : gds)
    225. //	{
    226. //		cout << e;
    227. //	}
    228. //	cout << endl;
    229. //	sort(gds, gds + sizeof(gds) / sizeof(gds[0]),GreaterSaleNum());
    230. //	for (auto e : gds)
    231. //	{
    232. //		cout << e ;
    233. //	}
    234. //	cout << endl;
    235. //}
    236. //建堆测试
    237. void test_priority_queue2()
    238. {
    239. 	int a[] = { 2,7,5,9,8,2,1 };
    240. 	//my::priority_queue pq(a, a + 7);
    241. 	my::priority_queue<int, std::vector<int>, my::greater<int>> pq(a, a + 7);
    242. 	cout << pq.top()<
    243. }
    244.  
    245. int main()
    246. {
    247. 	//test_priority_queue1();
    248. 	//test_function1();
    249. 	//test_function2();
    250. 	test_priority_queue2();
    251. 	return 0;
    252. }

    4.反向迭代器 ：

    与正向迭代器相比，除了++、--时方向相反，其他操作基本一致

    扩展：迭代器萃取技术。

    对于反向迭代器的模拟实现其实涉及到许多综合性实现，比如模板（只传模板参数、传多个参数），传不同参数实现用到的技术也不一样，而对于STL标准库里的实现则涉及到迭代器的萃取，这里只做简单学习了解，具体可参见STL源码。

    以下则模拟实现了模板（只传模板参数、传多个参数）两个版本，但实际应用中，建议使用传多个参数。

     

     

     

     

    4.1  ReverseIterator.h:

    1. #pragma once
    2.  
    3. //显示传3个参数
    4. namespace my
    5. {
    6. 	template<class Iterator,class Ref,class Ptr>
    7. 	struct Reverse_iterator
    8. 	{
    9. 		Iterator _it;
    10. 		typedef Reverse_iteratorSelf;
    11.  
    12. 		Reverse_iterator(Iterator it)
    13. 			:_it(it)
    14. 		{}
    15. 		Ref operator*()
    16. 		{
    17. 			Iterator tmp = _it;
    18. 			return *(--tmp);
    19. 		}
    20.  
    21. 		Ptr operator->()
    22. 		{
    23. 			return &(operator*());
    24. 		}
    25. 		Self& operator++()
    26. 		{
    27. 			--_it;
    28. 			return *this;
    29. 		}
    30. 		Self& operator--()
    31. 		{
    32. 			++_it;
    33. 			return *this;
    34. 		}
    35. 		bool operator!=(const Self& s)
    36. 		{
    37. 			return _it != s._it;
    38. 		}
    39. 	};
    40. }
    41.  
    42. 只传迭代器
    43. //namespace my
    44. //{
    45. //	template
    46. //	struct Reverse_iterator
    47. //	{
    48. //		Iterator _it;
    49. //		typedef Reverse_iteratorSelf;
    50. //		//萃取
    51. //		typedef typename Iterator::reference reference;
    52. //		typedef typename Iterator::pointer pointer;
    53. //		Reverse_iterator(Iterator it)
    54. //			:_it(it)
    55. //		{}
    56. //		//类模板、模板虚拟类型 在没有实例化之前不能去它里面找内嵌定义的类型
    57. //		//否则，类模板没有实例化，找出来的也是虚拟类型，后期无法处理
    58. //		//typename会告诉编译器后面这一块是一个类型，等Iterator实例化以后，再去它里面找这个内嵌类型
    59. //		//非萃取写法
    60. //		/*typename Iterator::reference operator*()
    61. //		{
    62. //			Iterator tmp = _it;
    63. //			return *(--tmp);
    64. //		}
    65. //
    66. //		typename Iterator::pointer operator->()
    67. //		{
    68. //			return &(operator*());
    69. //		}*/
    70. //		//萃取写法:
    71. //		reference operator*()
    72. //		{
    73. //			Iterator tmp = _it;
    74. //			return *(--tmp);
    75. //		}
    76. //
    77. //		pointer operator->()
    78. //		{
    79. //			return &(operator*());
    80. //		}
    81. //
    82. //		Self& operator++()
    83. //		{
    84. //			--_it;
    85. //			return *this;
    86. //		}
    87. //		Self& operator--()
    88. //		{
    89. //			++_it;
    90. //			return *this;
    91. //		}
    92. //		bool operator!=(const Self& s)
    93. //		{
    94. //			return _it != s._it;
    95. //		}
    96. //	};
    97. //}

    4.2  list的反向迭代器：

    1.  
    2. //反向迭代器传3个参数
    3. #pragma once
    4. #include
    5. #include
    6. #include
    7. #include"ReverseIterator.h"
    8. using namespace std;
    9.  
    10. //自定义命名空间，防止与库里的冲突
    11. namespace my
    12. {
    13. 	template<class T>
    14. 	struct list_node
    15. 	{
    16. 		list_node* _next;
    17. 		list_node* _prev;
    18. 		T _data;
    19.  
    20. 		list_node(const T& val)  //或A:给个缺省值list_node(const T& val=T())
    21. 			:_next(nullptr)
    22. 			, _prev(nullptr)
    23. 			, _data(val)
    24. 		{}
    25. 	};
    26. 	template<class T, class Ref, class Ptr> //多个模板参数
    27. 	struct __list_iterator
    28. 	{
    29. 		typedef list_node Node;
    30. 		typedef __list_iterator self;
    31. 		Node* _node;
    32. 		__list_iterator(Node* node)
    33. 			:_node(node)
    34. 		{}
    35. 		Ref operator*()
    36. 		{
    37. 			return _node->_data;
    38. 		}
    39. 		self& operator++() //默认为前置++
    40. 		{
    41. 			_node = _node->_next;
    42. 			return *this;
    43. 		}
    44. 		self& operator++(int) //后置++
    45. 		{
    46. 			self tmp(*this);
    47. 			_node = _node->_next;
    48. 			return tmp;
    49. 		}
    50. 		self& operator--()    //前置--
    51. 		{
    52. 			_node = _node->_prev;
    53. 			return *this;
    54. 		}
    55. 		self& operator--(int) //后置--
    56. 		{
    57. 			self tmp(*this);
    58. 			_node = _node->_prev;
    59. 			return tmp;
    60. 		}
    61. 		bool operator!=(const self& it)
    62. 		{
    63. 			return _node != it._node;
    64. 		}
    65. 		bool operator==(const self& it)
    66. 		{
    67. 			return _node == it._node;
    68. 		}
    69. 		//"->"重载
    70. 		Ptr operator->()
    71. 		{
    72. 			return &(operator*());//等价于return &_node->_data;
    73. 		}
    74.  
    75. 	};
    76.  
    77.  
    78. 	template<class T>
    79. 	class list
    80. 	{
    81. 		typedef list_node Node;
    82. 	public:
    83. 		typedef __list_iterator iterator;
    84. 		typedef __list_iteratorconst T&, const T*> const_iterator;
    85.  
    86. 		//反向迭代器适配支持
    87. 		typedef Reverse_iteratorreverse_iterator;
    88. 		typedef Reverse_iteratorconst T&, const T*>const_reverse_iterator;
    89.  
    90. 		reverse_iterator rbegin()
    91. 		{
    92. 			return reverse_iterator(end());
    93. 		}
    94. 		reverse_iterator rend()
    95. 		{
    96. 			return reverse_iterator(begin());
    97. 		}
    98. 		const_reverse_iterator rbegin() const
    99. 		{
    100. 			return const_reverse_iterator(end());
    101. 		}
    102. 		const_reverse_iterator rend() const
    103. 		{
    104. 			return const_reverse_iterator(begin());
    105. 		}
    106.  
    107. 		//迭代器
    108. 		iterator begin()
    109. 		{
    110. 			return iterator(_head->_next);
    111. 		}
    112. 		iterator end()
    113. 		{
    114. 			return iterator(_head);
    115. 		}
    116. 		//const迭代器:多模板参数，附用普通迭代器
    117. 		const_iterator begin() const
    118. 		{
    119. 			return const_iterator(_head->_next);
    120. 		}
    121. 		const_iterator end() const
    122. 		{
    123. 			return const_iterator(_head);
    124. 		}
    125.  
    126. 		//构造函数
    127. 		list()
    128. 		{
    129. 			_head = new Node(T());    //或A:_head = new Node(); A对应上面的A语句
    130.  
    131. 			_head->_next = _head;
    132. 			_head->_prev = _head;
    133. 		}
    134. 		//析构函数
    135. 		~list()
    136. 		{
    137. 			clear();
    138. 			delete _head;
    139. 			_head = nullptr;
    140. 		}
    141. 		//lt2(lt1)
    142. 		//构造函数传统写法
    143. 		//list(const list& lt)
    144. 		//{
    145. 		//	_head = new Node(T());  //或A:_head = new Node(); A对应上面的A语句
    146. 		//	_head->_next = _head;
    147. 		//	_head->_prev = _head;
    148. 		//	for (auto e : lt)
    149. 		//	{
    150. 		//		push_back(e);
    151. 		//	}
    152. 		//}
    153. 		//初始化
    154. 		void empty_init()
    155. 		{
    156. 			_head = new Node(T());  //或A:_head = new Node(); A对应上面的A语句
    157. 			_head->_next = _head;
    158. 			_head->_prev = _head;
    159. 		}
    160.  
    161. 		template <class InputIterator>
    162. 		list(InputIterator first, InputIterator last)
    163. 		{
    164. 			empty_init();
    165. 			while (first != last)
    166. 			{
    167. 				push_back(*first);
    168. 				++first;
    169. 			}
    170. 		}
    171. 		//交换
    172. 		void swap(list& lt)
    173. 		{
    174. 			std::swap(_head, lt._head);
    175. 		}
    176. 		//构造函数——现代写法
    177. 		list(const list& lt)
    178. 		{
    179. 			empty_init();
    180. 			list tmp(lt.begin(), lt.end());
    181. 			swap(tmp);
    182. 		}
    183. 		//赋值重载——现代写法
    184. 		list& operator=(list lt)
    185. 		{
    186. 			swap(lt);
    187. 			return *this;
    188. 		}
    189. 		void clear()   //clear清理数据，结构还在
    190. 		{
    191. 			iterator it = begin();
    192. 			while (it != end())
    193. 			{
    194. 				it = erase(it);
    195. 			}
    196. 		}
    197. 		//尾插
    198. 		void push_back(const T& x)
    199. 		{
    200. 			/*Node* tail = _head->_prev;
    201. 			Node* newnode = new Node(x);
    203. 			tail->_next = newnode;
    204. 			newnode->_prev = tail;
    205. 			newnode->_next = _head;
    206. 			_head->_prev = newnode;*/
    207. 			//附用insert
    208. 			insert(end(), x);
    209. 		}
    210. 		//头插
    211. 		void push_front(const T& x)
    212. 		{
    213. 			insert(begin(), x);
    214. 		}
    215. 		//insert插入在pos位置之前
    216. 		iterator insert(iterator pos, const T& x)
    217. 		{
    218. 			Node* newNode = new Node(x);
    219. 			Node* cur = pos._node;
    220. 			Node* prev = cur->_prev;
    221. 			prev->_next = newNode;
    222. 			newNode->_prev = prev;
    223. 			newNode->_next = cur;
    224. 			cur->_prev = newNode;
    225. 			return iterator(newNode);
    226. 		}
    227. 		//尾删
    228. 		void pop_back()
    229. 		{
    230. 			erase(--end());
    231. 		}
    232. 		//头删
    233. 		void pop_front()
    234. 		{
    235. 			erase(begin());
    236. 		}
    237. 		//删除
    238. 		iterator erase(iterator pos)
    239. 		{
    240. 			assert(pos != end());
    241. 			Node* cur = pos._node;
    242. 			Node* prev = cur->_prev;
    243. 			Node* next = cur->_next;
    244. 			prev->_next = next;
    245. 			next->_prev = prev;
    246. 			delete cur;
    247. 			return iterator(next);
    248. 		}
    249. 		//总结：list::insert不存在迭代器失效问题
    250. 		//list::erase存在野指针导致的迭代器失效
    251. 	private:
    252. 		Node* _head;
    253. 	};
    254.  
    255. }
    256.  
    257.  
    258. //反向迭代器
    259. //与正向迭代器相比，除了++、--时方向相反，其他操作基本一致
    260.  
    261.  
    262.  
    263. 只传迭代器（list只传迭代器，勉强能实现运行，但vector只传迭代器就比较复杂）
    264. //#pragma once
    265. //#include
    266. //#include
    267. //#include
    268. //#include"ReverseIterator.h"
    269. //using namespace std;
    270. //
    271. 自定义命名空间，防止与库里的冲突
    272. //namespace my
    273. //{
    274. //	template
    275. //	struct list_node
    276. //	{
    277. //		list_node* _next;
    278. //		list_node* _prev;
    279. //		T _data;
    280. //
    281. //		list_node(const T& val)  //或A:给个缺省值list_node(const T& val=T())
    282. //			:_next(nullptr)
    283. //			, _prev(nullptr)
    284. //			, _data(val)
    285. //		{}
    286. //	};
    287. //	template //多个模板参数
    288. //	struct __list_iterator
    289. //	{
    290. //		typedef list_node Node;
    291. //		typedef __list_iterator self;
    292. //		typedef  Ref reference;
    293. //		typedef  Ptr pointer;
    294. //		Node* _node;
    295. //		__list_iterator(Node* node)
    296. //			:_node(node)
    297. //		{}
    298. //		Ref operator*()
    299. //		{
    300. //			return _node->_data;
    301. //		}
    302. //		self& operator++() //默认为前置++
    303. //		{
    304. //			_node = _node->_next;
    305. //			return *this;
    306. //		}
    307. //		self& operator++(int) //后置++
    308. //		{
    309. //			self tmp(*this);
    310. //			_node = _node->_next;
    311. //			return tmp;
    312. //		}
    313. //		self& operator--()    //前置--
    314. //		{
    315. //			_node = _node->_prev;
    316. //			return *this;
    317. //		}
    318. //		self& operator--(int) //后置--
    319. //		{
    320. //			self tmp(*this);
    321. //			_node = _node->_prev;
    322. //			return tmp;
    323. //		}
    324. //		bool operator!=(const self& it)
    325. //		{
    326. //			return _node != it._node;
    327. //		}
    328. //		bool operator==(const self& it)
    329. //		{
    330. //			return _node == it._node;
    331. //		}
    332. //		//"->"重载
    333. //		Ptr operator->()
    334. //		{
    335. //			return &(operator*());//等价于return &_node->_data;
    336. //		}
    337. //
    338. //	};
    339. //
    340. //
    341. //	template
    342. //	class list
    343. //	{
    344. //		typedef list_node Node;
    345. //	public:
    346. //		typedef __list_iterator iterator;
    347. //		typedef __list_iterator const_iterator;
    348. //	
    349. //		//反向迭代器适配支持
    350. //		typedef Reverse_iteratorreverse_iterator;
    351. //		typedef Reverse_iteratorconst_reverse_iterator;
    352. //
    353. //		reverse_iterator rbegin()
    354. //		{
    355. //			return reverse_iterator(end());
    356. //		}
    357. //		reverse_iterator rend()
    358. //		{
    359. //			return reverse_iterator(begin());
    360. //		}
    361. //		const_reverse_iterator rbegin() const
    362. //		{
    363. //			return const_reverse_iterator(end());
    364. //		}
    365. //		const_reverse_iterator rend() const
    366. //		{
    367. //			return const_reverse_iterator(begin());
    368. //		}
    369. //
    370. //		//迭代器
    371. //		iterator begin()
    372. //		{
    373. //			return iterator(_head->_next);
    374. //		}
    375. //		iterator end()
    376. //		{
    377. //			return iterator(_head);
    378. //		}
    379. //		//const迭代器:多模板参数，附用普通迭代器
    380. //		const_iterator begin() const
    381. //		{
    382. //			return const_iterator(_head->_next);
    383. //		}
    384. //		const_iterator end() const
    385. //		{
    386. //			return const_iterator(_head);
    387. //		}
    388. //
    389. //		//构造函数
    390. //		list()
    391. //		{
    392. //			_head = new Node(T());    //或A:_head = new Node(); A对应上面的A语句
    393. //
    394. //			_head->_next = _head;
    395. //			_head->_prev = _head;
    396. //		}
    397. //		//析构函数
    398. //		~list()
    399. //		{
    400. //			clear();
    401. //			delete _head;
    402. //			_head = nullptr;
    403. //		}
    404. //		//lt2(lt1)
    405. //		//构造函数传统写法
    406. //		//list(const list& lt)
    407. //		//{
    408. //		//	_head = new Node(T());  //或A:_head = new Node(); A对应上面的A语句
    409. //		//	_head->_next = _head;
    410. //		//	_head->_prev = _head;
    411. //		//	for (auto e : lt)
    412. //		//	{
    413. //		//		push_back(e);
    414. //		//	}
    415. //		//}
    416. //		//初始化
    417. //		void empty_init()
    418. //		{
    419. //			_head = new Node(T());  //或A:_head = new Node(); A对应上面的A语句
    420. //			_head->_next = _head;
    421. //			_head->_prev = _head;
    422. //		}
    423. //
    424. //		template 
    425. //		list(InputIterator first, InputIterator last)
    426. //		{
    427. //			empty_init();
    428. //			while (first != last)
    429. //			{
    430. //				push_back(*first);
    431. //				++first;
    432. //			}
    433. //		}
    434. //		//交换
    435. //		void swap(list& lt)
    436. //		{
    437. //			std::swap(_head, lt._head);
    438. //		}
    439. //		//构造函数——现代写法
    440. //		list(const list& lt)
    441. //		{
    442. //			empty_init();
    443. //			list tmp(lt.begin(), lt.end());
    444. //			swap(tmp);
    445. //		}
    446. //		//赋值重载——现代写法
    447. //		list& operator=(list lt)
    448. //		{
    449. //			swap(lt);
    450. //			return *this;
    451. //		}
    452. //		void clear()   //clear清理数据，结构还在
    453. //		{
    454. //			iterator it = begin();
    455. //			while (it != end())
    456. //			{
    457. //				it = erase(it);
    458. //			}
    459. //		}
    460. //		//尾插
    461. //		void push_back(const T& x)
    462. //		{
    463. //			/*Node* tail = _head->_prev;
    464. //			Node* newnode = new Node(x);
    465. //
    466. //			tail->_next = newnode;
    467. //			newnode->_prev = tail;
    468. //			newnode->_next = _head;
    469. //			_head->_prev = newnode;*/
    470. //			//附用insert
    471. //			insert(end(), x);
    472. //		}
    473. //		//头插
    474. //		void push_front(const T& x)
    475. //		{
    476. //			insert(begin(), x);
    477. //		}
    478. //		//insert插入在pos位置之前
    479. //		iterator insert(iterator pos, const T& x)
    480. //		{
    481. //			Node* newNode = new Node(x);
    482. //			Node* cur = pos._node;
    483. //			Node* prev = cur->_prev;
    484. //			prev->_next = newNode;
    485. //			newNode->_prev = prev;
    486. //			newNode->_next = cur;
    487. //			cur->_prev = newNode;
    488. //			return iterator(newNode);
    489. //		}
    490. //		//尾删
    491. //		void pop_back()
    492. //		{
    493. //			erase(--end());
    494. //		}
    495. //		//头删
    496. //		void pop_front()
    497. //		{
    498. //			erase(begin());
    499. //		}
    500. //		//删除
    501. //		iterator erase(iterator pos)
    502. //		{
    503. //			assert(pos != end());
    504. //			Node* cur = pos._node;
    505. //			Node* prev = cur->_prev;
    506. //			Node* next = cur->_next;
    507. //			prev->_next = next;
    508. //			next->_prev = prev;
    509. //			delete cur;
    510. //			return iterator(next);
    511. //		}
    512. //		//总结：list::insert不存在迭代器失效问题
    513. //		//list::erase存在野指针导致的迭代器失效
    514. //	private:
    515. //		Node* _head;
    516. //	};
    517. //
    518. //}
    519. //
    520. //
    521. 反向迭代器
    522. 与正向迭代器相比，除了++、--时方向相反，其他操作基本一致

    4.3  vector的反向迭代器： 

    1.  
    2. //反向迭代器传3个参数
    3. #pragma once
    4. //模拟实现vector
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include"ReverseIterator.h"
    10. using namespace std;
    11.  
    12. //自定义命名空间，防止与库里的冲突
    13. namespace my
    14. {
    15. 	template<class T>
    16. 	class vector
    17. 	{
    18. 	public:
    19. 		typedef T* iterator;
    20. 		typedef const T* const_iterator;
    21. 		//反向迭代器适配支持
    22. 		typedef Reverse_iteratorreverse_iterator;
    23. 		typedef Reverse_iteratorconst T&, const T*>const_reverse_iterator;
    24.  
    25. 		reverse_iterator rbegin()
    26. 		{
    27. 			return reverse_iterator(end());
    28. 		}
    29. 		reverse_iterator rend()
    30. 		{
    31. 			return reverse_iterator(begin());
    32. 		}
    33. 		const_reverse_iterator rbegin() const
    34. 		{
    35. 			return const_reverse_iterator(end());
    36. 		}
    37. 		const_reverse_iterator rend() const
    38. 		{
    39. 			return const_reverse_iterator(begin());
    40. 		}
    41.  
    42. 		//构造函数
    43. 		vector()
    44. 			:_start(nullptr)
    45. 			, _finish(nullptr)
    46. 			, _endofstorage(nullptr)
    47. 		{}
    48. 		//使用n个val构造函数
    49. 		vector(size_t n, const T& val = T())
    50. 			:_start(nullptr)
    51. 			, _finish(nullptr)
    52. 			, _endofstorage(nullptr)
    53. 		{
    54. 			reserve(n);
    55. 			for (size_t i = 0; i < n; ++i)
    56. 			{
    57. 				push_back(val);
    58. 			}
    59. 		}
    60. 		vector(int n, const T& val = T())
    61. 			:_start(nullptr)
    62. 			, _finish(nullptr)
    63. 			, _endofstorage(nullptr)
    64. 		{
    65. 			reserve(n);
    66. 			for (size_t i = 0; i < n; ++i)
    67. 			{
    68. 				push_back(val);
    69. 			}
    70. 		}
    71. 		//类模板，类构造
    72. 		template<class InputIterator>
    73. 		vector(InputIterator first, InputIterator last)
    74. 			: _start(nullptr)
    75. 			, _finish(nullptr)
    76. 			, _endofstorage(nullptr)
    77. 		{
    78. 			while (first != last)
    79. 			{
    80. 				push_back(*first);
    81. 				++first;
    82. 			}
    83. 		}
    84. 		void swap(vector& v)
    85. 		{
    86. 			std::swap(_start, v._start);
    87. 			std::swap(_finish, v._finish);
    88. 			std::swap(_endofstorage, v._endofstorage);
    89.  
    90. 		}
    91. 		//拷贝构造函数（使用现代写法）
    92. 		vector(const vector& v)
    93. 			: _start(nullptr)
    94. 			, _finish(nullptr)
    95. 			, _endofstorage(nullptr)
    96. 		{
    97. 			vector tmp(v.begin(), v.end());
    98. 			swap(tmp); //this->swap(tmp);
    99. 		}
    100. 		//赋值重载函数(现代写法)
    101. 		vector& operator=(vector v)
    102. 		{
    103. 			swap(v);     //this->swap(v);
    104. 			return *this;
    105. 		}
    106. 		//析构函数（资源管理）
    107. 		~vector()
    108. 		{
    109. 			if (_start)
    110. 			{
    111. 				delete[] _start;
    112. 				_start = _finish = _endofstorage = nullptr;
    113. 			}
    114. 		}
    115.  
    116. 		iterator begin()
    117. 		{
    118. 			return _start;
    119. 		}
    120. 		iterator end()
    121. 		{
    122. 			return _finish;
    123. 		}
    124. 		const_iterator begin() const
    125. 		{
    126. 			return _start;
    127. 		}
    128. 		const_iterator end() const
    129. 		{
    130. 			return _finish;
    131. 		}
    132. 		size_t size() const
    133. 		{
    134. 			return _finish - _start;
    135. 		}
    136. 		size_t capacity() const
    137. 		{
    138. 			return _endofstorage - _start;
    139. 		}
    140. 		void reserve(size_t n)
    141. 		{
    142. 			size_t sz = size();
    143. 			if (n > capacity())
    144. 			{
    145. 				T* tmp = new T[n];
    146. 				if (_start)
    147. 				{
    148. 					//memcpy(tmp, _start, size() * sizeof(T));  //浅拷贝问题
    149. 					for (size_t i = 0; i < size(); ++i)
    150. 					{
    151. 						tmp[i] = _start[i];
    152. 					}
    153. 					delete[] _start;
    154. 				}
    155. 				_start = tmp;
    156. 			}
    157. 			_finish = _start + sz;
    158. 			_endofstorage = _start + n;
    159. 		}
    160. 		//总结：vector中，当T涉及深拷贝的类型时，如：string、vector等等，
    161. 		//扩容使用memcpy拷贝数据会存在浅拷贝问题，造成析构两次
    162. 		//解决：使用传值拷贝，如上
    163. 		void push_back(const T& x)
    164. 		{
    165. 			/*if (_finish == _endofstorage)
    166. 			{
    167. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    168. 				reserve(newCapacity);
    169. 			}
    170. 			*_finish = x;
    171. 			++_finish;*/
    172.  
    173. 			//附用insert
    174. 			insert(end(), x);
    175. 		}
    176. 		void pop_back()
    177. 		{
    178. 			/*if (_finish > _start)
    179. 			{
    180. 				--_finish;
    181. 			}*/
    182.  
    183. 			//附用erase
    184. 			erase(end() - 1);
    185. 		}
    186. 		T& operator[](size_t pos)
    187. 		{
    188. 			assert(pos < size());
    189. 			return _start[pos];
    190. 		}
    191. 		const T& operator[](size_t pos) const
    192. 		{
    193. 			assert(pos < size());
    194. 			return _start[pos];
    195. 		}
    196. 		//写在类里的小函数，被当做内联函数处理，减少了多次调用建立栈帧
    197. 		//void resize(size_t n, const T& val = T())
    198. 		void resize(size_t n, T val = T()) //T()匿名对象，调用默认构造函数，若T()为int（内置类型），
    199. 		{                                  //C++对于内置类型也可以认为有构造函数、析构函数，才能支持模板，只是int为0，double为0.1
    200. 			/*int i = 0;
    201. 			int j = int();
    202. 			int k = int(1);*/
    203.  
    204. 			if (n > capacity())
    205. 			{
    206. 				reserve(n);
    207. 			}
    208. 			if (n > size())
    209. 			{
    210. 				while (_finish < _start + n)
    211. 				{
    212. 					*_finish = val;
    213. 					++_finish;
    214. 				}
    215. 			}
    216. 			else
    217. 			{
    218. 				_finish = _start + n;
    219. 			}
    220. 		}
    221. 		iterator insert(iterator pos, const T& x)  //返回值为iterator,解决迭代器失效问题
    222. 		{
    223. 			//如果pos传引用，但有些时候，传不过去
    224. 			//检查参数
    225. 			assert(pos >= _start && pos <= _finish);
    226. 			//扩容
    227. 			//扩容以后，pos就失效了，要更新
    228. 			//insert导致的迭代器失效，是因为pos没更新
    229. 			if (_finish == _endofstorage)
    230. 			{
    231. 				size_t n = pos - _start;
    232. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    233. 				reserve(newCapacity);
    234. 				pos = _start + n;
    235. 			}
    236. 			//挪动数据
    237. 			iterator end = _finish - 1;
    238. 			while (end >= pos)
    239. 			{
    240. 				*(end + 1) = *end;
    241. 				--end;
    242. 			}
    243. 			*pos = x;
    244. 			++_finish;
    245. 			return pos;
    246. 		}
    247. 		//总结：迭代器在insert里的两种失效：
    248. 		//1.pos失效   2.迭代器it失效
    249.  
    250. 		iterator erase(iterator pos)
    251. 		{
    252. 			assert(pos >= _start && pos <= _finish);
    253. 			iterator it = pos + 1;
    254. 			while (it != _finish)
    255. 			{
    256. 				*(it - 1) = *it;
    257. 				++it;
    258. 			}
    259. 			--_finish;
    260. 			return pos;
    261. 		}
    262. 		//总结：
    263. 		//1.erase的失效都是意义变了，过着不在有效访问数据有效范围
    264. 		//2.一般不会使用缩容的方案，那么erase的失效也不存在野指针的失效
    265. 		//在VS和Linux不同环境下，处理不同
    266. 		//erase(pos)，使得pos失效,pos的意义改变，但是不同环境平台的处理不一样
    267. 		//在使用的时候，统一以失效的角度看待
    268.  
    269. 		//整体总结：
    270. 		//对于insert和erase造成的迭代器失效问题，Linux环境下g++检查不严格，基本依靠操作系统自身野指针越界检查机制
    271. 		//Windows环境下，VS系列检查严格，使用一些强制检查机制，意义改变造成的失效，也可能会检查出来
    272.  
    273. 		//vector迭代器的失效有两种：
    274. 		//1.扩容、缩容，导致形成野指针失效
    275. 		//2.迭代器指向的位置意义改变
    276. 		//这些通过操作系统的越界检查机制不一定能检查到
    277. 		//而通过编译器实现机制检查，相对靠谱
    278. 		void clear()
    279. 		{
    280. 			_finish = _start;
    281. 		}
    282.  
    283. 	private:
    284. 		iterator _start;
    285. 		iterator _finish;
    286. 		iterator _endofstorage;
    287.  
    288. 	};
    289. }
    290.  
    291.  
    292.  
    293. 只传迭代器（vector只传迭代器，需要萃取或者将T*封装，这里未实现）
    294. //#pragma once
    295. 模拟实现vector
    296. //#include
    297. //#include
    298. //#include
    299. //#include
    300. //#include"ReverseIterator.h"
    301. //using namespace std;
    302. //
    303. 自定义命名空间，防止与库里的冲突
    304. //namespace my
    305. //{
    306. //	template
    307. //	class vector
    308. //	{
    309. //	public:
    310. //		typedef T* iterator;
    311. //		typedef const T* const_iterator;
    312. //		//反向迭代器适配支持
    313. //		typedef Reverse_iteratorreverse_iterator;
    314. //		typedef Reverse_iteratorconst_reverse_iterator;
    315. //
    316. //		只传迭代器需要支持萃取或者将T*封装
    317. //		//typedef Reverse_iteratorreverse_iterator;
    318. //		//typedef Reverse_iteratorconst_reverse_iterator;
    319. //
    320. //		reverse_iterator rbegin()
    321. //		{
    322. //			return reverse_iterator(end());
    323. //		}
    324. //		reverse_iterator rend()
    325. //		{
    326. //			return reverse_iterator(begin());
    327. //		}
    328. //		const_reverse_iterator rbegin() const
    329. //		{
    330. //			return const_reverse_iterator(end());
    331. //		}
    332. //		const_reverse_iterator rend() const
    333. //		{
    334. //			return const_reverse_iterator(begin());
    335. //		}
    336. //
    337. //		//构造函数
    338. //		vector()
    339. //			:_start(nullptr)
    340. //			, _finish(nullptr)
    341. //			, _endofstorage(nullptr)
    342. //		{}
    343. //		//使用n个val构造函数
    344. //		vector(size_t n, const T& val = T())
    345. //			:_start(nullptr)
    346. //			, _finish(nullptr)
    347. //			, _endofstorage(nullptr)
    348. //		{
    349. //			reserve(n);
    350. //			for (size_t i = 0; i < n; ++i)
    351. //			{
    352. //				push_back(val);
    353. //			}
    354. //		}
    355. //		vector(int n, const T& val = T())
    356. //			:_start(nullptr)
    357. //			, _finish(nullptr)
    358. //			, _endofstorage(nullptr)
    359. //		{
    360. //			reserve(n);
    361. //			for (size_t i = 0; i < n; ++i)
    362. //			{
    363. //				push_back(val);
    364. //			}
    365. //		}
    366. //		//类模板，类构造
    367. //		template
    368. //		vector(InputIterator first, InputIterator last)
    369. //			: _start(nullptr)
    370. //			, _finish(nullptr)
    371. //			, _endofstorage(nullptr)
    372. //		{
    373. //			while (first != last)
    374. //			{
    375. //				push_back(*first);
    376. //				++first;
    377. //			}
    378. //		}
    379. //		void swap(vector& v)
    380. //		{
    381. //			std::swap(_start, v._start);
    382. //			std::swap(_finish, v._finish);
    383. //			std::swap(_endofstorage, v._endofstorage);
    384. //
    385. //		}
    386. //		//拷贝构造函数（使用现代写法）
    387. //		vector(const vector& v)
    388. //			: _start(nullptr)
    389. //			, _finish(nullptr)
    390. //			, _endofstorage(nullptr)
    391. //		{
    392. //			vector tmp(v.begin(), v.end());
    393. //			swap(tmp); //this->swap(tmp);
    394. //		}
    395. //		//赋值重载函数(现代写法)
    396. //		vector& operator=(vector v)
    397. //		{
    398. //			swap(v);     //this->swap(v);
    399. //			return *this;
    400. //		}
    401. //		//析构函数（资源管理）
    402. //		~vector()
    403. //		{
    404. //			if (_start)
    405. //			{
    406. //				delete[] _start;
    407. //				_start = _finish = _endofstorage = nullptr;
    408. //			}
    409. //		}
    410. //
    411. //		iterator begin()
    412. //		{
    413. //			return _start;
    414. //		}
    415. //		iterator end()
    416. //		{
    417. //			return _finish;
    418. //		}
    419. //		const_iterator begin() const
    420. //		{
    421. //			return _start;
    422. //		}
    423. //		const_iterator end() const
    424. //		{
    425. //			return _finish;
    426. //		}
    427. //		size_t size() const
    428. //		{
    429. //			return _finish - _start;
    430. //		}
    431. //		size_t capacity() const
    432. //		{
    433. //			return _endofstorage - _start;
    434. //		}
    435. //		void reserve(size_t n)
    436. //		{
    437. //			size_t sz = size();
    438. //			if (n > capacity())
    439. //			{
    440. //				T* tmp = new T[n];
    441. //				if (_start)
    442. //				{
    443. //					//memcpy(tmp, _start, size() * sizeof(T));  //浅拷贝问题
    444. //					for (size_t i = 0; i < size(); ++i)
    445. //					{
    446. //						tmp[i] = _start[i];
    447. //					}
    448. //					delete[] _start;
    449. //				}
    450. //				_start = tmp;
    451. //			}
    452. //			_finish = _start + sz;
    453. //			_endofstorage = _start + n;
    454. //		}
    455. //		//总结：vector中，当T涉及深拷贝的类型时，如：string、vector等等，
    456. //		//扩容使用memcpy拷贝数据会存在浅拷贝问题，造成析构两次
    457. //		//解决：使用传值拷贝，如上
    458. //		void push_back(const T& x)
    459. //		{
    460. //			/*if (_finish == _endofstorage)
    461. //			{
    462. //				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    463. //				reserve(newCapacity);
    464. //			}
    465. //			*_finish = x;
    466. //			++_finish;*/
    467. //
    468. //			//附用insert
    469. //			insert(end(), x);
    470. //		}
    471. //		void pop_back()
    472. //		{
    473. //			/*if (_finish > _start)
    474. //			{
    475. //				--_finish;
    476. //			}*/
    477. //
    478. //			//附用erase
    479. //			erase(end() - 1);
    480. //		}
    481. //		T& operator[](size_t pos)
    482. //		{
    483. //			assert(pos < size());
    484. //			return _start[pos];
    485. //		}
    486. //		const T& operator[](size_t pos) const
    487. //		{
    488. //			assert(pos < size());
    489. //			return _start[pos];
    490. //		}
    491. //		//写在类里的小函数，被当做内联函数处理，减少了多次调用建立栈帧
    492. //		//void resize(size_t n, const T& val = T())
    493. //		void resize(size_t n, T val = T()) //T()匿名对象，调用默认构造函数，若T()为int（内置类型），
    494. //		{                                  //C++对于内置类型也可以认为有构造函数、析构函数，才能支持模板，只是int为0，double为0.1
    495. //			/*int i = 0;
    496. //			int j = int();
    497. //			int k = int(1);*/
    498. //
    499. //			if (n > capacity())
    500. //			{
    501. //				reserve(n);
    502. //			}
    503. //			if (n > size())
    504. //			{
    505. //				while (_finish < _start + n)
    506. //				{
    507. //					*_finish = val;
    508. //					++_finish;
    509. //				}
    510. //			}
    511. //			else
    512. //			{
    513. //				_finish = _start + n;
    514. //			}
    515. //		}
    516. //		iterator insert(iterator pos, const T& x)  //返回值为iterator,解决迭代器失效问题
    517. //		{
    518. //			//如果pos传引用，但有些时候，传不过去
    519. //			//检查参数
    520. //			assert(pos >= _start && pos <= _finish);
    521. //			//扩容
    522. //			//扩容以后，pos就失效了，要更新
    523. //			//insert导致的迭代器失效，是因为pos没更新
    524. //			if (_finish == _endofstorage)
    525. //			{
    526. //				size_t n = pos - _start;
    527. //				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    528. //				reserve(newCapacity);
    529. //				pos = _start + n;
    530. //			}
    531. //			//挪动数据
    532. //			iterator end = _finish - 1;
    533. //			while (end >= pos)
    534. //			{
    535. //				*(end + 1) = *end;
    536. //				--end;
    537. //			}
    538. //			*pos = x;
    539. //			++_finish;
    540. //			return pos;
    541. //		}
    542. //		//总结：迭代器在insert里的两种失效：
    543. //		//1.pos失效   2.迭代器it失效
    544. //
    545. //		iterator erase(iterator pos)
    546. //		{
    547. //			assert(pos >= _start && pos <= _finish);
    548. //			iterator it = pos + 1;
    549. //			while (it != _finish)
    550. //			{
    551. //				*(it - 1) = *it;
    552. //				++it;
    553. //			}
    554. //			--_finish;
    555. //			return pos;
    556. //		}
    557. //		//总结：
    558. //		//1.erase的失效都是意义变了，过着不在有效访问数据有效范围
    559. //		//2.一般不会使用缩容的方案，那么erase的失效也不存在野指针的失效
    560. //		//在VS和Linux不同环境下，处理不同
    561. //		//erase(pos)，使得pos失效,pos的意义改变，但是不同环境平台的处理不一样
    562. //		//在使用的时候，统一以失效的角度看待
    563. //
    564. //		//整体总结：
    565. //		//对于insert和erase造成的迭代器失效问题，Linux环境下g++检查不严格，基本依靠操作系统自身野指针越界检查机制
    566. //		//Windows环境下，VS系列检查严格，使用一些强制检查机制，意义改变造成的失效，也可能会检查出来
    567. //
    568. //		//vector迭代器的失效有两种：
    569. //		//1.扩容、缩容，导致形成野指针失效
    570. //		//2.迭代器指向的位置意义改变
    571. //		//这些通过操作系统的越界检查机制不一定能检查到
    572. //		//而通过编译器实现机制检查，相对靠谱
    573. //		void clear()
    574. //		{
    575. //			_finish = _start;
    576. //		}
    577. //
    578. //	private:
    579. //		iterator _start;
    580. //		iterator _finish;
    581. //		iterator _endofstorage;
    582. //
    583. //	};
    584. //}

     4.4 test.cpp:

    1. #include"listplus.h"
    2. #include"vectorplus.h"
    3. #include
    4. void test_list_r_iterator()
    5. {
    6. 	my::list<int> lt;
    7. 	lt.push_back(10);
    8. 	lt.push_back(20);
    9. 	lt.push_back(30);
    10. 	lt.push_back(40);
    11. 	lt.push_back(50);
    12.  
    13. 	for (auto e : lt)
    14. 	{
    15. 		cout << e << " ";
    16. 	}
    17. 	cout << endl;
    18. 	my::list<int>::reverse_iterator rit = lt.rbegin();
    19. 	while (rit != lt.rend())
    20. 	{
    21. 		cout << *rit << " ";
    22. 		++rit;
    23. 	}
    24. 	cout << endl;
    25. }
    26. void test_vector_r_iterator()
    27. {
    28. 	my::vector<int> v;
    29. 	v.push_back(1);
    30. 	v.push_back(2);
    31. 	v.push_back(3);
    32. 	v.push_back(4);
    33. 	v.push_back(5);
    34.  
    35. 	for (auto e : v)
    36. 	{
    37. 		cout << e << " ";
    38. 	}
    39. 	cout << endl;
    40. 	my::vector<int>::reverse_iterator rit = v.rbegin();
    41. 	while (rit != v.rend())
    42. 	{
    43. 		cout << *rit << " ";
    44. 		++rit;
    45. 	}
    46. 	cout << endl;
    47. }
    48.  
    49.  
    50. template<class T>
    51. void print_list(const my::list& lt)
    52. {
    53. 	
    54. 	typename my::list::const_iterator cit = lt.begin();    //auto cit = lt.begin();   //或直接使用auto
    55.  
    56. 	while (cit != lt.end())
    57. 	{
    58. 		cout << *cit << " ";
    59. 		++cit;
    60. 	}
    61. 	cout << endl;
    62. }
    63.  
    64. template<class Container>
    65. void print_Container(const Container& lt)
    66. {
    67. 	
    68. 	typename Container::const_iterator cit = lt.begin();   //auto cit = lt.begin();   //或直接使用auto
    69.  
    70. 	while (cit != lt.end())
    71. 	{
    72. 		cout << *cit << " ";
    73. 		++cit;
    74. 	}
    75. 	cout << endl;
    76. }
    77. int main()
    78. {
    79. 	
    80. 	//test_list_r_iterator();
    81. 	//test_vector_r_iterator();
    82.  
    83. 	my::list<int> lt1;
    84. 	lt1.push_back(1);
    85. 	lt1.push_back(2);
    86. 	lt1.push_back(3);
    87. 	lt1.push_back(4);
    88. 	print_list(lt1);
    89. 	print_Container(lt1);
    90.  
    91. 	my::list lt2;
    92. 	lt2.push_back("hello");
    93. 	lt2.push_back("world");
    94. 	print_list(lt2);
    95. 	print_Container(lt2);
    96.  
    97. 	return 0;
    98. }

     

    后记：
    ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
                                                                     ——By 作者：新晓·故知

     

  • 相关阅读:
    深入理解JNINativeInterface函数＜三＞
    二硫化钨/二硒化钨纳米复合材料|WSe2二硒化钨负载掺氮三维石墨烯|氮掺杂二氧化钛负载二硒化钨|二硒化钨薄片/氧化铟纳米线复合材料
    继续总结Python中那些简单好用的用法
    【无标题】积鼎CFD VirtualFlow：航空及汽车燃油晃动流体仿真计算及试验对比
    加速老化测试目的是什么？
    路由、 网络、互联网、因特网、公网私网IP、NAT技术
    Unity之OpenXR+XR Interaction Toolkit快速监听手柄任意按键事件
    linux基础操作代码
    马斯克公开支持上班“摸鱼”，允许员工坐班听音乐，还可外放
    流量回放－The Big Picture
  • 原文地址：https://blog.csdn.net/m0_57859086/article/details/126226346