如何找到地图的中间元素？STL

Question

你好，我遇到了STL库/C++中Map概念的困惑。

int arr[] = {10,15,14,13,17,15,16,12,18,10,29,24,35,36};
int n = sizeof arr / sizeof *arr;

map<int, bool> bst;
map<int, bool>::iterator it;
vector<int> median_output;

const int k = 5;
for (int i = 0; i < k; ++i) {
    bst.insert(make_pair(arr[i], true));
}

for (it = bst.begin(); it != bst.end(); it++) {
    cout << (*it).first << " ";
}

现在当我打印这张地图时，它按排序顺序打印出来。 现在有没有最简单的方法找到这张地图的中间部分......需要找到一个更大问题的中位数......因此尝试实现平衡二叉搜索树。

- AGeek

---

一棵增强型二叉搜索树支持 O(log n) 的 k-th 元素查询。但是 STL 实现默认情况下并不支持，而且（我猜）也不可能使用现有的 STL 树代码来实现。你必须编写自己的平衡二叉搜索树来处理这种类型的查询。 - Yin Zhu

你真的需要一个映射表吗，还是只是想找到一个序列的中位数？ - juanchopanza

+1。非常好的问题。我想补充一点，需要一个O(log n)的解决方案。 - Alexey Malistov

Answer 1

map 是一种平衡搜索树。要找到它的中间节点，需要先确定它的大小，然后从 begin() 开始迭代一半的大小，即可找到中间节点。可以参考以下示例代码：

for (it = bst.begin(), int middle = 0; middle < bst.size()/2; it++, middle++) {
    cout << (*it).first << " ";
}

// now after the loop it is the median.

如果你使用map来排序的话，我认为这是过度的。你可以用数组（或vector）更有效地完成此操作，然后找到中间位置也将变得轻而易举。map用于按键访问数据，而不仅仅是排序。

- littleadv

---

我完全不明白为什么你要保留地图进行排序，而且感觉需要迭代，而不是只说 std::advance(bst.begin(), bst.size()/2)。 - sehe

我保留了这个映射表，因为问题就是关于它的。至于std::advance - 它提供的唯一好处就是隐藏循环（从而使代码更加“美观”和更安全，免受各种错误的影响），但重点是展示这里所做的事情。 - littleadv

@littleadv - 是的，可能需要，也可能不需要。我认为OP问的是是否有简单易行的方法。 - Alexey Malistov

@AGeek - 使用advance和迭代之间没有功能上的区别 - 它们完全相同，只是如果你使用迭代 - 你需要编写自己的代码，而advance是一个预先构建的模板。我在示例中使用了你自己代码的片段，所以你可以看到循环，@Michael在下面编写了一个从头开始使用advance的示例，但它们是相同的。关于反转 - 我不确定我理解你的意思... - littleadv

@Alexey - 如果你有一个在答案中尚未提到的想法 - 随时添加即可。 - littleadv

Answer 2

使用所示代码时，您正在滥用地图以对键进行排序。

您可以获得更高的性能，避免完全排序和复制：

   const int len = 14;
   const int a[len] = {10,15,14,13,17,15,16,12,18,10,29,24,35,36};

   std::nth_element( a, a+len/2, a+len );
   std::cout << "Median: " << a[len/2] << std::endl;

如果您喜欢使用STL容器，您的代码将如下所示（假设容器具有随机访问迭代器）：

   std::vector<int> v( a, a+len );
   std::nth_element( v.begin(), v.begin()+len/2,v.end() );
   std::cout << "Median: " << v[len/2] << std::endl;

- sehe

---

使用std::nth_element和std::sort同时使用有点浪费（而且容易混淆）。我建议你只使用其中之一。 - juanchopanza

如果map除了对序列进行排序之外没有其他原因，那么这就是最好的答案。实际上，甚至不需要使用向量 - nth_element()可以直接在数组上工作（如果它被保留为非常量）：nth_element(arr，arr + len/2，arr + len)。 - Michael Burr

@sehe 好的，我理解了你的观点。但是也许你可以在回答的文字中解释一下？目前你只提到“完整排序和复制”。这可能会让问题发起人感到困惑... - juanchopanza

稍微调整了一下答案，展示了更多细微差别，这是原帖没有问到的 :) - sehe

@sehe：nth_element()无法在std:list上工作，因为它需要随机访问迭代器。 - Michael Burr

@Michael：啊...我的错。我过于笼统了。 - sehe

Answer 3

std::map可能不是定位中位数的最佳容器。但这个方法相当简单：

it = bst.begin();
advance( it, bst.size() / 2);
cout << endl << "median: " << it->first << endl;

- Michael Burr

---

在advance（预处理）中涉及了什么时间复杂度？ - AGeek

advance() 在 std::map 上的时间复杂度为 O(N)。 - Michael Burr

Answer 4

std::maps无法一次性给出中位数。如果您想要中位数，您需要使用这个算法。

- Manoj R

---

从链接页面中：CAVEAT EMPTOR（即买方自负）[...]更好的地方是去别处找（我太懒了，找不到正确的参考资料，好吧？）...（原文如此） - sehe

你引用的算法是std::partial_sort的简化版。如果元素是在一个数组里，类似这样的std::partial_sort(v.begin(), v.begin() + v.size() / 2 + 1, v.end())会将中位数放在v.begin() + v.size() / 2。 - James Kanze

顺便说一下，你将会接近重新实现 std::nth_element。IYAM - sehe