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

This doesn't build and I don't understand the compilation error.

#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++ complains as follows. VS2013 is even more cryptic.

/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

As far as I can tell this map meets the std::partition type requirements listed on cppreference.com so I'm stumped. My question is why doesn't it build?

The error is because the elements of a map and unordered_map are std::pair<const Key, value> not std::pair<Key, Value>, so you can't re-order them using an algorithm like std::partition because the const Key can't be modified:

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

Only the map itself can re-order the elements, and it keeps them in whatever order it needs to in order to maintain its invariants. If you re-order them you will corrupt the map's internal data structures.

can be used to iterate through a single bucket but not across buckets: const_local_iterator: An iterator type whose category, value, difference, pointer and reference types are the same as const_iterator. This iterator can be used to iterate through a single bucket but not across buckets: node_type (since C++17)

std::partition reorders the elements in the provided container, however you can not reorder the elements of a std::map - it has a predefined fixed order of its elements. The standard guarantees that when iterating over the elements of a map, you will always iterate them in increasing order.

As you mention unordered_map in the title I will also mention that unlike map it does not give guarantees about the order of its elements but reordering its elements is also not possible. After all unordered_map is unordered so it will never give any guarantee about the order in which you iterate over its elements.

Download Run Code. Output: {3 -> three} {1 -> one} {2 -> two} We can also pass a binary predicate with std::map which takes two values of the same type and defines ordering of map’s keys.

All other answers are correct. unordered_map doesn't let you rearrange its elements in the same way that map doesn't and that's it. However there is a deeper conceptual problem.

When you created the unordered_map you decided that the order (any order) wouldn't matter, and suddenly you want the order to matter (parition operation). If you want a range, this requires your elements in a different container for sure, one in which the partition order matters.

You can always convert the partition into a comparison criterion, in which case you can use a multiset to store a new version of your collection.

#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) );

}

(More conceptually you can move the elements into the new container but it won't make a difference in this case. Also you can't use multimap because you would loose information and the ordering criterion can't be on the second part of the pair.)

In this article we will discuss the different ways to iterate over an unordered_map. First lets create an unordered_map and then we will see the different ways to iterate over it.

Armed with this knowledge, we can insert lots of multiples of one of these primes to the map in order to get n 2 blow-up. Not all of the primes work though, due to the resizing policy of the map; in order for a prime to work, we need the map to actually resize to this prime at some point in its set of operations.

For searching an element, std::unordered_map gives the complexity O(1) in best case but O(n) in worst case (if hash implementation is not perfect). So, if your hash implementation is not good and you have millions and billions of data then go for std::map because it will give you guaranteed O(log N). When to choose unordered_map instead of map

Return value. Returns a pair consisting of an iterator to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place (true if insertion happened, false if it did not).

Comments
  • What do you want this to do? A std::map is always sorted. A std::unordered_map has no fixed notion of order. In either case, partitioning doesn't make sense.
  • @jtbandes The reason I want to do this, is that this is a minimal example where the actual code has a map as the appropriate container for other reasons. My usage here is one small part where I want the ints (indexes) that have zero occurrences. I can workaround by std::copy the contents into a vector.
  • You missed the ValueSwappable requirement on the iterators.
  • @molbdnilo No, what I missed is what Jonathon Wakely has answered below about the actul element type. std::pair<int, size_t> is value swappable but not std::pair<const int, size_t>.
  • Thank you for the edit to the question, it was a typo.