容器、迭代器.doc

容器的迭代器还有几种: + iterator:正常迭代器(常用) + reverse_iterator:反向迭代器(有时也用) - rbegin(),rend()/返回反向迭代器 + const_iterator:常量迭代器 + const_reverse_iterator: C+代码1. iteratorfind(数据) 2. for(从beg;!=end;it+) 3. if(*it=数据) 4. returnit; 5. returnend;/未找到,返回无效迭代器 6. /查询 7. *it=new_data;/更新迭代器iterator find(数据)for( 从beg;!=end;it +)if(*it=数据)return it;return end;/未找到,返回无效迭代器/查询*it = new_data;/更新迭代器- 所有的容器在插入数据时会自动加长,程序员不必关心空间问题. 容器的分类: + (sequence) - vector - list - deque 序列式容器共性 构造函数:constructor(int n);constructor(int n,T val) 调整大小:resize(int n),resize(int n,T val)一般用来加长,不一定能缩短 赋值:assign(n,val),放入n个相同的值 assign(区间(beg-end),val),把指定区间的内容放入容器 插入:insert(pos/*迭代器*/,n,val),insert(pos,区间) 毛插:push_back(val);/在末尾插入新数据 取得首尾元素:front(),back() 尾删:pop_back();/删除尾部元素 - 序列式容器不同点 vector 类似于数组,也支持,不做越界检查,但更安全;能自动增长. vector.at(下标);/如果越界会throw异常,返回的是引用 vector.reserve(n)/保留空间(没必要用) vector.capacity()/目前容量(没必要用),用size() vector只适合在末尾插入和删除数据 vector的查找效率高而list低 list对于频繁的插入与删除做了优化. 凡是标准库抛出的异常都可以用exception类来catch C+代码 1. /vector例子 2. #include 3. usingnamespacestd; 4. #include 5. 6. intmain() 7. 8. vectorvi; 9. couts; 14. if(s=-1)break; 15. vi.push_back(s); 16. if(sm) 17. m=s; 18. 19. intinc=100-m; 20. for(inti=0;ivi.size();i+) 21. vii+=inc; 22. for(inti=0;ivi.size();i+) 23. coutvii; 24. coutendl; 25. try 26. coutvi1000=vi1000endl; 27. coutvi.at(1000)=vi.at(1000)endl; 28. catch(exception&e) 29. coute.what()endl; 30. 31. /vector例子#include using namespace std;#include int main() vector vi; cout s; if(s=-1) break; vi.push_back(s); if(sm) m = s; int inc = 100-m; for(int i=0; ivi.size(); i+) vii += inc; for(int i=0; ivi.size(); i+) cout vii ; cout endl; try cout vi1000= vi1000 endl; cout vi.at(1000)= vi.at(1000) endl; catch(exception& e) cout e.what() endl; - list支持push_front(),push_back(),pop_front(),pop_back() list不支持和at(),因为它不是连续存放的. 标准模板库里比大小都用,比等于用= C+代码 1. c1.splice(pos,c2)/转移,就是挪走了 2. c1.splice(pos,c2,it)/把c2中it位置的元素转移到c1的pos处 3. c1.splice(pos,c2,区间)/把c2里的区间转移到c1的pos 4. c1.merge(c2)/自动归并排序到合适的位置 5. remove(val)/删除指定值的元素c1.splice(pos,c2)/转移,就是挪走了c1.splice(pos,c2,it)/把c2中it位置的元素转移到c1的pos处c1.splice(pos,c2,区间)/把c2里的区间转移到c1的posc1.merge(c2)/自动归并排序到合适的位置remove(val)/删除指定值的元素C+代码 1. /list.cc 2. #include 3. usingnamespacestd; 4. #include 5. 6. intmain() 7. 8. intcpp5=3,5,6,8,9; 9. intjava8=1,2,3,4,5,6,7,8; 10. intUnix4=3,4,5,6; 11. listli; 12. li.insert(li.begin(),cpp,cpp+5); 13. li.insert(li.begin(),java,java+8); 14. li.insert(li.begin(),unix,unix+4); 15. li.sort();/排序 16. li.unique();/删除相邻的重复的元素,只留一份 17. list:iteratorit=li.begin(); 18. while(it!=li.end() 19. cout*it+; 20. coutendl; 21. /list.cc#include using namespace std;#include int main() int cpp5 = 3,5,6,8,9; int java8 = 1,2,3,4,5,6,7,8; int Unix4 = 3,4,5,6; list li; li.insert(li.begin(),cpp,cpp+5); li.insert(li.begin(),java,java+8); li.insert(li.begin(),unix,unix+4); li.sort();/排序 li.unique();/删除相邻的重复的元素,只留一份 list:iterator it = li.begin(); while(it!=li.end() cout *it+ ; cout endl;- C+代码 1. deque.at() 2. deque.push_front(val); 3. deque.pop_front();deque .at()deque.push_front(val);deque.pop_front();- + 关联式 关联式迭代器的共性: - 插入不用指定位置:insert(val),会自动排序 - 查找一个指定的数据:find(val)返回指向元素的迭代器 如未找到会返回end()无效迭代器 multimap,multiset有一个统计函数:count(val)/返回val的个数 以下两个函数只对允许重复才会有意义 ib = lower_bound(val)/返回val在容器中的第一个位置 ie = upper_bound(val)/返回val在容器中的最后一个位置的下一个位置 while(ib!=ie) cout *ib+; 还有一些人喜欢另一种方式:equal_range(val)/返回一个pair 重复 元素 不同点 - map N pair 支持key multimap Y pair N set N key N multiset Y key N - C+代码 1. /map.cc 2. #include 3. #include 4. usingnamespacestd; 5. #include 6. 7. intmain() 8. 9. mapm; 10. m.insert(make_pair(1001,李明); 11. m.insert(make_pair(1002,王国); 12. m.insert(make_pair(1005,失小); 13. m1006=刘华; 14. m.insert(make_pair(1001,娜娜); 15. map:iteratorit; 16. it=m.begin(); 17. while(it!=it.end() 18. coutfirst:secondendl; 19. +it;/会比it+性能高 20. 21. 22. 23. 对于set,map来说重复的插入被忽略. 24. 25. /multimap 26. /一切操作都是对key而言的 27. /key一定要支持小于运算符,不然是不能进行排序的 28. #include 29. usingnamespacestd; 30. #include 31. #include 32. 33. intmain() 34. 35. typedefmultimapM; 36. Mmss; 37. M:iteratorib,ie; 38. mss.insert(make_pair(a,b); 39. mss.insert(make_pair(c,d); 40. mss.insert(make_pair(e,f); 41. mss.insert(make_pair(c,p); 42. mss.insert(make_pair(a,m); 43. mss.insert(make_pair(c,d); 44. mss.insert(make_pair(a,p); 45. ib=mss.begin(); 46. ie=mss.end(); 47. while(ib!=ie) 48. coutfirst,secondendl; 49. +ib; 50. /endwhile 51. coutacount:mss.count(a)endl; 52. coutccount:mss.count(c)endl; 53. ib=mss.lower_bound(c); 54. ie=mss.upper_bound(c); 55. while(ib!=ie) 56. coutfirst,secondendl; 57. +ib; 58. /endwhile 59. 60. /endmain 61. 62. /set 63. /同样的插入同样被忽略 64. #include 65. usingnamespacestd; 66. #include 67. 68. intmain() 69. 70. setsi; 71. intuserid5=1,3,3,4,5; 72. for(inti=0;i5;i+) 73. si.insert(useridi); 74. set:iteratorit; 75. it=si.begin(); 76. while(it!=si.end() 77. cout*it+; 78. coutendl; 79. coutuser3:(si.find(3)!=si.end()endl; 80. coutuser9:(si.find(9)!=si.end()endl; 81. 82. 83. /multiset 84. /用的是平衡二叉树,所以它的查找效率是相当高的. 85. #include 86. usingnamespacestd; 87. #include 88. 89. template 90. voidshow(Iterib,Iterie) 91. 92. while(ib!=ie) 93. cout*ib+; 94. coutendl; 95. 96. intmain() 97. 98. inta5=5,1,7,5,1; 99. multisetpids(a,a+5); 100. show(pids.begin(),pids.end(); 101. pids.insert(7); 102. pids.insert(7); 103. pids.insert(7); 104. pids.erase(pids.find(5); 105. show(pids.begin(),pids.end(); 106. coutendprocess7.endl; 107. pids.erase(7); 108. show(pids.begin(),pids.end(); 109. /endmain/map.cc#include #include using namespace std;#include int main()map m;m.insert(make_pair(1001,李明);m.insert(make_pair(1002,王国);m.insert(make_pair(1005,失小);m1006 = 刘华;m.insert(make_pair(1001,娜娜);map:iterator it;it = m.begin();while(it!=it.end()cout first : second endl;+ it;/会比it+性能高对于set,map来说重复的插入被忽略./multimap/一切操作都是对key而言的/key一定要支持小于运算符,不然是不能进行排序的#include using namespace std;#include #include int main() typedef multimap M; M mss; M:iterator ib,ie; mss.insert(make_pair(a,b); mss.insert(make_pair(c,d); mss.insert(make_pair(e,f); mss.insert(make_pair(c,p); mss.insert(make_pair(a,m); mss.insert(make_pair(c,d); mss.insert(make_pair(a,p); ib = mss.begin(); ie = mss.end(); while(ib!=ie) cout first , second endl; + ib; /end while cout a count : mss.count(a) endl; cout c count : mss.count(c) endl; ib = mss.lower_bound(c); ie = mss.upper_bound(c); while(ib!=ie) cout first , second endl; + ib; /end while/end main/set/同样的插入同样被忽略#include using namespace std;#include int main() set si; int userid5 = 1,3,3,4,5; for(int i=0;i5; i+) si.insert(useridi); set:iterator it; it = si.begin(); while(it!=si.end() cout *it+ ; cout endl; cout user 3 : (si.find(3)!=si.end() endl; cout user 9 : (si.find(9)!=si.end() endl;/multiset/用的是平衡二叉树,所以它的查找效率是相当高的.#include using namespace std;#include templatevoid show(Iter ib, Iter ie)