effizienteste Weg, ein Element in sortierten Array einfügen und findet den Index

Question

Ich brauche ein Element in sortierte Bereich einzufügen, aber ich muß auch seinen Index (Anzahl der Elemente in dem Bereich, das ist weniger als das Element) kennen. Ich möchte dies in O (logN) Zeit tun. Kann ich das mit einfachen C++ Containern machen?

Ich dachte, std :: multimap zu verwenden, mit diesem Container kann ich das Element an seinen Platz mit O (logN) Komplexität einfügen. Aber um den Index zu erhalten, muss ich std :: distance aufrufen, was O (N) -Operationen erfordert, da der Multimap-Iterator kein zufälliger Zugriff ist.

Ein anderer Weg ist, um std sortiert verwenden :: vector und std :: binary_search Algorithmus. In diesem Fall dauert die Suche O (logN), aber die Einfügung wird O (N) -Operationen benötigen, da die Einfügung in die Mitte des Vektors eine lineare Operation ist.

So gibt es std/Boost-Container, die ich verwenden kann, um das Ergebnis zu erreichen, oder ich brauche, um meine eigene Struktur für diesen zu implementieren? Vielen Dank!

Answer 1

können Sie verwenden Boost.MultiIndex ‚s ranked indices:

Live Coliru Demo

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/ranked_index.hpp> 
#include <boost/multi_index/identity.hpp> 

using namespace boost::multi_index; 
using ranked_int_set=multi_index_container< 
    int, 
    indexed_by< 
    ranked_unique<identity<int>> 
    > 
>; 

#include <iostream> 

int main() 
{ 
    ranked_int_set s={0,2,4,6,8,10,12,14,16}; 

    auto it=s.insert(9).first; 
    std::cout<<"9 was inserted at position #"<<s.rank(it)<<"\n"; 
    std::cout<<"14 is located at position #"<<s.find_rank(14)<<"\n"; 
} 

Ausgabe

 
9 was inserted at position #5 
14 is located at position #8 

Answer 2

Nein. Ich suchte danach.

Es gibt eine Möglichkeit, die Sie implementieren können. Beginnen Sie mit einem Binärbaum oder einer Überspringliste, und behalten Sie die Größe der Unterbäume/Überspringungen bei (ein bisschen zusätzlicher Aufwand - wenn Elemente eingefügt werden, müssen Sie zurück zu Eltern/Überspringen und Inkrementieren und ähnlich für Löschungen).

Dann können Sie Indizes in lg n Zeit, Direktzugriff (durch den Index oder Offset) in lg n Zeit erhalten, und halten Sie es zur gleichen Zeit sortiert.

Meine Versuche, einen vorgeschriebenen Container zu finden, die dies taten, waren fruchtlos, und das Projekt wurde in Dosen so habe ich das Schreiben nicht umgehen.

A full-on-Datenbank verwendet werden könnte, mit der sortierten Spalte indiziert, und man könnte die Zahl weniger als einigermaßen schnell erhalten kann.

Quoten sind, wenn ein einfacher linearer Vektor (mit seinem teuren Einsatz-in-Mitte) nicht vernünftig sortiert ist, könnte man sowieso eine Datenbank zu betrachten.

Als Beispiel für einen Container, der vielversprechend aussieht, aber fehlgeschlagen ist, können Sie mit dem MultiIndex-Container von Boost einen Container auf verschiedene Arten indizieren, aber die sequenziellen und geordneten Indizes sind unabhängig. So können Sie sagen, in welcher Reihenfolge Sie das Element eingefügt haben und wo es vorher/nachher in sort geht, aber nicht den Index, den es in der Sortierung hat.