C ++ STL: ricerca di mappe per iteratore su un'altra mappa

Question

Sto cercando di saltare attraverso alcuni cerchi per organizzare i dati in modo speciale. Sto includendo un pezzo di codice semplificato che dimostra il mio dolore.

Non posso usare boost. Sto usando l'ultima versione di g ++ in cygwin.

#include <iostream>
#include <map>

using namespace std;

int main () {

    map< int,int > genmap;
    map< int,int >::iterator genmapit;
    map< map<int,int>::iterator,int > itermap;

    // insert something into genmap
    genmap.insert (make_pair(1,500) );

    // find and return iterator.
    genmapit=genmap.find(1);

    // insert the iterator/int into itermap. Dies on each of the following 3 versions of this line.
    //itermap[genmapit] = 600; // crash
    //itermap.insert ( pair< map<int,int>::iterator,int >(genmapit,600) ); // crash
    itermap.insert ( make_pair(genmapit,600) ); // crash

    return 0;
}

Come puoi vedere, ho 1 semplice mappa, un iteratore per quella mappa e un'altra mappa che ha il primo argomento come iteratore per la prima mappa.

Da questo è chiaro: Perché non riesco a mettere un iteratore nella mappa? Che posso avere un iteratore come secondo argomento. Tuttavia, il modo sopra indicato fornisce questo:

$ make
g++    -c -o main.o main.cpp
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_function.h: In member fun
ction `bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp =
 std::_Rb_tree_iterator<std::pair<const int, int> >]':
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_tree.h:871:   instantiate
d from `std::pair<typename std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _All
oc>::iterator, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::i
nsert_unique(const _Val&) [with _Key = std::_Rb_tree_iterator<std::pair<const in
t, int> >, _Val = std::pair<const std::_Rb_tree_iterator<std::pair<const int, in
t> >, int>, _KeyOfValue = std::_Select1st<std::pair<const std::_Rb_tree_iterator
<std::pair<const int, int> >, int> >, _Compare = std::less<std::_Rb_tree_iterato
r<std::pair<const int, int> > >, _Alloc = std::allocator<std::pair<const std::_R
b_tree_iterator<std::pair<const int, int> >, int> >]'
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_map.h:360:   instantiated
 from `std::pair<typename std::_Rb_tree<_Key, std::pair<const _Key, _Tp>, std::_
Select1st<std::pair<const _Key, _Tp> >, _Compare, _Alloc>::iterator, bool> std::
map<_Key, _Tp, _Compare, _Alloc>::insert(const std::pair<const _Key, _Tp>&) [wit
h _Key = std::_Rb_tree_iterator<std::pair<const int, int> >, _Tp = int, _Compare
 = std::less<std::_Rb_tree_iterator<std::pair<const int, int> > >, _Alloc = std:
:allocator<std::pair<const std::_Rb_tree_iterator<std::pair<const int, int> >, i
nt> >]'
main.cpp:23:   instantiated from here
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_function.h:227: error: no
 match for 'operator<' in '__x < __y'
make: *** [main.o] Error 1

" istanziato da qui " non mi dice nulla e una ricerca web non mi fornisce informazioni al riguardo.

STL: map semplicemente non lo consente? Posso ricodificare la mia app per aggirare questo problema, ma sarà molto inefficiente e vorrei farlo funzionare. Esiste un altro tipo di puntatore che posso creare per un elemento della mappa che posso usare?

Grazie per il tuo tempo.

Answer 1

Non puoi farlo perché std::map gli iteratori non sono iteratori ad accesso casuale quindi non sono comparabili con <.

Invece, puoi usare i puntatori a value_type nella prima mappa come chiave della mappa.

Answer 2

Devi imparare a leggere i messaggi di errore. In particolare, guarda il messaggio che segue la lunga descrizione dove si è verificato l'errore:

  

/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_function.h:227: error: no match for 'operator<' in '__x < __y'

Gli iteratori di mappe non sono confrontabili con un operatore diverso da quello utilizzato dalla mappa per impostazione predefinita.

Suppongo che tu possa fornire una funzione di confronto che confronta le coppie indicate dall'iteratore, dal momento che gli stessi iteratori non possono essere facilmente confrontati in modo significativo.

struct CompareIterator
{
     template <class FirstIter, class SecondIter>
     bool operator()(FirstIter lhv, SecondIter rhv) const
     {
         return *lhv < *rhv;
     }
};

//usage with map:
map< map<int,int>::iterator,int, CompareIterator > itermap;

std::pair definisce operator<. Ho anche usato due tipi di iteratore, poiché potrebbe essere possibile che i tipi siano diversi (iterator e const_iterator)

Answer 3

map<Key, Value>

map iterator come elemento chiave in un altro operator < non è possibile perché Key prevede che map iterator sia definito per impostazione predefinita nella chiave. Se <=> (in questo caso <=>) non è definito, è necessario passare un functor come funzione predicata che fornisce il confronto di Key (map iterator).