Was ist ein Algorithmus oder Code für die Erlangung der ordinalen Position eines Elements in einer nach Wert sortierten Liste in C++

Question

Dies ist vergleichbar mit einer jüngste Frage.

Ich werde eine sortierte Liste von Werten pflegen. Ich werde Elemente von beliebigem Wert in die Liste einfügen. Jedes Mal, wenn ich einen Wert einfüge, möchte ich seine Ordnungsposition in der Liste bestimmen (ist es der 1., 2., 1000.). Was ist die effizienteste Datenstruktur und der effizienteste Algorithmus, um dies zu erreichen? Offensichtlich gibt es viele Algorithmen, mit denen dies möglich ist, aber ich sehe keine Möglichkeit, dies mit einfachen STL- oder QT-Vorlagenfunktionen zu bewerkstelligen. Idealerweise würde ich gerne wissen, ob es Open-Source-C++-Bibliotheken oder Beispielcode gibt, mit denen dies möglich ist.

Ich kann mir vorstellen, wie man einen B-Baum oder einen ähnlichen Algorithmus für diesen Zweck modifizieren kann, aber es scheint, dass es einen einfacheren Weg geben sollte.

Bearbeiten3:

Mike Seymour hat ziemlich genau bestätigt, dass es, wie ich in meinem ursprünglichen Beitrag schrieb, tatsächlich keine Möglichkeit gibt, diese Aufgabe mit einer einfachen STL zu bewältigen. Ich bin also auf der Suche nach einem guten btree, balanced-tree oder einer ähnlichen Open-Source-C++-Vorlage, die ohne oder mit möglichst wenigen Änderungen auskommt - Pavel Shved hat gezeigt, dass dies möglich ist, aber ich möchte mich nicht selbst in die Implementierung eines balancierten Baums stürzen.

(die Historie sollte meine erfolglosen Bemühungen zeigen, Mathieus Code mit make_heap so zu modifizieren, dass er O(log N) ist)

Bearbeiten 4:

Ich spreche Pavel trotzdem meine Anerkennung dafür aus, dass er darauf hingewiesen hat, dass btree a Lösung zu finden, muss ich erwähnen, dass der einfachste Weg, diese Art von Funktionalität zu erreichen, ohne die Implementierung eines benutzerdefinierte btree c++ Vorlage selbst zu erstellen, ist eine In-Memory-Datenbank verwenden . Dies würde log n ergeben und ist Ziemlich einfach zu implementieren.

Answer 1

Der Binärbaum ist dafür gut geeignet. Auch seine Änderung ist einfach: In jedem Knoten wird einfach die Anzahl der Knoten in seinem Teilbaum gespeichert.

Nachdem Sie einen Knoten eingefügt haben, suchen Sie ihn erneut, indem Sie von Root zu diesem Knoten gehen. Und aktualisieren Sie den Index rekursiv:

if (traverse to left subtree)
  index = index_on_previous_stage;
if (traverse to right subtree)
  index = index_on_previous_stage + left_subtree_size + 1;
if (found)
  return index + left_subtree_size;

Dies dauert O(log N) Zeit, genau wie das Einfügen.

Answer 2

Ich denke, Sie können std::set hier. Es bietet Ihnen Sortierverhalten gibt auch die Position des Iterators, wo der Wert eingefügt wird. Von dieser Position aus können Sie den Index ermitteln. Zum Beispiel:

std::set<int> s;
std::pair<std::set<int>::iterator, bool> aPair = s.insert(5);
size_t index = std::distance(s.begin(), aPair.first) ;

Answer 3

Beachten Sie, dass die Funktion std::list insert(it, value) einen Iterator für das neu eingefügte Element zurückgibt. Vielleicht kann das helfen?

Answer 4

Wenn Sie, wie Sie in einem Ihrer Kommentare schreiben, nur eine ungefähre ordinale Position, Sie könnten dies aus dem Bereich der Werte, die Sie bereits haben, schätzen - Sie müssen nur den ersten und den letzten Wert in der Sammlung in konstanter Zeit lesen, etwa so:

multiset<int> values;

values.insert(value);
int ordinal = values.size() * (value - values.front()) /
                              (values.back()-values.front());

Um die Annäherung zu verbessern, könnten Sie die statistischen Eigenschaften (Mittelwert und Varianz und möglicherweise Momente höherer Ordnung für eine bessere Genauigkeit) der Werte verfolgen, während Sie sie zu einer Mehrfachmenge hinzufügen. Dies wird immer noch eine konstante Zeit sein. Hier ist eine vage Skizze, wie man vorgehen könnte:

class SortedValues : public multiset<int>
{
public:
    SortedValues() : sum(0), sum2(0) {}

    int insert(int value)
    {
        // Insert the value and update the running totals
        multiset<int>::insert(value);
        sum += value;
        sum2 += value*value;

        // Calculate the mean and deviation.
        const float mean = float(sum) / size();
        const float deviation = sqrt(mean*mean - float(sum2)/size());

        // This function is left as an exercise for the reader.
        return size() * EstimatePercentile(value, mean, deviation);
    }

private:
    int sum;
    int sum2;
};

Answer 5

Wenn Sie eine ordinale Position wünschen, benötigen Sie einen Container, der die RandomAccessContainer Konzept... im Grunde genommen, ein std::vector .

Eine Art von Operationen auf einem std::vector sind relativ schnell, und Sie können die gewünschte Position mit std::lower_bound o std::upper_bound können Sie selbst entscheiden, ob Sie mehrere Werte auf einmal abrufen wollen. Um alle gleichen Werte abzurufen, ist eine gute Möglichkeit die Verwendung von std::equal_range was im Grunde das gleiche Ergebnis liefert wie die Anwendung der beiden lower y upper Schranken, aber mit einer besseren Komplexität.

Die gute Nachricht für die ordinale Position ist nun, dass std::distance als eine O(1)-Komplexität auf Modellen von RandomAccessIterator .

typedef std::vector<int> ints_t;
typedef ints_t::iterator iterator;

ints_t myInts;

for (iterator it = another.begin(), end = another.end(); it != end; ++it)
{
  int myValue = *it;
  iterator search = std::lower_bound(myInts.begin(), myInts.end(), myValue);
  myInts.insert(search, myValue);
  std::cout << "Inserted " << myValue << " at "
            << std::distance(myInts.begin(), search) << "\n";
  // Not necessary to flush there, that would slow things down
}

// Find all values equal to 50
std::pair<iterator,iterator> myPair =
    std::equal_range(myInts.begin(), myInts.end(), 50);
std::cout << "There are " << std::distance(myPair.first,myPair.second)
          << " values '50' in the vector, starting at index "
          << std::distance(myInts.begin(), myPair.first) << std::endl;

Ganz einfach, nicht wahr?

std::lower_bound , std::upper_bound y std::equal_range haben eine O(log(n)) Komplexität und std::distance hat eine O(1)-Komplexität, also ist dort alles ziemlich effizient...

EDITAR wie in den Kommentaren unterstrichen >> Einfügen ist eigentlich O(n), da man die Elemente verschieben muss.