###STL学习--适配器

点击查看Evernote原文。

#@author:       gr
#@date:         2014-08-24
#@email:        forgerui@gmail.com

STL中的适配器。

###stl学习
　|--迭代器
　|--类属算法
　|--容器
　　　|--vector
　　　|--deque
　　　|--list
　　　|--set
　　　|--map
　|--函数对象
　|--适配器
　|--分配器

一、Contents

适配器概述：

适配器作用是改变其他组件的接口。它们是以模板类的形式定义的，并且以另一种组件的类型作为参数。STL提供了3种适配器组件，包括容器适配器、迭代适配器和函数适配器。

容器适配器

1. 栈容器适配器(stack)

栈适配器只有有限的接口，包括push,pop,top,empty,size。可以用vector,deque,list实现。其中pop函数没有返回值，要取值，先用top函数获取。

stack是类型为T的栈，默认情况下以deque实现。
stack< T, vector >是类型为T的栈，以vector实现。
stack< T, list >是类型为T的栈，以list实现。
stack< T, deque >是类型为T的栈，以deque实现。

stack<int> s;
int thedata[] = {1, 2, 3, 4};
for (int i = 0; i < 4; i++){
    s.push(thedata[i]);
}
s.pop();
cout<<s.top();
cout<<s.size();
while (!s.empty())
    s.pop();

2. 队列适配器(queue)

queue提供的操作包括：empty,size,front,back,push,pop。同样，pop没有返回值。队列适配器可以使用list和deque实现。没有vector，因为它不支持pop_front，实际上实现pop_front很容易，v.erase(v.begin());便可以，但是这个操作需要将后面所有值都前移，效率太低，没有vector没有提供这种接口。

queue类型为T的队列，默认情况下以deque实现。
queue<T, list >类型为T的队列，以list实现。
queue<T, deque >类型为T的队列，以deque实现。

int thedata[] = {1, 2, 3, 4};
//使用list实现
queue<int, list<int> > q;
for (int i = 0; i < 4; i++){
    q.push(the_data[i]);
}
q.pop();

3. 优先级队列容器适配器

优先级队列根据元素之间某种特定的排序准则，只有序列中最大的元素可以第一个被检索到。可以用具有随机访问迭代器的容器实现，即可以使用vector和list实现。

priority_queue将int类型保存到vector中，并使用默认的比较对象less<int>。
priority_queue<int, list, greater >将int类型保存到list中，并使用greater<int>比较对象。
priority_queue<int, vector, greater >将int类型保存到vecotr中，并使用greater<int>比较对象。

int thedata[] = {1, 2, 3, 4};
//使用默认
priority_queue<int> pq;
for (int i = 0; i < 4; i++){
    pq.push(the_data[i]);
}
pq.pop();

迭代器适配器

1. 反向迭代器适配器

迭代器适配器是用来改变迭代器组件的STL组件。STL中只预定了这一种迭代器适配器。容器都直接提供了反向迭代器，reverse_iterator和const_inverse_iterator，也可以使用rbegin和rend。

使用accumulate进行浮点数相加时，如果是从大到小排序，则一般相加是从大到小相加，然而我们知道，先将小数进行相加，可以获得更高的准确率，一个例子中，从左向右结果为1，而从右向左（小数先加）的结果为1.000000119，得到的结果更加精确。

float sum1 = accumulate(v.begin(), v.end(), (float)0.0);
float sum2 = accumulate(v.rbegin(), v.rend(), (float)0.0);
//使用反向迭代器,从后往前遍历
vector<char>::reverse_iterator r = find(v.rbegin(), v.rend(), 't');
//从后往前拷贝
copy(r, v.rend(), out);

函数适配器

函数适配器可以帮助我们创建各类更加广泛的函数对象。STL提供了3种类型函数适配器：绑定器(binder)，取反器(negator)和函数指针适配器。

1. 绑定器

可以把二元函数的一个参数绑定到一个特定的值，将二元函数转化为一元函数。

//可以使用bind1st去绑定第一个参数，下面程序的功能是查找第一个>200元素位置
int* where = find_if(&arr[0], &arr[100], bind2nd(greater<int>(), 200));
//greater operator()定义
bool operator() (int x, int y) const { return x > y;}
//使用bind2nd后可以理解为
bool operator() (intx) const { return x > 200;}

2. 取反器

取反器是一种用来对判决函数对象取反的函数适配器。STL提供了两种类型的取反适配器，not1和not2。
not1是对一元判决函数取反，not2是对二元判决函数取反。

//查找第一个不大于200(即<=200)的元素
int* where = find_if(&arr[0], &arr[100], not1(bind2nd(greater<int>(), 200)));
//上面也可以直接用函数对象less_equal实现，更明确
int* where = find_if(&arr[0], &arr[100], bind2nd(less_equal<int>(), 200));

3. 函数指针适配器

提供函数指针适配器的目的是为了让指向一元二元函数的指针能够与STL所提供的其它函数适配器一起工作。

如果在一个程序中需要使用两种不同的集合，但它们只有比较函数不同，如下定义：

set<string, less<string> > set11;
set<string, greater<string> > set2;

尽管两个实体的大部分实现代码都相同，编译器还是会重复生成两个实体的大部分或全部实现代码，为了避免这种代码重复，可以只声明set的一个实体，并使用函数指针适配器作为其比较函数的类型，用来保持集合中元素的有序性。

set<string, pointer_to_binary_function<const string&, const string&, bool> >

具体实现需要合用ptr_fun：

bool less1(const string& x, const string& y){
    return x < y;
}
bool greater1(const string& x, const string& y){
    return x > y;
}
int main(){
    typedef set<string, pointer_to_binary_function<const string&, const string&, bool> > set_type1
    
    set_type1 set1(ptr_fun(less1));
    //可以使用set1了
    set1.insert("the");
    set_type1 set2(ptr_fun(greater1));
    //可以使用set2了
    set2.inser("the");
}

这种操作利用函数指针需要直接寻址，比使用不同的set实体的程序慢一点，但这种方式可以大大降低可执行文件大小。

二、Miscellany

@author gr  
@mail   forgerui@gmail.com