geordnete Liste

Ich suche einen Container, der Elemente des Typs vector<int> aufnimmt und sortiert ist nach der Länge der vectoren. Einfügen und Löschen soll in O(1) gehen.

Suchst du ggf. so ein Konzept, wie es auch bei Bucket-Sort verwendet wird? Also mach einen Vector, der für jede verfügabare Länge wiederum eine Kollektion von vector<int> enthält.

Zumindest bekommst du so Einfügen in O(1) hin. Löschen hängst dann aber davon ab, wie viele andere Vectoren gleicher Länge zuvor eingefügt wurden.

Die andere Frage ist natürlich, ob man das will... Wie groß ist denn die Länge deiner Vectoren und wie viele sind es? Oder ist die Frge rein akademisch?

using ivec = vector<int>;
struct Cmp { 
  bool operator()(const ivec &lhs, const ivec &rhs) const
  { return lhs.size() < rhs.size(); }
};
set<ivec, Cmp> S;

hustbaer

O(1)
lol

Einfügen in O(1) geht wohl nicht. O(log(n)) sollte reichen.

Löschen in O(1) sollte aber gehen.

wob schrieb:

Suchst du ggf. so ein Konzept, wie es auch bei Bucket-Sort verwendet wird? Also mach einen Vector, der für jede verfügabare Länge wiederum eine Kollektion von vector<int> enthält.

Gute Idee, zumal ich eine obere Schranke für die Längen habe, die ca. 10 ist. Das wäre dann O(1).