map与iterator

* 容器的迭代器还有几种: 
   + 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
using namespace std;
#include

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[i] += inc;
        for(int i=0; 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
using namespace std;
#include

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] 
multimap   Y    pair      N 
set   N key     N 
multiset   Y key     N 
----------------------------------------------------- 

//map.cc
#include
#include
using namespace std;
#include

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
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 << 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
using namespace std;
#include

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
using namespace std;
#include

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