Schneller Zugriff aus 2dim Elemente
-
Ein Gerüst hab' ich schon: http://ideone.com/N58aM
Jetzt muss das alles noch umgeschrieben werden.
-
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>?
-
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!
-
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.
-
Oje, es tut mir Leid!
-
Decimad schrieb:
Oje, es tut mir Leid!
Haha, entspann dich
Jetzt mach ich's richtig. Da hat sich aber wetten noch keiner rangetraut
-
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" ) ); } }
-
Zerstör' doch nicht den Spaß, camper
Ich seh's gerade vor mir, der Camper oben auf dem Dach mit seinem Spoilerrifle
-
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)?
-
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.
-
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.
-
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).
-
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.
-
Sone schrieb:
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.
Schon mal auf Einbahnstraßen unterwegs gewesen?
-
Edit: Was hat eine Einbahnstraße mit einer Anordnung von Elementen zu tun? Klar, die Autos sollen die Gegenstücke im Analogieschluss sein, aber....
-
Der TE redet von Ausgangs- und Zielorten. Da steht nicht, dass diese austauschbar sein sollen.
Ohne den Kontext zu kennen, kann nicht einfach angenommen werden, das der Weg von A nach B gleich dem Weg von B nach A wäre.
Und da die Mengen der Ausgangs- und Zielpunkte sowieso disjunkt sein sollen, kommt es darauf für den TE sowieso nicht an, mithin besteht auch gar keine Notwendigkeit, darauf speziell einzugehen.
Wenn eine solche Nebenabrede getroffen werden soll, muss der Ordnungsindex eben entsprechend angepasst werden (z.B. statt pair<A,B> ordered_pair<A,B> als Vergleichsobjekt).
-
camper schrieb:
Ohne den Kontext zu kennen, kann nicht einfach angenommen werden, das der Weg von A nach B gleich dem Weg von B nach A wäre.
Ja, du hast Recht. Ich dachte, Köln--Düsseldorf wäre umgekehrt genauso schnell, aber vielleicht fliegt man ja eine Umleitung o.ä.
-
Sone schrieb:
Edit: Was hat eine Einbahnstraße mit einer Anordnung von Elementen zu tun? Klar, die Autos sollen die Gegenstücke im Analogieschluss sein, aber....
Stichwort: gerichtete gewichtete Graphen
-
camper schrieb:
Der TE redet von Ausgangs- und Zielorten. Da steht nicht, dass diese austauschbar sein sollen.
Ohne den Kontext zu kennen, kann nicht einfach angenommen werden, das der Weg von A nach B gleich dem Weg von B nach A wäre.
Und da die Mengen der Ausgangs- und Zielpunkte sowieso disjunkt sein sollen, kommt es darauf für den TE sowieso nicht an, mithin besteht auch gar keine Notwendigkeit, darauf speziell einzugehen.
Wenn eine solche Nebenabrede getroffen werden soll, muss der Ordnungsindex eben entsprechend angepasst werden (z.B. statt pair<A,B> ordered_pair<A,B> als Vergleichsobjekt).das hast du dir aus den fingern gesaugt
klar sind andere entfernungen denkbar, im sinne von len(A,B) != len(B,A), eben undendlich viele und so viel speicher haben wir momentan noch nicht ganz zur verfügung.Thomas1982 schrieb:
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).es könnte eventuell sinnvoll sein, wenn du deine matrix so aufbauen würdest ( falls sie nicht schon so aufgebaut ist ), dass sie den anforderungen des dijkstra algorithmus genügt:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
-
xyz offgeloggt schrieb:
camper schrieb:
Der TE redet von Ausgangs- und Zielorten. Da steht nicht, dass diese austauschbar sein sollen.
Ohne den Kontext zu kennen, kann nicht einfach angenommen werden, das der Weg von A nach B gleich dem Weg von B nach A wäre.
Und da die Mengen der Ausgangs- und Zielpunkte sowieso disjunkt sein sollen, kommt es darauf für den TE sowieso nicht an, mithin besteht auch gar keine Notwendigkeit, darauf speziell einzugehen.
Wenn eine solche Nebenabrede getroffen werden soll, muss der Ordnungsindex eben entsprechend angepasst werden (z.B. statt pair<A,B> ordered_pair<A,B> als Vergleichsobjekt).das hast du dir aus den fingern gesaugt
y, ist ja auch fern von jeder realität - stimmt...
xyz offgeloggt schrieb:
klar sind andere entfernungen denkbar, im sinne von len(A,B) != len(B,A), eben undendlich viele und so viel speicher haben wir momentan noch nicht ganz zur verfügung.
Thomas1982 schrieb:
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).es könnte eventuell sinnvoll sein, wenn du deine matrix so aufbauen würdest ( falls sie nicht schon so aufgebaut ist ), dass sie den anforderungen des dijkstra algorithmus genügt:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmusach - man sollte also nicht davon ausgehen, dass es negativ gewichtete kanten gibt... komisch
