具有快速数组访问功能的 STL 容器：map、set 和 list

• 下载源代码文件 - 11 Kb

引言

此源代码包含五个符合 STL 标准的容器类，名称如下：

index_list<T>
index_set<T,Cmp>
index_multiset<T,Cmp>
index_map<Key,T,Cmp>
index_multimap<Key,T,Cmp>

这些类中的每一个都实现了与其名称第二部分中的 STL 类相同的接口。 此外，每个类还实现了 vector<T> 类的 STL 接口，通过 operator[] 和 at() 提供快速数组访问。 T 是所包含类的类型。 Key 是配对关联容器的查找键的类型。 Cmp 是比较谓词，必须是具有类型为 T 的参数的二元谓词，用于 set，以及具有类型为 Key 的参数的二元谓词，用于 map。 如果您没有提供比较谓词，则默认使用 std::less<Arg>。

这些类都是从我从 Andreas Jager 那里借来的 AVL 树派生的（包含版权声明），并经过修改以允许索引访问。 每个树节点包含一个额外的长整数，用于保存其下方的子节点数量。 更新这些计数的算法不会增加任何原始树算法的复杂度。 由于接口在 STL 中有文档说明，因此我将仅提供以下复杂度分析。 我认为我已经涵盖了这些容器中最常用的函数，但某些函数可能未包含。 如果您希望添加另一个 STL 函数，请与我联系，我将很乐意更新源代码。

复杂度分析

index_list<T>

index_list 是一个序列，它结合了 array、deque 和 list 的接口。

以下是与其他序列容器的复杂度比较：

	数组	双端队列	列表	index_list
索引访问	1	1	(N)	lgN
插入/删除	N	N	1	1+
前部插入	(N)	1+	1	1+
后部插入	1+	1+	1	1+

它在大型集合 (N >> 1) 上效果最佳。

它还具有额外的函数 insert(const T&)，通常用于集合，它选择一个插入位置，该位置通过最少数量的旋转操作来保持树的平衡。

index_set<T,Cmp>
index_multiset<T,Cmp>
index_map<Key,T,Cmp>
index_multmap<Key,T,Cmp>

这些类实现了 set、multiset、map 和 multimap 的 STL 接口，以及索引访问 (operator[]、at())。 以下是与其他关联容器的复杂度比较：

	数组	列表	set	index_set/map 等。
索引访问	1	(N)	(N+)	lgN
插入/删除	N	1	1+	1+
搜索	lgN	N	lgN	lgN

尽情享用！

历史

2002 年 7 月 21 日 - 更新下载

2002 年 8 月 6 日 - 更新下载