Frage zu std::map und dessen insert-Methode

HumeSikkins

Hallo,
falls du effizientes Einfügen und effizientes Updaten Hand in Hand haben willst, hilft eine kleine Funktion:

template <class MapType, class KeyType, class ValueType>
typename MapType::iterator InsertOrUpdate(MapType& m, const KeyType& k, const ValueType& v)
{
    // suche Element mit Schlüssel k oder falls nicht vorhanden,
    // suche den Platz, wo ein solches Element hingehört.
    // Diese Operation hat eine logarithmische Komplexität
    typename MapType::iterator InsertPos = m.lower_bound(k);

    if (InsertPos != m.end() && ! (m.key_comp()(k, InsertPos->first)))
    {    // Ok. Schlüssel existiert -> Wert updaten  
         InsertPos->second = v;
         return InsertPos;
    }
    typedef typename MapType::value_type MapValType;
    // neues Element einfügen. Da wir bereits einen Iterator
    // auf die korrekte Einfügeposition haben, hat diese Operation
    // eine konstante Komplexität.
    return m.insert(InsertPos, MapValType(k, v));
}

volkard

template <class MapType, class KeyType, class ValueType>
typename MapType::iterator InsertOrUpdate(MapType& m, const KeyType& k, const ValueType& v)
erinnert mich in der wirkung sehr an den op[].

HumeSikkins

@volkard
Wieso? Zwar hat die Funktion eine Ähnlichkeit zum Op[]. Es gibt aber einen entscheidenen Unterschied. Der Op[] erzeugt für einen noch nicht vorhandenen Wert zuerst einen mit dem Default-Ctor und führt dann eine Zuweisung durch.

Oder was meinst du?

volkard

Hab mal gemessen (mit MSVC, auf Geschwindigkeit optimiert):

#include <iostream>
#include <map>
#include <ctime>
using namespace std;

template <class MapType, class KeyType, class ValueType>
typename MapType::iterator InsertOrUpdate(MapType& m, const KeyType& k, const ValueType& v)
{
    // suche Element mit Schlüssel k oder falls nicht vorhanden,
    // suche den Platz, wo ein solches Element hingehört.
    // Diese Operation hat eine logarithmische Komplexität
    typename MapType::iterator InsertPos = m.lower_bound(k);

    if (InsertPos != m.end() && ! (m.key_comp()(k, InsertPos->first)))
    {    // Ok. Schlüssel existiert -> Wert updaten  
         InsertPos->second = v;
         return InsertPos;
    }
    typedef typename MapType::value_type MapValType;
    // neues Element einfügen. Da wir bereits einen Iterator
    // auf die korrekte Einfügeposition haben, hat diese Operation
    // eine konstante Komplexität.
    return m.insert(InsertPos, MapValType(k, v));
}

struct Big
{
    char data[10];
    Big()
    {
        memset(data,0,sizeof(data));
    }
    Big(Big const& b)
    {
        memcpy(data,b.data,sizeof(data));
    }
    Big& operator=(Big const& b)
    {
        memcpy(data,b.data,sizeof(data));
        return *this;
    }
    ~Big()
    {//nothing to do
    }
};

int __cdecl main()
{
    {
        clock_t start=clock();
        map<int,Big> m;
        Big big;
        for(int i=0;i<1000000;++i)
            m[i]=big;
        clock_t stop=clock();
        cout<<double(stop-start)/CLOCKS_PER_SEC<<endl;
    }
    {
        clock_t start=clock();
        map<int,Big> m;
        Big big;
        for(int i=0;i<1000000;++i)
            InsertOrUpdate(m,i,big);
        clock_t stop=clock();
        cout<<double(stop-start)/CLOCKS_PER_SEC<<endl;
    }
    return 0;
}

ausgabe:
2.784
3.265
und mit char data[1024] aber dafür 1/10 der Durchläufe:
1.902
2.093

Bestimmt kann man auch leicht ausmessen, daß InsertOrUpdate schneller als der op[] ist. ka, wo gerade der Meßfehler liegt. Aber signifikant wird der Unterschied nie sein.
Ich kenne aber nen guten Grund für deine InsertOrUpdate: Ich mag Default-Konstruktoren nicht.

HumeSikkins

[edit] Großen Quatsch über Schlüssel und seine Kosten entfernt! [/edit]

Ich kenne aber nen guten Grund für deine InsertOrUpdate: Ich mag Default-Konstruktoren nicht

Das ist auch meine größte Motivation für die Funktion. Allerdings verkauft sich Geschwindigkeit besser Und ich bin ja mehr BWLer als Informatiker (zumindest in deinen Augen )

[ Dieser Beitrag wurde am 11.09.2002 um 22:14 Uhr von HumeSikkins editiert. ]

[ Dieser Beitrag wurde am 11.09.2002 um 22:22 Uhr von HumeSikkins editiert. ]

HumeSikkins

Bestimmt kann man auch leicht ausmessen, daß InsertOrUpdate schneller als der op[] ist

Jo. Ich habe z.B. Big gerade so verändert, dass ich als Ausgabe
Op[]: 11.92
InsertOrUpdate: 0.11

erhalte.
Man muss ja nur den Def-Ctor teuer und den Copy-Ctor billig machen.

Hallo,

ich habe zwei Frage zu dieser InsertOrUpdate Funktion.

Wofür ist diese Prüfung vorhanden?

! (m.key_comp()(k, InsertPos->first))

Und ist lower_bound nicht das selbe wie find?

HumeSikkins

Hallo,
lower_bound liefert die Position des ersten Objekts mit dem Suchschlüssel
oder falls es keinen solchen Wert gibt, die Position an die ein entsprechendes Objekt eingefügt werden würde.

Existiert also an der gelieferten Position bereits ein Objekt und ist der übergebene Schlüssel *nicht* echt kleiner als der des an der Position vorhandenen Objekts (!m.key_comp()(k, InsertPos->first)), so ist der neue und der vorhandene Wert schlüsselgleich -> update. Ansonsten: insert

Hallo,

danke für die Erklärung, doch ich steige leider immer noch nicht dadurch.

Mit lower_bound kriegt man also die Position wo das Objekt ist/hin muss.

Mit InsertPos != m.end() testet man ob der Schlüssel existiert (Bedingung ergibt true) oder neu eingefügt werden muss (Bedingung ergibt false).

Existiert der Schlüssel updaten wir ihn. Existiert er nicht, fügen wir ihn neu ein.

Wofür brauche ich nun noch key_comp? Ich weiß jetzt zwar was die Funktion macht, aber wofür sie dort hin muss nicht.

HumeSikkins

Hallo,
wenn das Ergebnis von lower_bound != map::end() ist, dann wissen wir lediglich, dass unserer Iterator auf ein Objekt zeigt. Wir wissen aber noch nicht, ob dieses Objekt den gleichen Schlüssel hat, wie das einzufügende.
Es gibt nun zwei Möglichkeiten:
1. Liefert key_comp true, dann ist der Schlüssel des neuen Elements echt kleiner als der des vorhandenen. Das einzufügende Element kommt in der Sortierreihenfolge also *vor* dem vorhandenen Element. Das vorhandene Element stellt die untere Schranke dar. Wir müssen ein neues Objekt vor dem vorhandenen einfügen.

2. Liefert key_com false, dann ist der Schlüssel des neuen Objekts *nicht* echt kleiner als der des vorhandenen. Da das vorhandene aber die untere Schranke darstellt, wissen wir, dass die beiden Objekte einen äquivalenten Schlüssen im Sinne der Sortierreihenfolge hat. Wir müssen also lediglich den Wert des vorhandenen Objekt aktualisieren und zwar mit dem des übergebenen Objekts.

Hi HumeSikkins,

macht diese Funktion das Gleiche oder gibt es einen Unterschied zu deiner? (außer dem Rückgabewert)
Ich finde sie irgendwie verständlicher.

template <class MapType, class KeyType, class ValueType>
void InsertOrUpdate(MapType& map, const KeyType& key, const ValueType& value)
{
	typedef typename MapType::value_type MapValueType;
	typedef typename MapType::iterator MapIteratorType;

	std::pair<MapIteratorType, bool> insertionResult = map.insert(MapValueType(key, value));

	if(!insertionResult.second)
	{
		insertionResult.first->second = value;
	}
}

Ich schieb den Beitrag mal hoch.

HumeSikkins

knopf schrieb:

macht diese Funktion das Gleiche oder gibt es einen Unterschied zu deiner?

Sie macht zwar das Gleiche, kopiert aber u.U. mehr. Du legst in jedem Fall ein value_type-Objekt an, kopierst damit also in jedem Fall auch key.
Das ist aber nur nötig, wenn das Element bisher nicht existiert. Sonst reicht eine Zuweisung des Wertes.

Ich finde sie irgendwie verständlicher

Das ist sie wohl. Allerdings ist map[key] = value sogar noch verständlicher

Ich finde sie irgendwie verständlicher

Das ist sie wohl. Allerdings ist map[key] = value sogar noch verständlicher :)[/quote]

default ctor ist nicht akzeptabel.