Anzahl der Einträge zwischen zwei std :: multimap Iteratoren effizient zählen

Question

Ich möchte die Anzahl der Einträge zwischen zwei Iteratoren einer std::multimap in weniger als O (N) Zeit zählen. Gibt es Tricks oder clevere Möglichkeiten, dies zu tun?

Seit std::multimap bidirektionale Iteratoren hat, ist mein Verständnis, dass etwas wie std::distance dies in O (N) Zeit tun könnte.

Zusätzliche Details: Der Schlüssel multimap ist ein N-Tupel. Ich versuche die Anzahl der Einträge in der multimap zu finden, deren erstes Element des Schlüssels 0 ist. Die Optionen für das erste Element des Schlüssels sind 0 und 1, und die multimap verwendet eine strenge schwache Reihenfolge, in der das erste Element des Schlüssels ist immer das Wichtigste. h. alle Elemente mit 0 kommen vor allen Elementen mit 1.

Kontext: Die Iteratoren werden von equal_range zurückgegeben, die in logarithmischer Zeit läuft. Deklarativ möchte ich die Länge des Bereichs messen.

Vielen Dank.

Answer 1

Was Sie suchen genannte so wird heterogeneous comparison lookup, die in N3465 vorgeschlagen wurde.Es ermöglicht eine verschiedene, aber kompatible Vergleichsfunktion in der equal_range Mitgliedsfunktion, die verwendet wird, um die Key zu speichern. In Ihrem Fall wäre der Suchvergleichsoperator (erstes Tupelelement) anders als, aber konsistent mit dem tupellexikalischen Vergleich.

Leider wurde nur ein kleiner Teil dieses Papiers gemäß this Q&A in den Entwurf C++ 14 Standard aufgenommen. Der Autor des N3465-Papiers ist jedoch auch der Autor von Boost.MultiIndex, der this feature implementiert hat. Sie können emulate a std::multimap durch Befolgen der Boost.MultiIndex-Dokumentation.

Sobald Sie die verallgemeinerte equal_range Elementfunktion eines angepassten boost::multiindex_container verwendet haben, können Sie einfach std::distance() für die zurückgegebenen Iteratoren tun. Die Komplexität wäre logarithmisch in der Containergröße für den equal_range und linear in der Größe des zurückgegebenen Iteratorbereichs. Wenn Sie nicht an dem Ergebnis, sondern nur an der Zählung interessiert sind, gibt es auch eine verallgemeinerte count() Elementfunktion, die diese in derselben logarithmischen + linearen Zeit zurückgibt.

Answer 2

Sie möchten die std::distance-Methode aus der Iterator-Bibliothek verwenden. Die Referenz ist std::distance. Hier ist die Hauptreferenz: Iterator library.

Die Beschreibung lautet also ab 25. März 2014:

template< class InputIt > 
typename std::iterator_traits<InputIt>::difference_type 
    distance(InputIt first, InputIt last); 

Gibt die Anzahl der Elemente zwischen dem ersten und letzten.

Das Verhalten ist undefiniert, wenn last nicht von vornherein erreichbar ist, indem es (möglicherweise) wiederholt inkrementiert wird.

Parameter
erste - Iterator auf das erste Element zeigt
zuletzt - Iterator auf das letzte Element zeigt

Typ Anforderungen
- InputIt müssen den Anforderungen der InputIterator erfüllen. Der Betrieb ist effizienter wenn InputIt erfüllt zusätzlich die Anforderungen der RandomAccessIterator

Rückgabewert
Die Anzahl der Elemente zwischen dem ersten und letzten.

Komplexität
Linear.
Wenn jedoch InputIt zusätzlich die Anforderungen von RandomAccessIterator erfüllt, ist die Komplexität konstant.

Beachten Sie, dass sich die oben genannten Angaben ändern können. Die genauesten Informationen erhalten Sie, indem Sie direkt zur Referenzseite std::distance navigieren.

Beispielcode aus der std::distance Referenz Webseite:

include <iostream> 
#include <iterator> 
#include <vector> 

int main() 
{ 
    std::vector<int> v{ 3, 1, 4 }; 

    auto distance = std::distance(v.begin(), v.end()); 

    std::cout << distance << '\n'; 
}