Le prestazioni hanno due parti:
- Fai meno lavoro possibile.
- Che lavoro fai, fai il più rapidamente possibile.
Qui la seconda parte può essere indirizzata abbastanza rapidamente: non utilizzare dynamic_cast , vedremo modi per evitarlo in un minuto. Non costruire lo stesso oggetto più e più volte. Per lo meno, vogliamo qualcosa di simile:
template <class TYPE>
A* search(TYPE const& expected) {
static_assert( TYPE is subclass of A );
for (TYPE* obj : magically_get_eligible_objects<TYPE>()) {
if (obj && (*obj == expected))
return obj;
}
return nullptr;
}
In C ++, i modelli e il polimorfismo non si adattano affatto bene. Non ci sarà una soluzione elegante e sicura per il tipo a magically_get_eligible_objects() . Ma se scriviamo il codice corretto possiamo prendere scorciatoie e violare il sistema di tipo C ++ in qualche modo in sicurezza. Per il resto di questa risposta, solo i TIPI di foglie sono rilevanti. Anche il tipo A* potrebbe essere void* .
Poiché conosci sempre il TIPO per una query, puoi suddividere gli oggetti per tipo. Non è necessario memorizzarli in una singola struttura dati. Ciò contribuirà a ridurre lo spazio di ricerca se la popolazione di oggetti è ben distribuita su più tipi: se al massimo il 30% degli oggetti ha lo stesso tipo, anche il tempo peggiore per una ricerca è sceso al 30% (più sovraccarico).
Per questo partizionamento puoi usare map<type_index, vector<A*>> o multimap<type_index, A*> nella condizione in cui usi type_index(typeid(obj)) di un oggetto come chiave per inserire, eliminare e cercare oggetti o intervalli di oggetti. Quando si ottengono iteratori o raccolte su un numero di oggetti che sono nominalmente di tipo A ma si conosce il loro TIPO effettivo, allora è possibile * tossire * reinterpret_cast delle raccolte. Dal momento che stai memorizzando solo i puntatori, questo dovrebbe essere sicuro nella pratica. Per i singoli puntatori puoi utilizzare static_cast in sicurezza.
Nota: se tutti gli oggetti hanno una costante name o altri dati che sono conosciuti da tutte ricerche, allora la chiave può essere un tuple<type_index, NameType> invece che dovrebbe portare ad un partizionamento sufficientemente buono . Continuerò a pensare che non sia così.
Probabilmente, potresti usare una struttura dati tuple<vector<TYPE1*>, vector<TYPE2*>, ..., vector<TYPEn*>> invece e cercare le partizioni per tipo. Questo evita alcuni cast ma è (a parte quella sicurezza di tipo e potenzialmente un po 'di performance di runtime) non fondamentalmente superiore a map<type_index, vector<void*>> . Questo rende le operazioni polimorfiche (come l'inserimento di un elemento in cui il TYPE non è noto) molto più difficile.
All'interno di una partizione, gli oggetti sarebbero ancora non ordinati, richiedendo la scansione lineare. Se i TYPE specifici hanno proprietà più forti, avremmo bisogno di introdurre un tipo di partizione personalizzato che possa essere specializzato per i singoli TIPI.
Avremmo bisogno di una partizione di base astratta per la compilazione del contenitore della partizione, qualcosa del tipo:
class BasePartition {
public:
virtual void insert(void*) = 0;
virtual void* search_by_name(NameType const&) = 0;
virtual void* search_by_expected(void*) = 0;
};
Quindi una classe template che fa automaticamente riferimento a un vettore non isolato, ma potrebbe essere specializzata per strutture dati migliori:
template<class TYPE>
class Partition : BasePartition {
vector<TYPE*> objects;
public:
void insert(void* obj) override {
objects.push_back(static_cast<TYPE*>(obj));
}
void* search_by_name(NameType const& name) override { ... }
void* search_by_expected(void* untyped_expected) override {
// may prefer dynamic_cast for more defensive code
TYPE* untyped_expected = static_cast<TYPE*>(untyped_expected);
...
}
};
Potremmo quindi avere un contenitore map<type_index, unique_ptr<BasePartition>> partitions . Dato un BasePartition* partition per il TYPE corretto, la funzione search() potrebbe quindi essere semplificata in
// partition casts internally
return static_cast<TYPE*>(partition->search_by_expected(&expected));
Possiamo quindi specializzare il modello Partition per i tipi in cui è possibile una ricerca più efficiente. Per esempio. se è possibile ordinare un tipo, potremmo utilizzare set anziché vector . Puoi anche conservare unordered_map s aggiuntivo per indicizzare gli oggetti con alcune proprietà, ad es. per nome. Se l'utilizzo della memoria aggiuntiva è un compromesso valido dipende dalla tua applicazione.