保持与std :: map平行的std :: vector

Question

最近,当我需要迭代std::map我通常std::vector从地图构建一个时,因为访问元素的复杂性是(log N)(实际上,只有当我需要通过自定义键访问元素时).

因此,我最终维护了一个std::vectorfor for for iterating我的所有元素,(因为它的复杂性是常数O(1))和一个std::map特定的检索(因为它的复杂性在迭代时是O(log n)).

这是一个正确的方法,或者我应该去std::map和忘记std::vector(你知道,对于这个特定情况).

谢谢.

Answer 1

你应该忘记,vector除非分析告诉你需要它.在每个迭代器增量中迭代a mapis not O(log ₂ N)...它只需要通过遍历平衡二叉树中当前元素的最小路径来找到下一个元素...这通常只跟随一个或两个链接虽然从最后一个左侧节点移动到第一个右侧节点的最坏情况步骤需要2*(log ₂(N)-1)个移动,如果它只是使用通用方法.

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

                     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 ^{i + 1} ....如果我们简化分数除以N得到一系列:

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

这里有很多证据表明它转换为2N,即迭代器每增量的平均链路数收敛到大N的2,而2是常数因子,我们仍然可以说迭代器的递增是O(1).