Pourquoi ne puis-je pas std :: partitionner std :: unordered_map?

Question

Cela ne se construit pas et je ne comprends pas l'erreur de compilation.

#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 ++ se plaint comme suit. VS2013 est encore plus énigmatique.

/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

Pour autant que je peux dire cette carte répond aux exigences de std :: type de partition figurant sur cppreference.com donc je suis perplexe. Ma question est pourquoi ne construit-elle pas?

Answer 1

L'erreur est parce que les éléments d'un map et unordered_map sont std::pair<const Key, value>passtd::pair<Key, Value>, de sorte que vous ne pouvez pas réordonner les utiliser comme un algorithme std::partition car le const Key ne peut pas être modifié:

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

Seule la carte elle-même peut réorganiser les éléments, et les conserve dans l'ordre dans lequel ils se trouvent afin de conserver leurs invariants. Si vous les réorganisez, vous allez corrompre les structures de données internes de la carte.

Answer 2

std::partition réorganise les éléments dans le récipient fourni, mais vous ne pouvez pas réorganiser les éléments d'un std::map - il a un ordre fixe prédéfini de ses éléments. La norme garantit que lorsque vous itérez sur les éléments d'une carte, vous les itérez toujours dans l'ordre croissant. Comme vous mentionnez unordered_map dans le titre je mentionnerai également que contrairement à map il ne donne pas de garanties sur l'ordre de ses éléments mais le réordonnancement de ses éléments n'est pas non plus possible. Après tout unordered_map est non ordonné donc il ne donnera aucune garantie sur l'ordre dans lequel vous itérez sur ses éléments.