Map mit zwei Keys und Joker



  • Hallo,

    ich benötige folgende Struktur:

    ID1 | ID2 | Object
    1 A O1
    1 B O2
    1 E O3
    2 B O4
    3 B O5
    4 A O6
    4 E O7

    Das könnte man ja mit einer std::map und std::pair hinbekommen. Nun mein Problem. Ich möchte alle Objekte mit ID1 bzw. ID2 seperat abfragen können.

    Beispiel:

    ID1==1 soll ausgeben O1,O2,O3
    ID2== A soll ausgeben O1,O6

    Ich hoffe ihr versteht, wie ich das meine. Wie kann ich das umsetzen? Am besten mit std-Mitteln.

    Viele Grüße



  • Mach es einfach selbst. Schleife drüber, argument ist 1 ?: vektor anlegen; if(id == ...) { gefunden.push_back(); } return gefunden;

    das ist doch prunzeinfach.

    und pair/map-Zeug würd ich mir schon aus Hässlichkeit sparen und (wenn möglich) einfach ein struct { id1; id2; object; } bauen, das in einen std vektor kommt.



  • Aber sind dann Operationen wie das finden bzw. löschen nicht langsamer als bei einer Map?



  • Johnny123 schrieb:

    Aber sind dann Operationen wie das finden bzw. löschen nicht langsamer als bei einer Map?

    Von wie vielen Elementen sprechen wir hier?



  • 10k-100k würde ich sagen.



  • 10k-100k würde ich sagen.



  • Du könntest mal den Boost Container MultiIndex ausprobieren.



  • Th69 schrieb:

    Du könntest mal den Boost Container MultiIndex ausprobieren.

    ja aber das hätter er auch auf stackoverflow finden können.

    Ansonsten eigene Lösung mit einem Baum, oder einfach 100k if abfragen fressen, kann ja u.U. ok sein.



  • Du könntest die Objekte dynamisch erzeugen und zwei Container (für jede ID einen) mit IDs und Zeigern auf die Objekte vorhalten. Für die Verwaltung dieses Konstrukts eine Klasse schreiben, damit Speicherverwaltung und Zuordnung nicht schief gehen können.



  • Willst du ID1 oder ID2 abfragen könne, oder auch beide in kombi?



  • NullBockException schrieb:

    Willst du ID1 oder ID2 abfragen könne, oder auch beide in kombi?

    Also beim Suchen reicht eine. Zum Abfragen sollten schon beide gehen.



  • Ich hab was gebastet:

    #include <iostream>
    #include <iterator>
    #include <map>
    #include <set>
    #include <string>
    #include <utility>
    using namespace std;
    
    template<typename Key_1, typename Key_2, typename T>
    class multikey_map
    {
    	private:
    		set<T> values;
    		typedef typename set<T>::iterator iterator;
    		multimap<pair<Key_1,Key_2>,iterator> m;
    		multimap<Key_1,iterator> m_key_1;
    		multimap<Key_2,iterator> m_key_2;	
    		typedef typename multimap<pair<Key_1,Key_2>,iterator>::iterator iterator_0;
    		typedef typename multimap<Key_1,iterator>::iterator iterator_1;
    		typedef typename multimap<Key_2,iterator>::iterator iterator_2;
    
    	public:
    		void insert( const Key_1& k1, const Key_2& k2, const T& value )
    		{
    			const auto it = values.insert( value ).first;
    			m.insert( make_pair(make_pair(k1,k2),it) );
    			m_key_1.insert( make_pair(k1,it) );
    			m_key_2.insert( make_pair(k2,it) );
    		}
    
    		pair<iterator_1,iterator_1> find( const Key_1& key ) { return m_key_1.equal_range( key ); }
    		pair<iterator_2,iterator_2> find( const Key_2& key ) { return m_key_2.equal_range( key ); }
    
    		iterator_0 begin() { return ::begin(m); }
    		iterator_0 end()   { return ::end(m);   }
    };
    
    int main()
    {
    	multikey_map<int,char,string> m;
    
    	m.insert( 1, 'A', "O1" );
    	m.insert( 1, 'B', "O2" );
    	m.insert( 1, 'E', "O3" );
    	m.insert( 2, 'B', "O4" );
    	m.insert( 3, 'B', "O5" );
    	m.insert( 4, 'A', "O6" );
    	m.insert( 4, 'E', "O7" );
    
    	for(const auto& elem : m)
    	{
    		auto key_1 = elem.first.first;
    		auto key_2 = elem.first.second;
    		auto value = *(elem.second);
    		cout << key_1 << " | " << key_2 << " = " << value << '\n';
    	}
    
    	{
    		auto range = m.find( 1 );
    		for(auto it=range.first; it!=range.second; ++it)
    		{
    			cout << it->first << " = " << *(it->second) << '\n';
    		}
    	}
    
    	{
    		auto range = m.find( 'A' );
    		for(auto it=range.first; it!=range.second; ++it)
    		{
    			cout << it->first << " = " << *(it->second) << '\n';
    		}
    	}
    }
    

Log in to reply