Schneller Zugriff aus 2dim Elemente

[Thomas1982]

Hallo,

ich habe folgendes Problem:

Ich habe eine große Matrix, in der Entfernungen zwischen Städten/Orten
enthalten sind (Zeilen = Ausgangsorte, Spalten = Zielorte, wobei Ausgangsorte != Zielorte, also 2 verschiedenen Mengen).

Nun möchte ich möglichst schnell und effizient auf ein Matrixelement zugreifen.

Bisher habe ich mir ein kleines Klassenelement "Verbindung" geschrieben, welches aus 2 strings (Ausgangsort, Zielort) und 1 int (Entfernung zwischen den 2 Orten) besteht. Die Entfernungsmatrix habe ich dann mit einem Tool in eine Liste umgewandelt und dann als Textdatei gespeichert. Diese habe ich dann in C++ in einen vector<Verbindung> eingelesen.

Wie kann ich nun gezielt auf Entfernungswerte zugreifen?

Beispielsweise brauche ich in einer Funktion die Entfernung zwischen Stuttgart und Köln. Bisher bin ich dann immer mit mehreren for und if - Schleifen
durch meinen vector gelaufen und habe Elemente miteinander verglichen (if Ausgangsort == Stuttgart && Zielort == Köln, dann gebe int Wert vom vector<Verbindung> zurück).

Das funktioniert soweit, ist aber für meine riesige Matrix und der Vielzahl zur berechnenden Elemente sicherlich ineffizient

Gibt es in der STL (oder sonstwo) andere (bessere) Möglichkeiten?
Ich habe mich bereits kurz mit "maps" beschäftigt. Dort bräuchte ich aber dann statt einem Schlüssel 2 Schlüssel (string, string). Cool wäre, wenn es sowas geben würde wie

map Entfernung<string,string, int> mit 2 Schlüsseln, so dass man
einfach durch aufruf von
Entfernung[Stuttgart,Köln] den richtigen int-Wert ausgegeben bekommt.

Gibt es eine solche Möglichkeit mit 2 Schlüsseln in einer map bzw. gibt es
andere / bessere Möglichkeiten, mein Problem effizient zu implementieren?

Ich freue mich auf Antworten und Anregungen

Besten Dank!
Thomas

[SeppJ]

map<string, size_t> welche zu einem gegebenen String die passende Zeile/Spalte in der Matrix kennt.

[seldon]

Ich vermute, dass eine unordered_map<string, size_t> besser geeignet wäre (gerade, wenn die Matrix sehr groß wird). Das hängt aber davon ab, woher die Bezeichner stammen -- mit Hashes macht man sich potentiell immer verwundbar, wenn die Daten aus einer nicht vertrauenswürdigen Quelle kommen.

Besser noch wäre ein TST oder eine andere trie-artige Datenstruktur; diese ist aber in der Standardbibliothek nicht vorhanden. Es gibt in Boost.Spirit eine Klassenvorlage, die man dafür missbrauchen könnte: http://www.boost.org/doc/libs/1_51_0/libs/spirit/doc/html/spirit/qi/reference/string/symbols.html

[hustbaer]

Thomas1982 schrieb:

Cool wäre, wenn es sowas geben würde wie

map Entfernung<string,string, int> mit 2 Schlüsseln, so dass man
einfach durch aufruf von
Entfernung[Stuttgart,Köln] den richtigen int-Wert ausgegeben bekommt.

Gibt es eine solche Möglichkeit mit 2 Schlüsseln in einer map bzw. gibt es
andere / bessere Möglichkeiten, mein Problem effizient zu implementieren?

No, es gibt da z.B. std::pair .
Also

std::map<std::pair<std::string, std::string>, int> meineMap;
// ...
int entfernung = meineMap[std::make_pair("Stuttgart", "Köln")]; // Baum, alter

[Sone]

Neues Ziel für Heute: Ich bastle eine Trimap.

[out]

Sone schrieb:

Neues Ziel für Heute: Ich bastle eine Trimap.

Da bin ich mal gespannt

[Sone]

out schrieb:

Sone schrieb:

Neues Ziel für Heute: Ich bastle eine Trimap.

Da bin ich mal gespannt

Das dauert noch
Momentan bin ich bei equal_range/lower_bound/upper_bound

[Sone]

Ein Gerüst hab' ich schon: http://ideone.com/N58aM

Jetzt muss das alles noch umgeschrieben werden.

[Thomas1982]

Hallo,

vielen Dank für die Antworten bisher:

also die maps mit einem pair als Schlüssel habe ich glaub ich gebastelt bekommen:

// map.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <fstream>

using namespace std;

int main()
{
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// maps mit <pair,int> (06.10.2012)
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
map<pair<string, string>, int> Verbindung;
Verbindung.insert(make_pair(make_pair("Dortmund", "Hannover"), 123)); // manuell einlesen

// - - - - - - - - - - - - - - - aus Textdatei einlesen - - - - - - - - - - - - - - - - - - - - - -
fstream f("Testenternungen.txt");
while (! f.eof())
{
string d1, d2;
int d3;
f >> d1 >> d2 >> d3;
Verbindung.insert(make_pair(make_pair(d1,d2), d3));
}

// - - - - - - - - - - - - - - - alle Entfernungen ausgeben - - - - - - - - - - - - - - - - - - - -
for (map<pair<string, string>,int>::const_iterator it=Verbindung.begin(); it!=Verbindung.end(); ++it)
{
cout << "[" << it->first.first << " , " << it->first.second << "] = " << it->second << endl;
}

// - - - - - - - - - - - - - - - auf ein Element zugreifen- - - - - - - - - - - - - - - - - - - - -

string Ausgangsort = "Dortmund";
string Zielort = "Hannover";

map<pair<string, string>,int>::const_iterator it = Verbindung.find(make_pair(Ausgangsort,Zielort));
cout << "Entfernung zwischen " << Ausgangsort << " und " << Zielort << " = " << it->second << endl;

getchar();

return 0;
}

Welche Vorteile hat den eine Trimap gegenüber einer map<pair<string,string>, int>?

[Gast]

Der Zugriff auf die anderen beiden Elemente eine Trios über die Suche nach einem der Element des Trios. Zumindest wenn ich das jetzt richtig deute.

tri_map.insert( make_trio<A,B,C>( "a", "b", "c" ) );
assert( tri_map.get<0>["a"] == make_pair<B,C>( "b", "c" ) );
assert( tri_map.get<1>["b"] == make_pair<A,C>( "a", "c" ) );
assert( tri_map.get<2>["c"] == make_pair<A,B>( "a", "b" ) );

oder so ähnlich... mach das mal mit der map!

[Sone]

Decimad schrieb:

Der Zugriff auf die anderen beiden Elemente eine Trios über die Suche nach einem der Element des Trios. Zumindest wenn ich das jetzt richtig deute.

tri_map.insert( make_trio<A,B,C>( "a", "b", "c" ) );
assert( tri_map.get<0>["a"] == make_pair<B,C>( "b", "c" ) );
assert( tri_map.get<1>["b"] == make_pair<A,C>( "a", "c" ) );
assert( tri_map.get<2>["c"] == make_pair<A,B>( "a", "b" ) );

oder so ähnlich... mach das mal mit der map!

Oh, ich hab das missverstanden! Ich hab die ganze map falsch gemacht

Edit: Aber jetzt hab' ich auch keinen Bock mehr.

[Gast]

Oje, es tut mir Leid!

[Sone]

Decimad schrieb:

Oje, es tut mir Leid!

Haha, entspann dich
Jetzt mach ich's richtig. Da hat sich aber wetten noch keiner rangetraut

[camper]

Schnell mit multi_index_container zusammengeschrieben

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/global_fun.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <iterator>
#include <iostream>
#include <string>

using namespace boost::multi_index;

struct distance_map
{

    struct from_tag {};     typedef std::string from;
    struct to_tag {};       typedef std::string to;
    struct path_tag {};
    struct distance_tag {}; typedef int distance_type;

    typedef std::tuple<from, to, distance_type> tuple_type;

    struct value_type : tuple_type
    {
        value_type(from a, to b, distance_type c) : tuple_type{ a, b, c } {}
    };

    typedef boost::multi_index_container<value_type, indexed_by<
        ordered_non_unique<tag<from_tag>,     global_fun<const tuple_type&, const std::tuple_element<0, tuple_type>::type&, std::get<0>>>,
        ordered_non_unique<tag<to_tag>,       global_fun<const tuple_type&, const std::tuple_element<1, tuple_type>::type&, std::get<1>>>,
        ordered_non_unique<tag<distance_tag>, global_fun<const tuple_type&, const std::tuple_element<2, tuple_type>::type&, std::get<2>>>,
        ordered_unique<tag<path_tag>, composite_key<
            value_type,
            global_fun<const tuple_type&, const std::tuple_element<0, tuple_type>::type&, std::get<0>>,
            global_fun<const tuple_type&, const std::tuple_element<1, tuple_type>::type&, std::get<1>>
        >>
    >> type;
};

std::ostream& operator<<(std::ostream& s, const distance_map::value_type& v)
{
    return s << std::get<0>(v) << '\t' << std::get<1>(v) << '\t' << std::get<2>(v);
}

int main()
{
    distance_map::type m;

    m.insert(distance_map::value_type{ "A", "B", 10 });
    m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
    m.insert(distance_map::value_type{ "B", "A", 11 });
    m.insert(distance_map::value_type{ "A", "A", 0 });

    {
        std::cout << "from = A\n";
        auto range = m.get<distance_map::from_tag>().equal_range("A");
        std::copy( range.first, range.second, std::ostream_iterator<distance_map::value_type>( std::cout, "\n" ) );
    }
    {
        std::cout << "to = A\n";
        auto range = m.get<distance_map::to_tag>().equal_range("A");
        std::copy( range.first, range.second, std::ostream_iterator<distance_map::value_type>( std::cout, "\n" ) );
    }
    {
        std::cout << "distance = 10\n";
        auto range = m.get<distance_map::distance_tag>().equal_range(10);
        std::copy( range.first, range.second, std::ostream_iterator<distance_map::value_type>( std::cout, "\n" ) );
    }
    {
        std::cout << "path = A...B\n";
        auto range = m.get<distance_map::path_tag>().equal_range(boost::make_tuple("A", "B"));
        std::copy( range.first, range.second, std::ostream_iterator<distance_map::value_type>( std::cout, "\n" ) );
    }
}

[Gast]

Zerstör' doch nicht den Spaß, camper

Ich seh's gerade vor mir, der Camper oben auf dem Dach mit seinem Spoilerrifle

[Sone]

camper ist so ein Gott .

Edit: Wo camper schon mal da ist, ich hab so angefangen:

#include <tuple>
#include <set>

template<typename Type1,
         typename Type2,
         typename Type3,
         typename Compare = std::less<std::tuple<Type1,
                                                 Type2,
                                                 Type3>>,
         typename Allocator = std::allocator<std::tuple<Type1,
                                                        Type2,
                                                        Type3>>>
class trimap
{
public:

        typedef Type1 key_type_1;
        typedef Type2 key_type_2;
        typedef Type3 key_type_3;

        typedef std::tuple<key_type_1,
                           key_type_2,
                           key_type_3> value_type;

private:

        typedef std::set<value_type,
                         Compare,
                         Allocator> array_type;
        array_type mArray;

public:

        typedef typename array_type::size_type size_type;

        typedef typename Allocator::pointer pointer;
        typedef typename Allocator::const_pointer const_pointer;
        typedef typename Allocator::reference reference;
        typedef typename Allocator::const_reference const_reference;

        typedef typename array_type::iterator iterator;
        typedef typename array_type::const_iterator const_iterator;
        typedef typename array_type::reverse_iterator reverse_iterator;
        typedef typename array_type::const_reverse_iterator const_reverse_iterator;

        typedef Allocator allocator_type;
        typedef Compare key_compare;
        typedef typename Allocator::difference_type difference_type;

        explicit trimap( const Compare& comp = Compare(),
                         const Allocator& alloc = Allocator() ):
                mArray(comp, alloc) {}

        explicit trimap( const Allocator& alloc = Allocator() ):
                mArray(alloc) {}

        template< class InputIt >
        trimap( InputIt first, InputIt last,
                const Compare& comp = Compare(),
                const Allocator& alloc = Allocator() ):
                trimap(comp, alloc)
        {
                insert(first, last);
        }

        trimap( const trimap& other, const Allocator& alloc ):
                trimap(alloc)
        {
                *this = other;
        }

        trimap(trimap&&) = default;
        trimap(trimap&& other, const Allocator& alloc ):
                trimap(alloc)
        {
                operator=(std::forward<trimap>(other));
        }
        trimap(trimap const&) = default;

        trimap( std::initializer_list<value_type> init,
                const Compare& comp = Compare(),
                const Allocator& alloc = Allocator() ):
                trimap(comp, alloc)
        {
                mArray = std::move(init);
        }

        trimap& operator=( trimap const& other ) = default;
        trimap& operator=( trimap&& other ) = default;

        void swap(trimap& other)
        {
                mArray.swap(other.mArray);
        }

        allocator_type get_allocator() const {return mArray.get_allocator();}
        key_compare key_comp() const {return mArray.key_comp();}

        void clear(){mArray.clear();}
        bool empty() const { return mArray.empty();}
        size_type size() const { return mArray.size();}
        size_type max_size() const { return mArray.max_size();}

        iterator begin() {return mArray.begin();}
        const_iterator begin() const {return mArray.begin();}
        iterator end() {return mArray.end();}
        const_iterator end() const {return mArray.end();}
        reverse_iterator rbegin() {return mArray.rbegin();}
        const_reverse_iterator rbegin() const {return mArray.rbegin();}
        reverse_iterator rend() {return mArray.rend();}
        const_reverse_iterator rend() const {return mArray.rend();}

        const_iterator cbegin() const {return mArray.cbegin();}
        const_iterator cend() const {return mArray.cend();}
        const_reverse_iterator crbegin() const {return mArray.crbegin();}
        const_reverse_iterator crend() const {return mArray.crend();}
};

Hat's noch Sinn weiterzumachen? Oder gibt es von der Idee her noch was besseres (neben dem MultiIndex-Container)?

[hinundher]

camper schrieb:

distance_map::type m;

    m.insert(distance_map::value_type{ "A", "B", 10 });
    m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
    m.insert(distance_map::value_type{ "B", "A", 11 });
    m.insert(distance_map::value_type{ "A", "A", 0 });

Im Fall des TE macht die 3te Zeile aber keinen Sinn. Sind die selben Orte.

[camper]

hinundher schrieb:

camper schrieb:

distance_map::type m;

    m.insert(distance_map::value_type{ "A", "B", 10 });
    m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
    m.insert(distance_map::value_type{ "B", "A", 11 });
    m.insert(distance_map::value_type{ "A", "A", 0 });

Im Fall des TE macht die 3te Zeile aber keinen Sinn. Sind die selben Orte.

Aber andere Richtung.

[Sone]

hinundher schrieb:

camper schrieb:

distance_map::type m;

    m.insert(distance_map::value_type{ "A", "B", 10 });
    m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
    m.insert(distance_map::value_type{ "B", "A", 11 });
    m.insert(distance_map::value_type{ "A", "A", 0 });

Im Fall des TE macht die 3te Zeile aber keinen Sinn. Sind die selben Orte.

Genau das hab ich mit meiner Map zu lösen versucht (und geschafft).

[Sone]

camper schrieb:

hinundher schrieb:

camper schrieb:

distance_map::type m;

    m.insert(distance_map::value_type{ "A", "B", 10 });
    m.insert(distance_map::value_type{ "A", "B", 10 }); // ignoriert, Pfade sind unique
    m.insert(distance_map::value_type{ "B", "A", 11 });
    m.insert(distance_map::value_type{ "A", "A", 0 });

Im Fall des TE macht die 3te Zeile aber keinen Sinn. Sind die selben Orte.

Aber andere Richtung.

Na und? Es zählt doch die Kombination.