0

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?

Improve this question
4
  • 2
    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. Commented Feb 24, 2017 at 8:28
  • @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. Commented Feb 24, 2017 at 8:36
  • 1
    You missed the ValueSwappable requirement on the iterators. Commented Feb 24, 2017 at 8:37
  • @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>. Commented Feb 24, 2017 at 8:41

3 Answers 3

Reset to default
7

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thank you for the edit to the question, it was a typo.
5

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.

Improve this answer

Comments

1

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 (partition 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.)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.