寻找提供随机和"顺序"访问的数据结构

这是我经常遇到的编程问题,并且想知道是否存在数据结构,无论是在C++ STL中还是我自己实现的,都提供随机和顺序访问.

我可能需要这个的一个例子:

假设有n种类型的项目(例如,n = 1000000),并且每种类型的项目都有固定数量(例如,0或10)

我将这些项存储到一个数组中,其中数组索引表示项的类型,值表示该给定类型的项数是多少

现在,我有一个迭代所有现有项目的算法.为了获得这些项目,当所有条目都为0时迭代整个数组是非常浪费的,除了数组[99999]和数组[999999].

通常,我通过使用链表来解决这个问题,该链表保存了所有非零数组条目的索引.我以这种方式实现标准操作:

Insert(int t):

1)如果Array [t] == 0,LinkedList.push_back(t);

2)数组[t] ++;

删除(int t):

1)如果Array [t] == 1,从LinkedList中查找并删除t;

2)数组[t] - ;

如果我想要删除操作的O(1)复杂性,我使数组存储容器而不是整数.每个容器都包含一个整数和指向LinkedList各自元素的指针,因此我不必搜索列表.

我想知道是否有一个数据结构正式化/改进了这种方法,或者是否有一种更好的方法来完成这项工作.

鉴于以下要求:

随机访问

快速查找

快速插入

快速删除

避免浪费空间

那么你可能想要一种称为稀疏数组的东西.稀疏数组不是标准库的一部分,因此您必须使用std::map或者模拟自己的数组std::unordered_map.在稀疏数组中,只有非零元素占用集合中的空间.

一ordered_map将有O(1)查找,插入和移除,但不提供有序的迭代.A map通常会有较慢的操作,但会提供有序的迭代.当我说std::map速度较慢时,我过于简单化,因为它取决于元素的数量和使用模式(一个话题可能已经在另一个问题中讨论过了).

如果你必须绝对同时进行O(1)查找和有序迭代,那么你可以结合使用a map和ordered_map并保持它们同步.此时,您将需要考虑使用Boost.MultiIndex.

这是一个粗略的草图,展示了如何实现自己的稀疏矢量类:

class SparseVector
{
public:
    int get(size_t index) const
    {
        auto kv = map_.find(index);
        return (kv == map_.end()) ? 0 : kv->second;
    }

    void put(size_t index, int value)
    {
        if (value == 0)
            map_.erase(index);
        else
            map_.emplace(index, value);
    }

    // etc...

private:
    std::unordered_map map_;
};

线性代数库,例如Eigen或Boost.uBlas,已经为稀疏向量和矩阵提供了模板.