符合 STL 标准的排序向量

Martin Holzherr

4.82/5 (9投票s)

2002年11月21日

7分钟阅读

151467

1173

一个模板容器，它使用向量实现集合/多重集合功能

下载源文件 - 7 Kb

引言

sorted_vector 将 std::vector 适配到 std::set/std::multiset 所需的接口，从而在一个容器中提供集合/多重集合和向量功能（随机访问）。

测试表明，sorted_vector 的元素检索（查找）速度比 std::set/std::multiset 快 2 倍（在大多数机器上）。缺点是 sorted_vector 的插入成员函数性能较差，因为它会将元素插入到排序向量的中间某个位置，以保持排序顺序。通过使用 sorted_vector 的低级接口，可以通过一系列 push_back 插入一堆对象，然后调用成员函数 sort 来恢复排序顺序，从而解决此性能瓶颈。

如果需要存储许多小元素，则应优先使用 sorted_vector 而不是 std::set/std::multiset。大多数 STL 实现都使用平衡树的变体来实现集合和多重集合，这会带来每个元素 3 个指针的存储开销。使用 std::set/std::multiset 而不是 sorted_vector 的最重要原因是需要在插入更多元素时保留指向集合/多重集合的迭代器。这些迭代器在集合/多重集合的情况下仍然有效，但在 sorted_vector 容器的情况下会失效。

命名空间

sorted_vector 位于命名空间 codeproject 中。

基本用法

下表显示了 sorted_vector 和 set/multiset 的相应声明。

STL 概念	标准库	sorted_vector
set	`set<Key,Pred>`	`sorted_vector<Key,true,Pred>`
multiset	`mutliset<Key,Pred>`	`sorted_vector<Key,Pred>`

（sorted_vector<Key,Pred,true> 表示 sorted_vector<Key,Pred,bNoDuplicates=true>）

各种 set/multiset insert 和 erase 成员函数以及 set/multiset 函数 count, lower_bound,upper_bound, equal_range 都是 sorted_vector 接口的一部分，并且其行为与它们的 set/multiset 对应函数相同。以下代码片段显示了使用 sorted_vector 来保存两个 std::vector 内容的集合交集。

#pragma warning(disable:4786)
#include "sorted_vector.h"
size_t             //build intersection using set interface of sorted_vector
BuildIntersection(  const std::vector<int>& v0,const std::vector<int>& v1,
                    codeproject::sorted_vector<int,true>& svecIntersection)
{		
    codeproject::sorted_vector<int,true> svec(v0.begin(),v0.end());
    for(int i=0;i<v1.size();i++){
        if( svec.find(v1[i])!=svec.end() ){
            svecIntersection.insert(v1[i]);
        }
    }
    return svecIntersection.size();
}

代码示例展示了 find 和 insert 成员函数的使用。如果您将 codeproject::sorted_vector<int,true> 替换为 std::set<int>，您将获得完全相同的结果。这段代码可以通过将循环中的 insert 调用替换为对基本容器（一个向量）的 push_back 调用，然后在循环结束时调用成员函数 sort 来优化速度。

#pragma warning(disable:4786)
#include "sorted_vector.h"
size_t             //same as previous example, optimized insertions 
BuildIntersection1(  const std::vector<int>& v0,const std::vector<int>& v1,
                    codeproject::sorted_vector<int,true>& svecIntersection)
{		
    codeproject::sorted_vector<int,true> svec(v0.begin(),v0.end());
    codeproject::sorted_vector<int,true>::Cont& vInterSect 
        = svecIntersection.get_container();
    for(int i=0;i<v1.size();i++){
        if( svec.find(v1[i])!=svec.end() ){
            vInterSect.push_back(v1[i]);
        }
    }
    svecIntersection.sort();
    return svecIntersection.size();
}

sorted_vector 接口

成员	来自	描述
`Cont`	sorted_vector	容器类型，用于存储受控序列的容器类型。
`value_type`	向量	存储在集合中的对象 T 的类型。
`key_type`	set/multiset	与 value_type 关联的键类型。
`key_compare`	set/multiset	用于比较两个键以进行排序的函数对象。
`value_compare`	set/multiset	用于比较两个值以进行排序的函数对象。
`pointer`	向量	指向 T 的指针。
`reference`	向量	T 的引用
`const_reference`	向量	T 的 const 引用
`size_type`	向量	一个无符号整数类型。
`difference_type`	向量	一个有符号整数类型。
`iterator`	向量	用于遍历向量的随机访问迭代器。
`const_iterator`	向量	用于遍历向量的随机访问 const 迭代器
`reverse_iterator`	向量	用于反向遍历向量的随机访问迭代器。
`const_reverse_iterator`	向量	用于反向遍历向量的随机访问 const 迭代器。
`iterator begin() const`	向量	返回指向 sorted_vector 开头的迭代器。
`iterator end() const`	向量	返回指向 sorted_vector 结尾的迭代器。
`reverse_iterator rbegin() const`	向量	返回指向反转 sorted_vector 开头的 reverse_iterator
`reverse_iterator rend() const`	向量	返回指向反转 sorted_vector 结尾的 reverse_iterator。
`size_type size() const`	向量	返回 sorted_vector 的大小。
`size_type max_size() const`	向量	返回 sorted_vector 的最大可能大小。
`bool empty() const`	向量	如果 sorted_vec 的大小为 0，则为 true。
`key_compare key_comp() const`	set/multiset	返回 sorted_vector 使用的 key_compare 对象。
`value_compare value_comp() const`	set/multiset	返回 sorted_vector 使用的 value_compare 对象。
`sorted_vector()`	set/multiset	创建一个空的 sorted_vector。
`sorted_vector(const key_compare& comp)`	set/multiset	创建一个空的 sorted_vector，使用 comp 作为 key_compare 对象。
VC++7.0: `template <class InputIterator> sorted_vector(InputIterator f, InputIterator l)` VC++6.0: `sorted_vector(const_iterator f, const_iterator l)`	set/multiset	创建一个带有范围副本的 sorted_vector。
VC++7.0: `template <class InputIterator> sorted_vector(InputIterator f, InputIterator l,const key_compare& comp)` VC++6.0: `sorted_vector(const_iterator f, const_iterator l,const key_compare& comp)`	set/multiset	创建一个带有范围副本的 sorted_vector，使用 comp 作为 key_compare 对象。
`sorted_vector(const sorted_vector&)`	set/multiset	复制构造函数。
`sorted_vector& operator=(const sorted_vector&)`	set/multiset	赋值运算符（赋值其他 sorted_vector）
`sorted_vector& operator=(const Cont&)`	sorted_vector	赋值运算符（赋值其他 vector<T>）
`void swap(sorted_vector&)`	set/multiset	交换两个 sorted_vector 的内容
`pair<iterator, bool>insert(const value_type& x)`	set/multiset	将 x 插入到 sorted_vector 中。
`iterator insert(iterator pos, const value_type& x)`	set/multiset	将 x 插入到 sorted_vector 中，pos 用作插入位置的提示。
VC++7.0: `template <class InputIterator> void insert(InputIterator f, InputIterator l)` VC++6.0: `void insert(const_iterator first f, const_iterator l)`	set/multiset	将一个范围插入到 sorted_vector 中。
`void erase(iterator pos)`	向量	擦除 pos 指向的元素。
`size_type erase(const key_type& k)`	set/multiset	擦除键为 k 的元素。
`void erase(iterator first, iterator last)`	向量	擦除一个范围内的所有元素。
`void clear()`	向量	擦除所有元素。
`iterator find(const key_type& k) const`	set/multiset	查找键为 k 的元素。
`size_type count(const key_type& k) const`	set/multiset	计算键为 k 的元素数量。
`iterator lower_bound(const key_type& k) const`	set/multiset	查找键不小于 k 的第一个元素。
`iterator upper_bound(const key_type& k) const`	set/multiset	查找键大于 k 的第一个元素。
`pair<iterator, iterator> equal_range(const key_type& k) const`	set/multiset	查找包含所有键为 k 的元素的范围。
`bool operator==(const sorted_vector&,const sorted_vector&)`	向量	测试两个 sorted_vector 是否相等。这是一个全局函数，而不是成员函数。还有一个运算符 !=
`bool operator<(const sorted_vector&, const sorted_vector&)`	向量	字典序比较。这是一个全局函数，而不是成员函数。还有运算符 <= >= 和 >
`Cont& get_container()`	sorted_vector	返回对用于存储受控序列的内部向量的引用
`void sort()`	sorted_vector	使用 key_compare 恢复排序顺序
`reference at(size_type i)`	sorted_vector	返回对 *(begin()+i) 处元素的引用，并进行范围检查
`const_reference at(size_type i) const`	sorted_vector	返回对 *(begin()+i) 处元素的引用，并进行范围检查
`const_reference operator[](size_type i) const`	sorted_vector	返回对 *(begin()+i) 处元素的引用
`reference operator[](size_type i)`	sorted_vector	返回对 *(begin()+i) 处元素的引用
`const_reference front() const`	sorted_vector	返回对第一个元素的引用
`reference front()`	sorted_vector	返回对第一个元素的引用
`reference back()`	sorted_vector	返回对最后一个元素的引用
`const_reference back() const`	sorted_vector	返回对最后一个元素的引用
`void pop_back()`	sorted_vector	从 sorted_vector 中删除最后一个元素

关注点

与 Alexander Stepanov（STL 的发明者）在 http://www.stlport.org/resources/StepanovUSA.html 的一次采访中，他提出将排序容器实现为 std::container 的适配器，这给我带来了这项工作的想法。令我真正惊讶的是 sorted_vector 与 set/multiset 相比出乎意料的良好性能。我的测试结果表明，std::set/std::multiset 相对于排序向量只有一个（重要的）优点，即迭代器在 set/multiset 中保持有效，即使添加了更多元素。

实现工作本身很简单，不需要任何高级 C++/STL 特性。可以总结如下：sorted_vector 的大多数成员函数都将调用转发给 vec_ 数据成员，它是一个 std::vector。用于插入/擦除和定位元素的 set/multiset 特定函数主要使用 STL 算法来处理 vec_ 数据成员中存在的排序序列。由成员函数 get_container()（返回对 vec_ 数据成员的引用）以及 sort 和 stable_sort（恢复排序顺序）组成的低级接口对于提高插入性能是必需的（通过允许暂时违反排序顺序）。只有一个函数出乎意料地难以实现：函数 unique，在 set 的情况下必须在 sort 和 stable_sort 之后调用。此函数是 STL 的一部分，需要一个谓词作为第三个参数。如果传入的元素相等，则此谓词必须返回 true。但是 sorted_vector 类只能访问评估 < 关系的谓词。理论上，应该可以将评估 < 关系的谓词转换为评估 == 的另一个谓词，但在实践中，这只有在 < 谓词作为派生自 std::binary_function 的对象实现时才有可能。最终，我因此不得不自己实现 unique。

历史

1.0：2002 年 11 月 19 日；首次发布。
1.1：2002 年 11 月 28 日；文档和代码更新
- 将命名空间从 std 更改为 codeproject
- 在 VC++7.0 的情况下支持成员模板，用于从迭代器范围构造/插入