C++标准程序库学习笔记

容器可分为两类：

1.序列式容器：可序群集，每个元素的位置取决于插入时间和地点，STL提供三个定义好的序列式容器：vector，list，deque

2.关联式容器：已序群集，元素的位置取决于元素值，STL提供四个定义好的关联式容器：map，multimap，set，multiset

deque是“double-end-queue”的缩写，在头部和尾部插入和删除元素十分迅速。他提供了 push_front和push_back操作，而vector只提供push_back操作。

关联式容器依据一定的排序准则，自动为元素排序，预设情况以operator <排序，也可以提供自己的比较函式，定义不同的排序准则。（见下面代码）关联式容器由二叉树实现，左子树的结点都比自己小，右结点都比自己大。

自定义排序准则示例：

#include <iostream>
#include <set>
using namespace std;

template <class T>
class RuntimeCmp
...{
public:
    enum cmp_mode...{normal,reverse};
private:
    cmp_mode mode;
public:
    RuntimeCmp(cmp_mode m=normal):mode(m)...{}
    bool operator()(const T &t1,const T &t2) const
    ...{
        return mode==normal?t1<t2:t2<t1;
    }
    bool operator == (const RuntimeCmp &rc)
    ...{
        return mode==rc.mode;
    }
};

typedef set<int ,RuntimeCmp<int>> IntSet;

void fill(IntSet &set);
void print(IntSet &set);

int main()
...{
    IntSet coll1;
    fill(coll1);
    print(coll1);

    RuntimeCmp<int >reverse_order(RuntimeCmp<int>::reverse);
    IntSet coll2(reverse_order);
    fill(coll2);
    print(coll2);

    coll1=coll2;
    coll1.insert(3);
    print(coll1);

    if(coll1.value_comp() == coll2.value_comp())
        cout<<"same sortint"<<endl;
    else 
        cout<<"different sorting"<<endl;
    return 0;
}

void fill(IntSet &set)
...{
    set.insert(4);
    set.insert(7);
    set.insert(5);
    set.insert(1);
    set.insert(6);
    set.insert(2);
    set.insert(5);
}

void print(IntSet &set)
...{
    IntSet::iterator it=set.begin();
    for(it;it!=set.end();++it)
        cout<<*it<<"   ";
    cout<<endl;
}

C++程序库还提供了一些特别的（并未预先定义好的）容器配接器，包括stack，queue，priority queue

三种迭代器的配接器(iterator adapters)：

1.Insert Iterators：可以使演算法以安插方式而不是覆盖方式运作，运用它，可以解决目标空间不足的问题，它会使目标空间的大小按需要成长,下面的例子演示了预先定义好的insert iterators

 

#include <vector>
#include <set>
#include <deque>
#include <list>
#include <algorithm>
using namespace std;

int main()
...{
    list<int > coll1;
    for(int i=1;i<9;++i)
    ...{
        coll1.push_back(i);
    }
    
    vector<int> coll2;
    copy(coll1.begin(),coll1.end(),back_inserter(coll2));

    deque<int > coll3;
    copy (coll1.begin(),coll1.end(),front_inserter(coll3));

    set <int > coll4;
    copy(coll1.begin(),coll1.end(),inserter(coll4,coll4.begin()));

    return 0;
}

 

2.Stream Iterators

3.Reverse iterators

 函式演算法示例：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void print(int elem)
...{
    cout<<elem<<"   ";
}

int main()
...{
    vector <int> coll;
    for(int i=1;i<9;++i)
        coll.push_back(i);
    for_each(coll.begin(),coll.end(),print);
    cout<<endl;
    return 0;
}

仿函式示例（function object）：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class PrintInt
...{
public:
    void operator()(int elem)  const
    ...{
        cout<<elem<<"  ";
    }
};

int main()
...{
    vector <int> coll;
    for(int i=1;i<9;++i)
        coll.push_back(i);
    for_each(coll.begin(),coll.end(),PrintInt());
    cout<<endl;
    return 0;
}