Container für ... ?

DDR-RAM

Also, ich sollte mir vielleicht mal nen bisschen STL "reinziehen".
Aber auf die Schnelle brauche ich erstmal nen Container für folgende Aufgabe.
Zwei nicht gleiche Zeiger p und q gleichen Typ als Schlüssel und
Ein weiterer Zeiger r als Wert.
also std::map böte sich an.
Allerdings ist der Schlüssel kein geordnetes Tupel, sondern ein ungeordnetes Tupel.
Folgende Funktionen sollen möglichst effizient sein
f(p;q) liefert zugehörigen Wert.
f(p) liefert Liste zugehöriger Schlüssel q und Werte r

Ich hatte zwei Ideen.
Erste Variante:
Verwendung von std::map, wobei der key ein nach aufsteigender Adresse geordnetes Paar von Zeigern ist.
f(p;q) würde normal funktionieren. Allerdings ist f(p) relativ aufwendig, wenn z.B. p der "größte" verwendete Zeiger ist. Sucht man auf einer unsortierten Liste sequenziell -> O(n).
Zweite variante, ich verwende wieder std::map mit geordneten tupeln als key. Allerdings speicher ich jeden möglichen Key in beiden Variationen. Die map enthält doppelt soviele keys aber gleiche Anzahl an values. einfüge-Operationen dauern doppelt solange und lösch-Operationen auch.
Zusatzbemerkung:
Außerdem muss ich die Daten (auf die r zeigt) noch nach einem weiteren Kriterium sortieren. Ich habe dafür ersteinmal ein set verwendet.

Welche Variante erste oder zweite erachtet ihr als sinnvoller, bzw. gibt es irgendeine Möglichkeit das besser oder anders zu lösen insbesondere unter Brücksichtigung der Zusatzbemerkung?
Ich bin die ganze Zeit am rätseln.
Danke für jede Wortmeldung.

MfG
DDR-RAM

Werner Salomon

Du kannst schon die von Dir beschriebenen erste Variante nehmen, ohne das f(p) dei Komplexität O(n) erreicht. Man kann auch ausnutzen das std::pair bereits über einen operator< verfügt und der 0-Pointer 'kleiner' als jeder andere ist. Dann wäre dies eine Möglichkeit:

#include <iostream>
#include <map>

class Egal {};

class Map
{
public:
    typedef std::pair< Egal*, Egal* > key_type;
    typedef int* mapped_type;
    typedef std::map< key_type, mapped_type > container_type;
    typedef container_type::iterator iterator;

    mapped_type& f( key_type::first_type p, key_type::second_type q )
    {
        return m_map[ std::make_pair( p, q ) ];
    }

    std::pair< iterator, iterator > f( key_type::first_type p )
    {
        return std::make_pair( m_map.lower_bound( std::make_pair( p, key_type::second_type(0) ) ),
            m_map.upper_bound( std::make_pair( p+1, key_type::second_type(0) ) ) );
    }
private:
    container_type m_map;
};

int main()
{
    using namespace std;
    Egal a,b, a1, b2, b3;
    int i1 = 1;
    int i2 = 2;
    int i3 = 3;
    Map m;
    m.f( &b, &b3 ) = &i3;
    m.f( &a, &a1 ) = &i1;
    m.f( &b, &b2 ) = &i2;
    std::pair< Map::iterator, Map::iterator > erg = m.f( &b );
    for( Map::iterator i = erg.first; i != erg.second; ++i )
    {
        cout << "Wert: " << *(i->second) << endl;
    }
    return 0;
}

Gruß
Werner

DDR-RAM

Problem ist nur, dass das ganze, so wie du das aufgeschrieben hast für geordnete Paare funktioniert. Aber die Reihenfolge kann für mich keine Rolle spielen und ist von daher egal.
assert(f(p;q) == f(q;p));
Ebenso die andere funktion f(p). p könnte sowohl first als auch second sein.

mapped_type& f( key_type::first_type p, key_type::second_type q )
    {
        return m_map[ std::make_pair( std::min( p, q ), std::max( p, q ) ) ];
    }

In der anderen Funktion geht dann das suchen los, weil die von dir vorgeschlagene Variante nur funktioniert, wenn p first ist. Aber p kann auch als second auftreten.

Trotzdem danke für die Antwort. (Ich muss mich mehr mit der STL und Boost befassen, die Syntax bereitet Freude)

MfG
DDR-RAM

camper

wie wärs mit boost::multi_index_container?

struct Value
{
    T* p;
    T* q;
    T* r;
};
typedef multi_index_container<
  Value,
  indexed_by<
    ordered_non_unique<member<Value,T*,&Value::p>,
    ordered_non_unique<member<Value,T*,&Value::q> >
  > 
> Container;

DDR-RAM

Der Name ist gut, ob er hält, was er verspricht werde ich mal am nachmittag oder so feststellen. jetzt geh ich erstmal schlafen. thx.

MfG
DDR-RAM