Map mit zwei Keys und Joker

Johnny123

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?

Johnny123

10k-100k würde ich sagen.

Johnny123

10k-100k würde ich sagen.

Th69

Du könntest mal den Boost Container MultiIndex ausprobieren.

randa

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.

Belli

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?

Johnny123

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';
		}
	}
}