GeekBand STL与泛型编程 第二周

5.容器（下）

Stack

Stack是一种先进后出（First In Last Out）的数据结构，只有一个出口：

• 支持push、pop和top
• 只能访问顶层元素，不能遍历
• #include<stack>

template<class _Ty, class _Container = deque<_Ty>>
class stack{
    ...
};

默认使用的容器为deque。top范围栈顶元素，但是不会弹出去，如果使用pop，则弹出栈顶元素。

Queue

Queue是一种先进先出（First In First Out）的数结构

• 支持push，pop，front和back操作
• 只能访问最前或最后元素，不允许遍历
• #include<queue>

template<class _Ty, class _Container = deque<_Ty>>
class queue{
    ...
};

默认使用的容器为deque。不允许遍历，没有迭代器。

Map and Multimap

Map

• 关联式容器，存储的对象是Key/Value pair
• 不允许有重复的key
• 对象必须具有可排序性能（Key）

template<class _Kty, class _Ty, class _Pr = less<_Kty>, 
    class _Alloc = allocator<pair<const _Kty, _Ty>>>
    class map{ ... };

• 默认采用less排序
• 可通过仿函数自定义排序
• #include<map>

map.png

插入元素：

map1.insert(std::make_pair(4, Employee(L"Brown")));
map1[5] = Empolyee(L"Fisher");

删除元素：

std::map<Person, PersonIdComparer>::iterator it = map1.begin();
map1.erase(it);

operator[]存取元素：

Employee& e = map1[2];
e.SetName(L"...");
...

Multimap

• 类似map的容器
• 允许key重复

Set and Multiset

Set

• 关联式容器，存储的对象是即是Key又是Value
• 不允许有重复的key
• 对象必须具有可排序性能

template<class _Kty, class _Pr = less<_Kty>, 
    class _Alloc = allocator<_Kty>>
    class set{ ... };

• 默认采用less排序，存储对象必须具有operator<行为
• 可通过仿函数自定义排序
• #include<set>

set.png

插入元素：

ps1.insert(Person(L"Bill", 4));

删除元素：

std::set<Person, PersonIdComparer>::iterator it = ps1.begin();
std::advance(it, 1); //it开始指向begin，通过advance增加1，之后指向第二个元素
ps1.erase(it);

相关算法：

set_union，合并两个set（具有相同的存储对象型别）

std::set<Person, PersonIdComparer> dest;
std::insert_iterator<std::set<Person, PersonIdComparer>> ii(dest, dest.begin());
std::set_union(ps1.begin(), ps1.end(), ps2.begin(), ps2.end(), ii, PersonIdComparer());

set_union.png

set_intersection，将连个set中相同的元素拿出来，放到新的set中。

std::set<Person, PersonIdComparer> dest;
std::insert_iterator<std::set<Person, PersonIdComparer>> ii(dest, dest.begin());
std::set_intersection(ps1.begin(), ps1.end(), ps2.begin(), ps2.end(), ii, PersonIdComparer());

set_intersection.png

set_difference，包含在[first1,last1)中而不包含在[first2,last2)中的元素。

std::set<Person, PersonIdComparer> dest;
std::insert_iterator<std::set<Person, PersonIdComparer>> ii(dest, dest.begin());
std::set_difference(ps1.begin(), ps1.end(), ps3.begin(), ps3.end(), ii, PersonIdComparer());

set_difference.png

特别注意：

• 用于排序的成员（在Person中对象的Id，是真正的Key）不可改变
• 出了真正的Key，其他成员可以改变但是需要特殊手法

std::set<Person, PersonIdCompare>::iterator it = ps1.find(Person(L"Bill", 4));
if(it != ps1.end()){
    it->SetName(L"Bill Gates"); //看上去没有问题，但是错误，编译不通过
}

set的实现方式不允许通过迭代器改变对象成员！

通过如下方式改变：

std::set<Person, PersonIdCompare>::iterator it = ps1.find(Person(L"Bill", 4));
if(it != ps1.end()){
    const_cast(Person&)<*it>.SetName(L"Bill Gates"); //通过const_cast将it转化为Person 的引用，在修改Person的名字。
}

一定要cast为对象的引用，如下两种方式可以编译通过，但是无法改变对象的成员：

static_cast(Person)<*it>.SetName(L"Bill Gates");
((Person)(*it)).SetName(L"Bill Gates");

因为上面两个方法的行为等同于下面的语句：

Person tempCopy(*it);
tempCopy.SetName(L"Bill Gates"); //改变的只是临时对象，并非set中的对象

扩展测试代码

#include <iostream>
#include <algorithm>
#include <string>
#include <set>

class Person{
public:
    Person(int id, std::string name): id(id), name(name){}
    std::string GetName() const{ return name; }
    void SetName(std::string n){ name = n; }
    int GetId() const{ return id; }
    void SetId(int i){ id = i; }
private:
    int id;
    std::string name;
};

std::ostream& operator<< (std::ostream& os, const Person& p){
    return os << "Id: " << p.GetId() << ", Name: " << p.GetName();
}

template<typename T>
struct PrintContainer{
    PrintContainer(std::ostream& out, std::string partition = "\n") : os(out), partition(partition){}
    void operator()(const T& x){ os << x << partition;}
    std::ostream& os;
    std::string partition;
};

template<class _Kty, class _Pr, class _Alloc>
void PrintSet(std::set<_Kty, _Pr, _Alloc> s){
    std::for_each(s.begin(), s.end(), PrintContainer<_Kty>(std::cout));
}

struct PersonIdCompare : public std::binary_function<Person, Person, bool>{
    bool operator()(Person p1, Person p2){
        return (p1.GetId() < p2.GetId()) ? true : false;
    }
};

struct PersonNameCompare : public std::binary_function<Person, Person, bool>{
    bool operator()(Person p1, Person p2){
        return (p1.GetName() < p2.GetName()) ? true : false;
    }
};

int main(){
    Person personArray1[3]={
        Person(1, "z_name"),
        Person(2, "y_name"),
        Person(3, "x_name")
    };

    std::set<Person, PersonIdCompare> psid1(personArray1, personArray1 + 3);
    std::cout << "psid1:" << std::endl;
    PrintSet(psid1);
    std::set<Person, PersonNameCompare> psname1(personArray1, personArray1 + 3);
    std::cout << "psname1:" << std::endl;
    PrintSet(psname1);

    std::set<Person, PersonIdCompare>::iterator it = psid1.find(Person(1, "z_name"));
    if(it != psid1.end()){
        std::cout << "((Person)(*it)).SetName(\"123\");" << std::endl;
        ((Person)(*it)).SetName("123");
        PrintSet(psid1);
        std::cout << "static_cast<Person>(*it).SetName(\"123\");" << std::endl;
        static_cast<Person>(*it).SetName("123");
        PrintSet(psid1);
        std::cout << "const_cast<Person&>(*it).SetName(\"123\");" << std::endl;
        const_cast<Person&>(*it).SetName("123");
        PrintSet(psid1);
    }
    getchar();
    return 0;
}

输出结果：

psid1:
Id: 1, Name: z_name
Id: 2, Name: y_name
Id: 3, Name: x_name
psname1:
Id: 3, Name: x_name
Id: 2, Name: y_name
Id: 1, Name: z_name
((Person)(*it)).SetName("123");
Id: 1, Name: z_name
Id: 2, Name: y_name
Id: 3, Name: x_name
static_cast<Person>(*it).SetName("123");
Id: 1, Name: z_name
Id: 2, Name: y_name
Id: 3, Name: x_name
const_cast<Person&>(*it).SetName("123");
Id: 1, Name: 123
Id: 2, Name: y_name
Id: 3, Name: x_name

6&7.STL整体结构，仿函数，仿函数适配器

STL整体结构

• 内存分配器 Allocator
• 容器 Containers
• 算法 Algorithms
• 迭代器 Iterators
• 仿函数 Functors
• 适配器 Adapters

stl组件关系.png

仿函数

又称作函数对象（Function Object），其作用相当于一个函数指针。

std::remove_if(v.begin(), v.end(), ContainsString(L"C+="));

STL中将这种行为函数指针定义为所谓的仿函数，其实现是一个class，再以仿函数产生一个对象作为算法的参数。

仿函数与算法之间的关系

Algorithm(Iterator first, Iterator last, ..., Functor func){
    ...
    func(...)//其实相当于调用对象中的operator()
    ...
}

仿函数的类别定义中必须重载函数调用（function call）operator()。

为什么要用仿函数而不用普通函数指针？

• 普通函数指针不能满足STL的抽象要求
• 函数指针无法和STL其他组件交互

仿函数可以作为模板实参用于定义对象的某种默认行为

class Person{...};
std::set<Person, std::less<Person>> set1, set2; //operator< 排序
std::set<Person, std::greater<Person>> set1, set2; //operator> 排序
...
if(set1 === set2)...//正确，相同的型别
if(set1 === set3)...//错误，不同的型别！

仿函数适配器

将无法匹配的仿函数“套接”成可以匹配的型别

• binder1st/binder2nd
• mem_fun/mem_fun_ref

binder1st

给定一个vector，其元素为[0, 0, 0, 0, 0, 0, 0, 0, 10, 0],通过not_equal_to来匹配第一个非0元素。

std::not_equal_to<int> f; //适配前的仿函数

typename std::not_equal_to<int>::first_argument_type nonZeroElement(0);
    //本例中实际为int，在not_equal_to<T> 中，typedef first_argument_type为T类型，并赋初值0

std::vector<int>::iterator it = std::find_if(v.begin(), b.end(),
    std::binder1st<std::not_equal_to<int>>(f，nonZeroElement));
    //注意此处为binder1st

在实际使用时，标准库封装了一个模板函数，bind1st，这个函数把定义nonZeroElement和f的过程封装掉了，因此以上三条语句可以简化为一条：

std::find_if(v.begin(), b.end(),
    std::bind1st(std::not_equal_to<int>()，0));
    //注意此处为bind1st

binder2nd

和binder1st有所区别的是，binder2nd绑定的是右值，而binder1st绑定的是左值，因此以下两条语句等价：

std::bind1st(std::less<int>(), 0);
std::bing2nd(std::greater<int>(), 0);

mem_fun

这个适配器用来适配对象的成员函数。

class Person{
public:
    Person(int id, std::string name): id(id), name(name){}
    std::string GetName() const{ return name; }
    void SetName(std::string n){ name = n; }
    int GetId() const{ return id; }
    void SetId(int i){ id = i; }
    void Print() const{ std::cout << "Id: " << id << ", Name: " << name << std::endl; }
private:
    int id;
    std::string name;
};

std::vector<Person*> v;
    v.push_back(new Person(1, "z_name"));
    v.push_back(new Person(2, "y_name"));
    v.push_back(new Person(3, "x_name"));
    
std::for_each(v.begin(), v.end(), &Person::Print);//编译错误，for_each不接受这种形式的参数

通过如下方式可以正常调用：

std::for_each(v.begin(), v.end(), std::mem_fun(&Person::Print));

mem_fun_ref

与mem_fun不同的是，mem_fun_ref采用引用，调用成员函数时，使用reference而不是指针。

std::vector<Person> v;
    v.push_back(Person(1, "z_name"));
    v.push_back(Person(2, "y_name"));
    v.push_back(Person(3, "x_name"));
    
    std::for_each(v.begin(), v.end(), std::mem_fun_ref(&Person::Print));

其他需要注意的问题

• std::string/std::wstring与vector<char>/vector<wchar_t>
  • 单线程情况下首选std::string/std::wstring
  • 多线程需注意string是否带reference count，多线程下，避免分配和拷贝的reference count省下的开销转到了并发控制上，因此可考虑使用vector<char>/vector<wchar_t>，vector不带reference conut
• new出的对象放入容器后，要在销毁容器前delete那些对象
• 尽量用算法来替代手写循环
• 容器的size（大小）和capacity（容量）是不一样的，可以使用swap为容器缩水
• 在有对象继承的情况下，建立指针的容器而不是对象的容器

8.泛型算法 非变易算法

非变易算法

非变易算法是一系列模板函数，在不改变操作对象的前提下对元素进行处理。查找、子序列搜索、统计、匹配等等。

• for_each

template<class _InIt, class _Fn1> inline
_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)

在区间[First，_Last)上对每一个元素应用_Func函数。

• find

template<class _InIt, class _Ty> inline
_InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)

在区间[First，_Last)中，如果*it=Value则返回该it，没有找到则返回_Last。

• find_if

template<class _InIt, class _Pr> inline
_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)

在区间[First，_Last)中，如果_Pred(*it)=true 则返回该it，没有找到则返回_Last。

• adjacent_find(1)

template<class _FwdIt> inline
_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)

在区间[First，_Last)中，如果*it==*(it + 1)则返回该it，没有找到则返回_Last。

• adjacent_find(2)

template<class _FwdIt, class _Pr> inline
_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)

在区间[First，_Last)中，如果_Pred(*it, *(it + 1))==true 则返回该it，没有找到则返回_Last。相当于adjacent_find(1)的_Pred默认使用的是equal_to。

• find_first_of(1)

template<class _FwdIt1, class _FwdIt2> inline
_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2)

在区间[First1，_Last1)中的it1，使得对于区间[First2，_Last2)中某个it2，满足 *it1 == *it2 则返回it1，如果没有找到则返回_Last1。

• find_first_of(2)

template<class _FwdIt1, class _FwdIt2， class _Pr> inline
_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)

在区间[First1，_Last1)中的it1，使得对于区间[First2，_Last2)中某个it2，满足 _Pred(*it1, *it2) == true, 则返回it1，如果没有找到则返回_Last1。

• count

template<class _InIt, class _Ty> inline
typename iterator_traits<_InIt>::difference_type count(_InIt _First, _InIt _Last, const _Ty& _Val)

返回在区间[First，_Last)中满足 *it==—Val 的迭代器的个数。

• count_if

template<class _InIt, class _Pr> inline
typename iterator_traits<_InIt>::difference_type count_if(_InIt _First, _InIt _Last, _Pr _Pred

返回在区间[First，_Las1)中满足 _Pred(*it)==true 的迭代器的个数。

• mismatch(1)

template<class _InIt1, class _InIt2> inline pair<_InIt1, _InIt2>
mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2)

在区间[First1，_Last1)中的it1，满足 *it1 != *(_First2 + (it1 - _First1)), 返回pair<it1, _First2 + (it1 - _First1)>，如果找不到则返回pair<_Last1, _First2 + (_Last1 - _First1)>。

• mismatch(2)

template<class _InIt1, class _InIt2, class _Pr> inline pair<_InIt1, _InIt2>
mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _Pr _Pred)

在区间[First1，_Last1)中的it1，满足 _Pred(*it1 ,*(_First2 + (it1 - _First1)))==false, 返回pair<it1, _First2 + (it1 - _First1)>，如果找不到则返回pair<_Last1, _First2 + (_Last1 - _First1)>。

• equal(1)

template<class _InIt1, class _InIt2> inline 
bool equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2)

在区间[First1，_Last1)中满足*it1 == *(_First2 + (it1 - _First1))则返回true，否则返回false。

• equal(2)

template<class _InIt1, class _InIt2, class _Pr> inline 
bool equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _Pr _Pred)

在区间[First1，_Last1)中满足_Pred(*it1, *(_First2 + (it1 - _First1)))==true,则返回true，否则返回false。

• search(1)

template<class _FwdIt1, class _FwdIt2> inline
_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2)

在区间[First1，_Last1)中的it1，对于每一个在区间[First2，_Last2)中的it2，满足*(it1 + (it2 - _First2)) == *it2; 则返回it1，否在返回_Last1。

• search(2)

template<class _FwdIt1, class _FwdIt2, class _Pr> inline
_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)

在区间[First1，_Last1)中的it1，对于每一个在区间[First2，_Last2)中的it2，满足_Pred(*(it1 + (it2 - _First2)), *it2) == true; 则返回it1，否在返回_Last1。