c++ - 寻找提供随机访问和 "sequential"访问的数据结构

Question

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

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

• 假设有 n 种类型的元素(例如 n = 1000000)，并且每种类型的元素都有固定数量(例如 0 或 10)

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

• 现在，我有一个迭代所有现有项目的算法。要获取这些项，在所有项均为 0 时遍历整个数组非常浪费，除了 Array[99999] 和 Array[999999]。

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

插入(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 相应元素的指针，因此我不必搜索整个列表。

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

Answer 1

鉴于以下要求:

• 随机访问
• 快速查找
• 快速插入
• 快速移除
• 避免浪费空间

那么你可能想要一个叫做 sparse array 的东西. 稀疏数组不是标准库的一部分，因此您必须使用 std::map 来模拟您自己的数组或 std::unordered_map .在稀疏数组中，只有非零元素占据集合中的空间。

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

如果您绝对必须同时拥有 O(1) 查找和有序迭代，那么您可以将 map 组合起来和 ordered_map并使它们保持同步。到那时，您将要考虑使用 Boost.MultiIndex .

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

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<size_t, int> map_;
};

在这样一个稀疏 vector 类中，你可以重载operator[]如果您希望允许类似 sparseVec[42] = 123 的内容.

线性代数库，例如 Eigen或 Boost.uBlas ，已经提供了稀疏 vector 和稀疏矩阵的模板。