c++ - 维护一个与 std::map 平行的 std::vector

Question

最近，当我需要遍历 std::map 时，我通常从 map 构建一个 std::vector，因为访问元素的复杂性是(log N)(实际上，仅当我需要通过自定义键访问元素时)。

所以，我最终维护了一个 std::vector 只是为了迭代我的所有元素，(因为它的复杂度是常量 O(1))和一个 std::map 用于特定的检索(因为它的复杂度在迭代时是 O(log n))。

这是正确的方法吗，还是我应该只使用 std::map 而忘记 std::vector(你知道，对于这个具体案例)。

谢谢。

Answer 1

除非分析告诉您需要它，否则您应该忘记 vector。在 map 中迭代不是每个迭代器增量的 O(log₂N)...它只需要通过遍历当前元素的最小路径来找到下一个元素平衡二叉树...通常只遵循一两个链接，尽管从最后一个左侧节点移动到第一个右侧节点的最坏情况步骤需要 2*(log₂(N)-1) 移动，如果它只是使用通用方法。

为了形象化这一点，请考虑下面 map 中的节点 - 它们总是按排序顺序排列，这里我假设数据元素恰好是递增整数，因为我们可以轻松地使用它们的值引用节点:

                     8
                  /    \
                4        12
              /   \    /   \
             2    6    10   14
           /  \  / \  / \   / \
          1   3 5  7 9  11 13  15

当您遍历时，您的迭代器可能必须从根“8”开始并遍历左侧分支到“1”，但随后向上移动一个链接到 2，然后向下移动一个链接到“3” , 在不得不弹出几个指向“4”的链接并向下弹出几个指向“5”的链接之前。很明显 - 大多数时候它只是跟随 1 或 2 个链接，更长的路径越来越少:如果我们全部列出:

6 links: once/x1: 7-6-4-8-12-19-9
3 links:  8-1
2 links: x4: 3-2-4, 4-6-5, 11-10-12, 12-14-13
1 link: x8: 1-2, 2-3, 5-6, 6-7, 9-10, 10-11, 13-14, 14-15

总共是 8*1 + 2*4 + 3*1 + 6*1 = 25...遍历 25 个链接以迭代 15 个元素。

对于任意 N，该序列可以概括为:N/2 + 4N/8 + 6N/16 + 10N/32 + 12N/128 + 14N/256... 2iN/2ⁱ⁺¹....如果我们简化分数并除以 N，我们得到一个级数:

1/2, 1/2, 3/8, 1/4, 5/32, 3/32, 7/128, ...

有很多 proofs here它转换为 2N，即迭代器每次增量的平均链接数在 N 较大时收敛到 2，并且由于 2 是常数因子，我们仍然可以说递增迭代器是 O(1)。