C++容器与迭代器

* 容器的迭代器还有几种:
   + 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();//删除尾部元素
-----------------------------------
序列式容器不同点
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
-----------------------------------------------------

//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<类型>(优先队列)