std :: multimap ottenendo due intervalli

Sto usando un C++ std::multimap e devo eseguire il ciclo su due chiavi diverse. Esiste un modo efficace per fare questo oltre alla creazione di due gamme e il loop su questi intervalli separatamente?std :: multimap ottenendo due intervalli

questo è il modo sto facendo ora:

std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range; 
std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range2; 

// get the range of String key 
range = multimap.equal_range(key1); 
range2 = multimap.equal_range(key2); 

for (std::multimap<String, Object*>::iterator it = range.first; it != range.second; ++it) 
{ 
    ... 
} 
for (std::multimap<String, Object*>::iterator it2 = range2.first; it2 != range2.second; ++it2) 
{ 
    ... 
}

fonte

2011-09-07 Kaiser Wilhelm

perché pensi che non sia efficiente? –

Questa è la mia prima volta che uso multimap, quindi non ho molta familiarità con loro. Farò molto lavoro in questi loop e mi chiedevo se ci fosse un'altra operazione in cui potresti ottenere due intervalli allo stesso tempo o qualcosa del genere. –

Puoi dare un esempio di chiavi in cui i tasti si sovrappongono, ma non sono uguali tra loro? Forse il mio cervello è inzuppato, ma sembra che un semplice controllo di uguaglianza sui tasti lo farebbe. Ha più senso per me se tu avessi limiti inferiori e superiori separati per ogni query. –

Il codice si è iniziato con la più semplice.

Se desideri davvero eseguire l'iterazione su due intervalli nello stesso ciclo, puoi creare un iteratore personalizzato che richiede due intervalli di iteratore, itera il primo fino a quando non viene eseguito, quindi passa al secondo. Probabilmente è più un problema che ne vale la pena, in quanto è necessario implementare tutti i membri iteratori.

Modifica: Ero sopraffatto da questo; è facile modificare i due loop in uno solo.

for (std::multimap<String, Object*>::iterator it = range.first; it != range2.second; ++it) 
{ 
    if (it == range.second) 
    { 
     it = range2.first; 
     if (it == range2.second) 
      break; 
    } 
    ... 
}

fonte

2011-09-07 15:27:06

Ho pensato anche a questo. Tuttavia, queste due chiavi devono essere l'una accanto all'altra perché funzioni? Ad esempio, se ho 3 chiavi e voglio passare in rassegna il 1 ° e il 3 ° non includerò il 2 ° con loro? O quelli se le affermazioni lo risolvono? –

@Kaiser, le istruzioni 'if' gestiscono la transizione dal primo al secondo. Possono anche essere fuori uso. L'unica cosa che * non possono * fare è intersecare; se 'range2' include' range.second' allora otterrai un ciclo infinito. –

Ah, capisco. Il mio range2 è statico e range1 sarà sempre diverso. Non dovrebbero mai intersecare correttamente? Poiché multimap lo ordina al momento dell'inserimento? –

Boost fa questo, ovviamente. Utilizzando Boost.Range e la sua funzione join otterrai ciò che desideri. Vedi Boost Range Library: Traversing Two Ranges Sequentially per maggiori dettagli.

fonte

2011-09-07 15:29:56

Grazie, Boost sembra davvero potente. Sfortunatamente, la mia azienda è vecchia scuola e odia le cose nuove ... Immagino che dovranno accontentarsi dell'inefficienza –

questa volta non si tratta di efficienza, ma di convenienza –

Se si ha accesso a C++ - 11 (Visual Studio 10+, gcc-4.5 +) e il permesso di usarlo auto è un vero gioiello:

// get the range of String key 
auto range = multimap.equal_range(key1); 
auto range2 = multimap.equal_range(key2); 

for (auto it = range.first; it != range.second; ++it) 
{ 
    ... 
} 
for (auto it2 = range2.first; it2 != range2.second; ++it2) 
{ 
    ... 
}

In ogni caso, vorrei solo testare le chiavi e fai solo il secondo ciclo se key2! = key1. Controllare gli iteratori ogni volta in un ciclo ha un costo.

Una std :: set_difference del primo intervallo dal secondo potrebbe semplificare il codice. Forse std :: set_union i due intervalli e inserisci attraverso back_inserter in un set in modo da ottenere solo una copia?

Alcuni esperimenti potrebbero essere in ordine. Non dimenticare di mettere la tua prima ipotesi nel mix. Potrebbe sorprenderti stando bene in termini di velocità. A meno che gli intervalli siano in genere molto lunghi e/o l'operazione di loop sia costosa, potrebbe non valere la pena di una contabilità extra.

fonte

2011-09-07 19:38:57 emsr

std :: multimap ottenendo due intervalli

risposta

Problemi correlati