C++ Container für pair?

[T_55]

Hallo,
Ich suche ein Container für ein pair wo der eine Wert A den Key darstellt, der Container aber nach dem anderen Wert B sortiert ist.
Die std::map macht beides im Key : Zugriff per Key, sortiert auch anhand Key.
Ich möchte aber Zugriff per Key A und sortiert nach Value B.
Wenn ich den Wert B als Key nehme und den Key A als Wert dann ist zwar bei std::map alles fein nach B sortiert aber dann gibts eben kein Zugriff mehr per Key A. Im übrigen soll B öfters mal geändert werden, diesen dann als Key zu nehmen würde dann immer ein komplettes löschen und neu erstellen bedeuten, nicht gut.
Also kurz gesagt ist das Ziel: Zugriff Key A, Sortierung nach B.
Ich konnte leider nichts gutes finden, ist dafür ein passenden Container bekannt oder kann man sich sowas selbst schreiben?
Grüße

 

[coolmodi]

Bin kein Profi was C++ angeht, und es ist früh, aber mein müdes Ich sieht das so:

Wenn Keys fest und beliebig sein sollen, Werte sich verändern können sollen, und Werte die Ordnung vorgeben sollen, dann musst du dir da selbst was bauen. Wüsste nicht dass es so etwas von Haus aus gibt. Du willst ja mehr oder weniger eine map, set und vector gleichzeitig.

Wenn die Anzahl der Werte sich in Grenzen hält, und/oder du die Ordnung vergleichsweise selten brauchst, dann wäre eine Option einfach eine map zu nehmen, und dann on-demand ein (multi)set aus den Werten zu erstellen wenn benötigt.

Ansonsten eine eigene Containerklasse erstellen, welche beim Hinzufügen, Entfernen und Ändern immer eine Ordnung aktualisiert, z.B. map um key->value zu speichern, und eine map (oder vermutlich eher set, müsste machen was es soll) der keys der map, mit Werten als key. Ist dementsprechend aufwändiger bei den genannten Operationen, aber kann jederzeit geordnet nach Werten iteriert werden.

Kommt halt sehr stark auf den genauen Anwendungszweck an.

 

[kuddlmuddl]

Warum ist dir die Sortierung nach Value denn wichtig?

Deine Anforderung macht wenig Sinn muss ich mal behaupten.

Was is dein eigentliches Problem, was du zu lösen versuchst? Da gibts sicher ne passende Antwort.

Ich glaube in boost gibts ne map die auch query per Value erlaubt, also quasi beides
https://www.boost.org/doc/libs/1_70_0/libs/fusion/doc/html/index.html
Evtl mittels der „Views“

 

[hroessler]

Hallo,
ich sehe das wie @kuddlmuddl. Wenn du sowieso über Keys zugreifen möchtest, wozu benötigst du dann eine Sortierung nach Values?

Erläutere doch bitte mal deinen Gedankengang, den du dabei hast.

greetz
hroessler

 

[Raijin]

Das klingt irgendwie nach einem klassichen XY-Problem. Ich schließe mich der Frage nach dem eigentlichen Ziel an. Um es nochmal klar zu machen: Beschreibe deinen Anwendungsfall, das was du lösen willst (X) und nicht die vermeintliche Lösung, die du dir dazu ausgedacht hast (Y) und nun scheinbar nicht umsetzen kannst.

Beispiel eines XY-Problems:

Wenn am Auto der Auspuff klappert (X), fährt man ja auch nicht in die Werkstatt und erklärt dem Mechanicus, dass er einem doch bitte zeigen soll wie die Benzinpumpe getauscht wird (Y), weil man denkt, damit den klappernden Auspuff zu reparieren. Nein, man erzählt dem Mechanicus direkt von X, dem klappernden Auspuff

 

[T_55]

Der Grund ist, dass über die Keys (Anzahl immer fix) die assoziierenden Values regelmäßig aktualisiert werden aber auch häufig die Keys der Value-Extremwerte (min/max und die folgenden darauf folgenden x) ermittelt werden sollen.
Das heißt ich will nicht nur per Key die assoziierenden Values aktualisieren, sondern auch anhand der Value-sortier-Position die assoziierenden Keys herausfinden (zB die maximalen x oder minimalen x Values der kompletten Liste).

Funktionieren tut das natürlich auf verschiedenen Art und Weise. Ich finde nur total unschön, dass man mindestens immer von einer Seite aus einen Kompromiss eingeht um den gewünschten Zugriff zu erhalten, zB gibt es folgende Möglichkeiten, die halte ich aber für unschön und langsam:

1. Nehme unordered_multimap: Wert A als Key. Wert B als Value.
Vorteil: Aktualisieren von Wert B über Key A geht easy.
Nachteil: Zugriff auf die x max/min Werte B der Liste geht nicht da nicht danach sortiert. Man müsste also die Map komplett durchiterieren oder etwas anderes machen um die x max/min Werte B der Liste zu finden und daraus die assoziierenden Keys A.

1b: Das selbe als unordered_multiset mit std:: pair. Vor-Nachteile müssten identisch sein.

2. Nehme multimap (ordered): Wert B als Key. Wert A als Value.
Vorteil: Map immer nach B sortiert. Zugriff auf x max/min Werte und dessen assoziierenden Wert A geht easy über begin() end().
Nachteil: Das häufige Aktualisieren des Values B (der hier der Key ist) geht nur über komplettes erase() und dann neues insert() -> sehr unschön und langsam.

2b: Das selbe als multiset (ordered) mit std:: pair. Vor-Nachteile müssten identisch sein.

3. Nehme vector mit std:: pair oder struct:
Vorteil: da die Keys fix sind kann der Key dem vector-Index entsprechen.
Vorteil: Aktualisieren von Wert B über Index A geht easy und flott.
Nachteil: Zugriff auf die x max/min Werte B der Liste geht nicht da nicht danach sortiert. Man müsste also den Vector komplett kopieren und dann per std::sort sortieren um die assoziierenden Keys der maximalen x oder minimalen x Values der kompletten Liste herauszufinden. Die Kopie muss sein da sonst nach dem sortieren die Keys nicht mehr dem Index entsprechen würden.


Daher gibt es immer einen Kompromiss:

• Kompromiss A: Das Aktualisieren der Values über den Key ist einfach wenn A als Key/Index fungiert aber dann ist das schnelle finden dieser Keys anhand der maximalen x oder minimalen x Values der kompletten Liste nur durch aufwändiges kopieren/sortieren möglich.
• Kompromiss B: Das Finden der Keys anhand der maximalen x oder minimalen x Values der kompletten Liste ist schnell möglich wenn Value B als Key fungiert und so sortiert ist aber dann ist das Aktualisieren der Values B durch Zugriff von A sehr aufwändig weil -> erst finden dann erase() dann insert().

Grundsätzlich kommt der Usecase "Aktualisiere Values B über Zugriff Key A" etwas häufiger vor als "zeige mir die assoziierenden Keys der x max/min-Werte B der ganzen Liste".
Daher ist Variante 1, 1b und 3 vermutlich tendenziell schneller als 2 und 2b. Ein Kompromiss ist es aber in beiden Fällen.

Cool wäre daher ein Container für ein pair bei dem Wert A den Key darstellt (flottes und häufiges aktualisieren des assoziierenden Values über diesen Key) UND der Container aber nach dem Value B sortiert ist (flotter Zugriff auf assoziierenden Keys über maximale x oder minimale x Values der kompletten Liste (zb über begin() end()).

 

[hroessler]

Wenn du Werte öfter aktualisierst, musst so sowieso öfter sortieren. Ich würde mir die Werte beim "holen" einfach sortiert zurückgeben lassen bzw. selbst sortieren.

greetz
hroessler

 

[T_55]

Ja erst wenn ich über den max/min Value der kompletten Liste die assoziierenden Keys erfahren will brauche ich es sortiert. Beim Aktualisieren der Values umgekehrt über die Keys wäre es nicht zwangsläufig nötig.

Ansonsten ich lese mich gerade auch in doppelt verkettete Listen ein. Evt versuche ich mal eine doppelt verkettete Liste auf Basis eines std::vectors zu bauen. Key entspricht index und datentyp von vector ist struct mit dem value und zwei pointern zum sortierten vorgänger und nachfolger... Man macht dann noch ein start und endpointer von dem aus man die max-min werte findet und dessen folgenden. Wenn ich dann sage: gebe mir den key von dem dritt-kleinsten Value dann starte ich vom start-pointer und gehe über die pointer zum dritten knoten.
Um es aktuell zu halten müssten dann jedes mal, wenn über einen Key der Value verändert wird, auch entsprechend die pointer der verkettete Liste so angepasst werden, dass die Verkettung immer sortiert ist.
Mal sehen ich hab noch nie verkettete Listen gemacht setze mich mal dran.

Ergänzung (11. August 2019)

wobei ich überlege gerade, jede Änderung des Values bewirkt dann, dass die Pointer des Value neu verbunden werden müssen und man so sich in der Liste von Pointer zu Pointer iterieren muss bis man die neue richtige Position gefunden hat. Das ist sicher ein gewisser Overhead, die Frage ist dann tatsächlich ob Variante 3 (#6) mit einem vector der dann kopiert wird und sortiert std::sort dann am Ende nicht sogar flotter geht...

 

[kuddlmuddl]

Das lässt sich viel effizienter lösen

Evtl hab ich nachher Zeit was zu tippen..

Sind As eindeutig? Und sind Bs eindeutig?
Und sind As einfache Datentypen wie int? Du sagtest ja, dass es der index eines vektors sein könnte. Dh lückenlos und immer >=0?

 

[T_55]

Ja genau Key A ist immer int und geht ab 0 hoch, kann daher auf jeden Fall index eines std::vector sein.
Die Anzahl der Einträge wird zur Laufzeit einmal fix festgelegt und verändert sich ab dann nicht mehr also zB resize(999) und danach ist es fix.
Value B ist immer Datentyp double.

 

[T_55]

Nachdem ich über verkettete Listen nun bis hin zu Rot-Schwarz-Bäumen mir alles möglich reingezogen habe bin ich jetzt auf Boost.MultiIndex gestoßen, sollte in die richtige Richtung gehen.

Ansonsten std::vector als Basis fand ich ansonsten auch ein guten Ansatz da ist schon mal eine gewisse Cachelokalität gegeben, man müssten dann vielleicht noch irgend eine verkettete Sache oder ein Suchbaum dranbauen... Ich guck mir jetzt erstmal Boost.MultiIndex an...

Das lässt sich viel effizienter lösen

das wäre natürlich noch besser

Ergänzung (11. August 2019)

ps: ok Boost.MultiIndex ist raus, man kann den Value nicht ändern:

Daten wie Name und Beine je nach Schnittstelle Schlüssel sein können, dürfen sie nicht beliebig geändert werden können. Wenn zum Beispiel nach einem Tier mit einem bestimmten Namen gesucht wird und die Anzahl der Beine des Tiers geändert werden könnte, wüsste die andere Schnittstelle, die die Anzahl der Beine als Schlüssel verwendet, nicht, dass einer der Schlüssel geändert wurde und ein neuer Hashwert gebildet werden muss.
So wie es nicht möglich ist, den Schlüssel in einem Container vom Typ std::unordered_map zu ändern, können Daten in einem MultiIndex-Container nicht geändert werden.

https://dieboostcppbibliotheken.de/boost.multiindex

Ergänzung (11. August 2019)

Der Kniff ist wohl wirklich das B verändert wird (und der Value mehrfach vorkommen kann), dies macht es sinnfrei Ihn zb in einer zweiten Map als Key zu nutzen, was wiederum eine automatische Sortierung aber unmöglich macht.

Sind As eindeutig? Und sind Bs eindeutig?

Wenn ich die Frage richtig verstehe, ob die Values mehrfach vorkommen können?

Bei "Key/Index A": NEIN alle Werte sind unterschiedlich (integer wie array index). Jeder Eintrag hat ein einzigartigen Wert den kein anderer Eintrag hat.

Bei "Value B": JA Werte können mehrfach vorkommen. In mehreren Einträgen kann der selbe Wert enthalten sein.

 

[striker159]

Wie wäre es, einen einfachen Wrapper um eine map zu schreiben, der beim Einfügen bzw Update das aktuelle minimum und Maximum anpasst?
In etwa soetwas:

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <limits>

template<class Key, class T>
struct S{
    using Map_t = std::unordered_multimap<Key, T>;
    using iterator = typename Map_t::iterator;
    using const_iterator = typename Map_t::const_iterator;
    using value_type = typename Map_t::value_type;
    
    Map_t map;
    
    Key kmin{};
    Key kmax{};
    T vmin = std::numeric_limits<T>::max();
    T vmax = std::numeric_limits<T>::min();
    
    void clear(){
        map.clear();
        kmin = Key{};
        kmax = Key{};
        vmin = std::numeric_limits<T>::max();
        vmax = std::numeric_limits<T>::min();
    }
    
    void insert(const Key& k, const T& v){
        map.insert(std::make_pair(k,v));
        if(v < vmin){
            vmin = v;
            kmin = k;
        }
        if(v > vmax){
            vmax = v;
            kmax = k;
        }
    }
    
    std::pair<const_iterator,const_iterator> equal_range(Key key) const{
        return map.equal_range(key);   
    }
    
    value_type getMin() const{
        return std::make_pair(kmin, vmin);
    }
    
    value_type getMax() const{
        return std::make_pair(kmax, vmax);   
    }
};

int main()
{
  S<int, double> map;
  map.insert(0, 1.0);
  map.insert(0, 2.0);
  map.insert(1, 3.0);
  map.insert(2, 42.0);
  
  auto eq = map.equal_range(0);
  for(auto it = eq.first; it != eq.second; ++it){
      std::cout << "(" << it->first << ", " << it->second << "), ";
  }
  std::cout << std::endl;
  
  auto pmin = map.getMin();
  auto pmax = map.getMax();
  std::cout << "min (" << pmin.first << ", " << pmin.second << ")" << std::endl;
  std::cout << "max (" << pmax.first << ", " << pmax.second << ")" << std::endl;
}

 

[kuddlmuddl]

Wie wäre es, einen einfachen Wrapper um eine map zu schreiben, der beim Einfügen bzw Update das aktuelle minimum und Maximum anpasst?

Hatte ich auch überlegt, aber dann kann man schlecht zB das zweit und drittbeste finden. Ich hatte ihn so verstanden, dass das wichtig wäre.

Aber nen Wrapper um stl Container war natürlich auch meine Idee.

 

[T_55]

Danke @striker159 guter Ansatz mit dem Wrapper aber das wäre dann nur ein einziger max/min Wert aber ich will dann auch hoch bzw runter iterieren können um die Keys der zB 15 kleinsten/größten Werte zu erhalten. Daher irgendeine sortierte Sache muss es irgendwie geben bei der man ab dem maximum runter gehen kann und in sortierter Reihenfolge auch auf die nächstkleineren herankommt.

 

[coolmodi]

Dann mach es doch wie ich gesagt habe, und aktualisiere statt min und max einfach eine komplette Ordnung aller keys. Einfügen, Ändern und Entfernen ist dementsprechend dann viel kostenintesiver.

Je nach dem wie wichtig Performance ist, kannst du da einen vector (direkter Zugriff auf Positionen) oder sogar einfach ne andere map für nehmen. Aber bei dem Vorhaben ist performance vermutlich eh keine Priorität

 

[kuddlmuddl]

Habs mal so probiert. Ich dachte man schaffts in O(1) aber ich glaube das ist entweder deutlich schwieriger oder gar unmöglich. unordered_maps haben O(1) inserts aber sind - wie ja der Name sagt - leider unsortiert.

Das hier ist nun aber immerhin in der Lage Duplikate bei B zu vertragen (multimap) und hat nur O(log N) time und natürlich O(n) space:

#include <QCoreApplication>
#include <iostream>
#include <math.h>

typedef uint32_t Key;
typedef double Value;

class Storage
{
public:
    Storage(size_t size)
    {
        m_values.resize(size);
    }

    const Value& get(const Key& index) const // O(1)
    {
        return m_values[static_cast<size_t>(index)];
    }

    void set(const Key& key, const Value& value) // O(log N), N := m_values.size()
    {
        size_t indexST = static_cast<size_t>(key);

        // Remove the correct pair from multimap which will be replaced
        const Value& oldValueAtIndex = m_values[indexST];
        // http://www.cplusplus.com/reference/map/multimap/equal_range/
        std::pair<std::multimap<Value, Key>::iterator, std::multimap<Value, Key>::iterator> ret;
        ret = m_PairsOfValueKey.equal_range(oldValueAtIndex);
        for (std::multimap<Value, Key>::iterator it = ret.first; it != ret.second; ++it)
        {
            const Value& v = it->first;
            const Key& k = it->second;
            if (key == k && oldValueAtIndex == v)
            {
                // https://stackoverflow.com/questions/3952476/how-to-remove-a-specific-pair-from-a-c-multimap
                m_PairsOfValueKey.erase(it);
                break;
            }
        }

        m_PairsOfValueKey.insert(std::make_pair(value, key));

        m_values[indexST] = value;
    }

    void printAll() const
    {
        std::cout << "Vector:\n";
        for (size_t i = 0; i < m_values.size(); ++i)
            std::cout << i << " | " << m_values[i] << "\n";
        std::cout << "\n";

        std::cout << "Map<Value, Key>:\n";
        for (const auto& pair : m_PairsOfValueKey)
            std::cout << "[" << pair.first << "] " << pair.second << "\n";
        std::cout << "\n";
    }

    void printNSmallest(size_t limit) const
    {
        std::cout << "print" << limit << "Smallest of Map<Value, Key>:\n";
        size_t counter = 0;
        for (auto it = m_PairsOfValueKey.cbegin(); it != m_PairsOfValueKey.cend() && counter < limit; ++it, counter += 1)
            std::cout << "[" << it->first << "] " << it->second << "\n";
    }
    void printNBiggest(size_t limit) const
    {
        std::cout << "print" << limit << "Biggest of Map<Value, Key>:\n";
        size_t counter = 0;
        for (auto rit = m_PairsOfValueKey.crbegin(); rit != m_PairsOfValueKey.crend() && counter < limit; ++rit, counter += 1)
            std::cout << "[" << rit->first << "] " << rit->second << "\n";
    }

private:
    std::vector<Value> m_values;
    std::multimap<Value, Key> m_PairsOfValueKey;
};

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    Storage storage(6);
    for (Key i = 0; i < 6; ++i)
        storage.set(i, fmod(i * 10.0 , 30.0));

    storage.printAll();
    storage.printNSmallest(3);
    storage.printNBiggest(3);

    std::cout << "----------------------------------------------------------------------------------\n";
    std::cout << "Testing replaces:\n";
    std::cout << "----------------------------------------------------------------------------------\n";

    for (Key i = 0; i < 6; i += 2)
        storage.set(i, 1000.0 + static_cast<double>(i));

    storage.printAll();
    storage.printNSmallest(3);
    storage.printNBiggest(3);

    return a.exec();
}

Edit: Für Sonderfälle, wo zB alle Values gleich sind dauert der insert bis zu N, also wohl doch nur O(N) im worst case

 

[T_55]

Prima danke das läuft. Man kommt da wohl leider echt nicht so leicht am iterieren->erase->insert vorbei.
ps: den double Vergleich "&& oldValueAtIndex == v" könnte man eigentlich weglassen oder?

Aber bei dem Vorhaben ist performance vermutlich eh keine Priorität

Ich hab wohl schon meinen Ruf Man muss es am Ende ohnehin messen aber bei der Sache hier find ich es echt spannend wie bestimmte Anforderungen (hier die Sortierung nach Value und der damit umständlichere Zugriff auf den ursprünglichen Key) zwangsläufig eine Grenze der Möglichkeiten setzt, wo man einfach nicht mehr viel mehr anderes machen kann. Aber genau wegen dieser Anforderungen der Sortierung gibts dann eben auch kein Free-Lunch bei der Rechenzeit

 

[coolmodi]

Habs mal so probiert. Ich dachte man schaffts in O(1) aber ich glaube das ist entweder deutlich schwieriger oder gar unmöglich.

O(1) ist nur möglich, wenn du direkt auf Speicherbereiche zugreifen kannst. Das ist nur bei Arrays und bekanntem Key der Fall.

Hier hast du ja in jedem erdenklichen Fall O(logn) für den lookup (bei dir equal_range) und O(logn) fürs einfügen. Binärbäume sind da einfach mit das höchste der Gefühle.

Wenn das generelle Verhalten bekannt ist kann man noch etwas optimieren, vor allem wenn einem Speicher egal ist. Und mit hints kann man beim insert noch was rausholen, vor allem im Randbereich.

ps: den double Vergleich "&& oldValueAtIndex == v" könnte man eigentlich weglassen oder?

Ne, das ist eine multimap, d.h. keys sind nicht eindeutig. Gesucht ist da das genaue key->value paar, wobei key ja der eigentlich Wert in der ganzen Sache ist, und der kann eben doppelt vorkommen. Ansonsten könnte man eine normale map nehmen, und einfach direkt erase mit dem Wert aufrufen. Performancetechnisch aber kaum bis kein Unterschied.