寻找同时提供随机和“顺序”访问的数据结构

Question

这是我经常遇到的编程问题，想知道是在C ++ STL中还是在我可以实现的数据结构中，它提供了随机访问和顺序访问。

为什么我可能需要这个例子：

• [[说有n种类型的项目（例如，n = 1000000），每种类型的项目都有固定数量（例如0或10）
• 我将这些项目存储到一个数组中，其中数组索引代表该项目的类型，而值代表该给定类型的项目数]]] >>

• 现在，我有一个算法可以迭代所有现有项。要获得这些项，当所有条目均为0时，除了Array [99999]和Array [999999]之外，在整个数组上进行迭代非常浪费。

通常，我通过使用链接列表来解决此问题，该列表保存所有非零数组条目的索引。我以这种方式实施标准操作：

Insert（int t）：

1）如果Array [t] == 0，则LinkedList.push_back（t）;

2）数组[t] ++;

Delete（int t）：

1）如果Array [t] == 1，则从LinkedList中查找并删除t；

2）数组[t]-;

如果要删除操作的复杂度为O（1），则使数组存储容器而不是整数。每个容器包含一个整数和一个指向LinkedList各个元素的指针，因此我不必在列表中进行搜索。

[我很想知道是否有一个可以正式化/改进这种方法的数据结构，或者是否有更好的方法可以完全做到这一点。

这是我经常遇到的编程问题，想知道是在C ++ STL中还是在我可以实现的数据结构中，它同时提供随机和...

Answer 1

随机访问