C++容器与迭代器
副标题#e#
* 容器的迭代器尚有几种：
+ iterator：正常迭代器（常用）
+ reverse_iterator：反向迭代器（有时也用）
– rbegin（），rend（）//返回反向迭 代器
+ const_iterator：常量迭代器
+ const_reverse_iterator：
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（）；//删除尾部元素
—– ——————————
#p#副标题#e#
序列式容器差异点vector 雷同于数组，也支持 ‘[]’，不做越界查抄，但更安详；能自动增长。
vector.at（下标）；//如 果越界会throw异常，返回的是引用
vector.reserve（n）//保存空间（没须要用）
vector.capacity（）//今朝容量（没须要用），用size（）
vector只适合在 末端插入和删除数据
vector的查找效率高而list低
list对付频繁的插入与删 除做了优化。
每每尺度库抛出的异常都可以用exception类来catch
//vector例子
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> vi;
cout << "Input scores,end by -1:";
int s;
int m=0;
for(;;){
cin >> s;
if(s==-1) break;
vi.push_back(s);
if(s>m)
m = s;
}
int inc = 100-m;
for(int i=0; i<vi.size(); i++)
vi[i] += inc;
for(int i=0; i<vi.size(); i++)
cout << vi[i] << ' ';
cout << endl;
try{
cout << "vi[1000]=" << vi[1000] << 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（） ，因为它不是持续存放的。
尺度模板库里比巨细都用<，比便是用 ==
c1.splice(pos,c2)//转移,就是挪走了
c1.splice(pos,c2,it)//把c2中it位置的元素转移到c1的pos处
c1.splice(pos,c2,区间)//把c2里的区间转移到c1的pos
c1.merge(c2)//自动合并排序到符合的位置
remove(val)//删除指定值的元素
//list.cc
#include <iostream>
using namespace std;
#include <list>
int main()
{
int cpp[5] = {3,5,6,8,9};
int java[8] = {1,2,3,4,5,6,7,8};
int Unix[4] = {3,4,5,6};
list<int> 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<int>::iterator it = li.begin();
while(it!=li.end())
cout << *it++ << ' ';
cout << endl;
}
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，value> 支持[key]
multimap Y pair<key，value> N
set N key N
multiset Y key N
————————————- —————-
#p#分页标题#e#
//map.cc
#include <iostream>
#include <map>
using namespace std;
#include <string>
int main()
{
map<int, string> m;
m.insert(make_pair(1001,"李明"));
m.insert(make_pair(1002,"王国"));
m.insert(make_pair(1005,"失小"));
m[1006] = "刘华";
m.insert(make_pair(1001,"娜娜"));
map::iterator it;
it = m.begin();
while(it!=it.end()){
cout << it->first << ':' << it->second << endl;
++ it;//会比it++机能高
}
}
对付set,map来说反复的插入被忽略.
//multimap
//一切操纵都是对key而言的
//key必然要支持小于运算符,否则是不能举办排序的
#include <iostream>
using namespace std;
#include <map>
#include <string>
int main()
{
typedef multimap<string,string> 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 << ib->first <<',' << ib->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 << ib->first <<',' << ib->second << endl;
++ ib;
}//end while
}//end main
//set
//同样的插入同样被忽略
#include <iostream>
using namespace std;
#include <set>
int main()
{
set<int> si;
int userid[5] = {1,3,3,4,5};
for(int i=0;i<5; i++)
si.insert(userid[i]);
set<int>::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 <iostream>
using namespace std;
#include <set>
template<typename Iter>
void show(Iter ib, Iter ie)
{
while(ib!=ie)
cout << *ib++ << ' ';
cout << endl;
}
int main()
{
int a[5] = {5,1,7,5,1};
multiset<int> pids(a,a+5);
show(pids.begin(),pids.end());
pids.insert(7);
pids.insert(7);
pids.insert(7);
pids.erase(pids.find(5));
show(pids.begin(),pids.end());
cout << "end process 7..." << endl;
pids.erase(7);
show(pids.begin(),pids.end());
}//end main
=================================================
* STL Algorithms
+ 险些所用的算法都事情在某个区间
+ Search：for_each（beg， end，fun），find（beg，end，data），find_first_of
（），find_end（） ……
+ Sort：sort（），reverse（）……
+ Copy ：copy（），copy_backward（）……
+ Modify：replace（beg，end， oldv，newv），merge（），remove（）/*假删除，与erase（）
一起用来实现真正的 删除*/，c.erase（remove（……），c.end（））；//都这么用+ Numeric： min（，max（），count（），swap（），accumulate（）
容器适配器
+ stack<范例>（push，pop，size，empty，clear，top）
+ queue<范例> （push，pop，size，empty，clear，front，back）
+ priority_queue<范例> （优先行列）
