23.考虑用有序vector代替关联容器

Posted on | In

（我认为本节内容强调的是底层数据结构的选择）

各容器的查找速度

 
理论上，散列容器可以提供常数时间的查找。如果你仅仅需要对数时间的查找，和直觉相悖的是，有序vector性能可能会优于关联容器。

有序vector的优越性

为何有序vector在性能上优于关联容器

关联容器的底层数据结构是平衡搜索二叉树，其设计是综合了插入，删除，查找下的最优，但我们在实际应用中这三种操作并非像在测试条件那样随机执行。一般而言，都是某一段时间都在插入，另一段时间都是在查找等等…在这种情况下，有序vector可能会比关联容器在时间和空间上性能更好。

具体优越点

  1. 空间问题
  2. 引用局部性问题

问题实例

空间优越性

假设关联容器元素类型为Widget，在底层数据结构平衡二叉树中不仅仅存着一个Widget，更是存着左子、右子、父节点这三个指针。
vector不需要存储指针，并且可以通过swap技术可以消除多余的内存需求。空间占用比关联容器少了许多。

引用局部性问题

假设我们有足够多数据结构，那么它们在存储时会分成多个内存页面，vector所占用的页面显然要少于关联容器（空间优越性），但这并不是最关键的。如果STL没有改进关联容器的引用局部性，二叉树节点会分散在各个页面，直接导致了更多的缺页中断。vector则不会如此，因为其内存连续，二分查找时不会发生太多的页面错误。

vector的缺陷

上述所说的查找高效性仅限于vector处于有序状态。此外，对于动态操作，是vector的花销惊人（可能还伴随着扩容），所以只有当查找操作几乎不与插入删除混用时，使用有序vector代替关联容器才有意义。

有序vector与关联容器的替换

替换set

用vector替换set十分自然，仅有在针对mutiset时记住排序应该使用stable_sort.关于具体的查找算法选择，详见Effective STL 45；

替换map

元素类型

当我们试图用vector代替map或者mutimap时，需要注意的是，vector内部必须容纳pair对象。
当我们声明map<K,V>时，map内部其实存储的是pair<const K,V>,由于对vector排序时其值会通过赋值来移动，所以vector模拟map时内部只能是pair<K,V>.

排序函数

map在排序时仅仅使用key来作为排序的依据，那么vector中的pair也一样。这导致我们必须自定义一个pair的比较函数，因为默认版本根据pair的两个组件来排序。（我还没排序过pair)

查找函数

用来排序的比较函数将作用于两个pair对象，但是查找只用到了key值，所以必须给用于查找的比较函数一个key类型的对象和一个pair，关键在于我们并不了解到底是key还是pair作为第一个实参传递，所以需要用两个用于查找的比较函数：一个key值先传递，另一个pair先传递。

比较类型实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef pair<string, int> Data; 
class DataCompare {// 用于比较的类
public:
    bool operator()(const Data& lhs,const Data& rhs) const{//用于排序的比较函数
        return keyLess(lhs.first, rhs.first);
    }
    //以下为基于查找的比较函数，因为无法确定是输入次序，因此构成重载
    bool operator()(const Data& Ihs, const Data::first_type& k) const {
        return keyLess(lhs.first, k);
    }
    bool operator()(const Data::first_type& k,const Data& rhs) const {
        return keyLess(k, rhs.first);
    }
private:
    //真正调用的比较函数
    bool keyLess(const Data::first_type& k1,const Data::first_type& k2) const{
        return k1 < k2;
    }
};

总结

 
只要数据结构的使用过程确实符合本章所述，并且没有误用比较函数设计，有序vector的效率几乎绝对优于关联容器。