为什么我不能std::partition这个std::unordered_map？

Question

这无法构建，我不明白编译错误。

#include <unordered_map>
#include <algorithm>

int main()
{
    std::unordered_map<int, size_t> occurences = { { 10, 2 }, { 20, 5 }, { 30, 0 }, { 40, 5 }, { 50, 0 }, { 100, 9 } };

    auto newEnd = std::partition(occurences.begin(), occurences.end(), [](const std::pair<int, size_t> &p)
        {
        return p.second == 0;
        });

    return 0;
}

g++ 报错如下。 VS2013就更神秘了

/usr/local/include/c++/6.3.0/bits/stl_pair.h: In instantiation of 'void std::pair<_T1, _T2>::swap(std::pair<_T1, _T2>&) [with _T1 = const int; _T2 = long unsigned int]': /usr/local/include/c++/6.3.0/bits/stl_pair.h:473:7: required from 'void std::swap(std::pair<_T1, _T2>&, std::pair<_T1, _T2>&) [with _T1 = const int; _T2 = long unsigned int]' /usr/local/include/c++/6.3.0/bits/stl_algobase.h:148:11: required from 'void std::iter_swap(_ForwardIterator1, _ForwardIterator2) [with _ForwardIterator1 = std::__detail::_Node_iterator, false, false>; _ForwardIterator2 = std::__detail::_Node_iterator, false, false>]' /usr/local/include/c++/6.3.0/bits/stl_algo.h:1500:20: required from '_ForwardIterator std::__partition(_ForwardIterator, _ForwardIterator, _Predicate, std::forward_iterator_tag) [with _ForwardIterator = std::__detail::_Node_iterator, false, false>; _Predicate = main()::&)>]' /usr/local/include/c++/6.3.0/bits/stl_algo.h:4524:30: required from '_BIter std::partition(_BIter, _BIter, _Predicate) [with _BIter = std::__detail::_Node_iterator, false, false>; _Predicate = main()::&)>]' main.cpp:12:4: required from here /usr/local/include/c++/6.3.0/bits/stl_pair.h:416:6: error: no matching function for call to 'swap(const int&, const int&)' swap(first, __p.first);

See it live on Coliru here

据我所知，这张地图符合 cppreference.com 中列出的 std::partition 类型要求，所以我很困惑。我的问题是为什么它不构建？

Answer 1

std::partition 对提供的容器中的元素重新排序，但是您不能对 std::map 的元素重新排序 - 它具有预定义的 fixed 顺序它的元素。该标准保证在迭代地图的元素时，您将始终以递增顺序迭代它们。

正如您在标题中提到的 unordered_map 我还要提到的是，与 map 不同，它不保证其元素的顺序，但重新排序其元素也是不可能的。毕竟 unordered_map 是 无序的 所以它永远不会保证你迭代它的元素的顺序。

Answer 2

报错是因为amap和unordered_map的元素是std::pair<const Key, value>不是std::pair<Key, Value>,所以可以不要使用像 std::partition 这样的算法重新排序它们，因为 const Key 无法修改：

error: no matching function for call to 'swap(const int&, const int&)'

只有地图本身可以对元素重新排序，并且它会按需要的顺序排列元素以保持其不变性。如果您重新排序它们，您将破坏地图的内部数据结构。

Answer 3

所有其他答案都是正确的。 unordered_map 不允许您以与 map 相同的方式重新排列其元素，仅此而已。然而，还有一个更深层次的概念问题。

当您创建 unordered_map 时，您决定顺序（任何顺序）无关紧要，突然您希望顺序重要（分区操作）。如果你想要一个范围，这肯定需要你的元素在不同的容器中，其中分区顺序很重要。

您始终可以将分区转换为比较标准，在这种情况下，您可以使用 multiset 来存储新版本的集合。

#include<algorithm>
#include<unordered_map>
#include<set>

using std::cout; using std::cerr;

int main(){

    std::unordered_map<int, size_t> occurences = { { 10, 2 }, { 20, 5 }, { 30, 0 }, { 40, 5 }, { 50, 0 }, { 100, 9 } };

    auto null_second_pred = [](auto& e){return e.second == 0;};
    auto null_second_comp = [&](auto& a, auto& b){return null_second_pred(a) and (not null_second_pred(b));};
    std::multiset<std::pair<int, size_t>, decltype(null_second_comp)> 
        occurences2(occurences.begin(), occurences.end(), null_second_comp);

    assert( std::is_partitioned(occurences2.begin(), occurences2.end(), null_second_pred) );

}

（从概念上讲，您可以将元素移动到新容器中，但在这种情况下不会有什么不同。另外你不能使用 multimap 因为你会丢失信息并且排序标准不能在对的第二部分。）

为什么我不能std::partition这个std::unordered_map？

Why can I not std::partition this std::unordered_map?

c++

stl-algorithm