20.为含有指针的关联容器指定比较类型

问题实例

</br>
假设存在一个元素类型为string 的set，其内容如下：

set<string*> ssp; //ssp = “set of string ptrs”
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lemur"));
ssp.insert(new string("Penguin"));
//以为set内部元素已然按照字典序排序

我们试图去遍历并输出它：

for (auto i = ssp.cbegin();i != ssp.cend();++i)
    cout << *i << endl; //以为会获得按照字典序的string对象

但实际上输出的只是一堆地址，并不是string对象。
如果你使用的是算法而非显式循环：

copy(ssp.begin(), ssp.end(),ostream_iterator<string>(cout, "\n"));

你将更早地得到错误信息，上述代码无法编译，ssp内部存放的是string\而非string，所以和ostream_iterator的打印类型不匹配。这也从侧面反映了算法至少在正确性上确实优于循环。（Effective STL 43）
就算我们在显式循环中使用**i，最后的输出也会不尽人意，你会发现输出的字符串并没有像你想的那样按照首字母排序，而是按照string* 的大小进行排序。
原因在于set使用了默认的排序器，ssp的声明其实等价于

set<string*> ssp;
set<string*, less<string*> > ssp;

---

自定义比较类型

</br>
如果我们试图以指针所指向的对象为排序对象，那么比较器应该改为自定义的比较仿函数类，如下所示：

struct StringPtrLess:
    public binary_function<const string*, const string*, bool> {//该基类详见Effective STL 40
        bool operator()(const string *ps1, const string *ps2) const{
            return *ps1 < *ps2;
        }
};

此时，可以声明ssp为

typedef set<string*, StringPtrLess> StringPtrSet;
StringPtrSet ssp;//按照字典序排序内部指针指向对象的set

这个时候再使用显式循环即可正确完成任务。

如果你想使用算法输出string对象，那必须对一个元素执行解引用，写一个谓词或者lambda配合for_each算法即可：

//谓词版本
void print(const string *ps){
    cout << *ps << endl;
}
for_each(ssp.begin(), ssp.end(), print);
//lambda版本
for_each(ssp.begin(), ssp.end(),[](const string *ps){cout << *ps << endl;});

当然，你也可以自定义解引用仿函数类，然后配合transform与ostream_iterator：

struct Dereference {//传入T*，返回const T&
    template <typename T>
    const T& operator()(const T *ptr) const{
        return *ptr;
    }
};
transform(ssp.begin(), ssp.end(),ostream_iterator<string>(cout, "\n"),Dereference());

---

为何是比较类型而非比较函数

</br>
也许你会好奇为什么传递给set的永远是一个class而非某个函数，因此有人会试图直接使用函数作为参数声明set:

bool stringPtrLess(const string* ps1,const string* ps2){ 
    return *ps1 < *ps2; 
}
set<string*, stringPtrLess> ssp;//无法编译

原因在于set模板的三个参数均为class，而函数不需要类型。set不需要一个函数，它需要的是能在内部用实例化建立函数的一种类型。

---

通用解决方案

</br>
我们可以发现，在大多数情况下，比较类型只是解引用指针并比较所指向的对象。鉴于这种情况，我们完全可以定义一个通用仿函数模板：

struct DereferenceLess {
    template <typename PtrType>
    bool operator()(PtrType pT1,PtrType pT2) const {//这里采用了值传递，因为指针等内置类型值传递效率更高
        return *pT1 < *pT2;
    }
};

声明式如下：

set<string*, DereferenceLess> ssp;

---

总结

</br>
本节虽以指针为名，但实际上使用范围是内部元素表现为指针的容器：如元素是智能指针、迭代器等。在这些容器中务必自定义比较类型。