Schneller Zugriff aus 2dim Elemente
-
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
-
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
.
Alsostd::map<std::pair<std::string, std::string>, int> meineMap; // ... int entfernung = meineMap[std::make_pair("Stuttgart", "Köln")]; // Baum, alter
-
Neues Ziel für Heute: Ich bastle eine Trimap.
-
Sone schrieb:
Neues Ziel für Heute: Ich bastle eine Trimap.
Da bin ich mal gespannt
-
out schrieb:
Sone schrieb:
Neues Ziel für Heute: Ich bastle eine Trimap.
Da bin ich mal gespannt
Das dauert noch
Momentan bin ich beiequal_range/lower_bound/upper_bound
-
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....