Contenitore per le ricerche di database-like
-
01-10-2019 - |
Domanda
sto cercando un po 'di STL, spinta, o un contenitore simile a utilizzare lo stesso modo in cui gli indici sono utilizzati in banche dati per la ricerca di record utilizzando una query come questa:
select * from table1 where field1 starting with 'X';
o
select * from table1 where field1 like 'X%';
Avevo pensato di usare std :: map, ma non posso perché ho bisogno di cercare per i campi che "iniziano con" un testo, e non quelli che sono "uguale a". Accanto a questo, ho bisogno di lavorare su più campi (ogni "record" dispone di 6 campi, per esempio), quindi avrei bisogno di uno std :: map separata per ciascuno di essi.
ho potuto creare un vettore ordinato o una lista e usare la ricerca binaria (rompendo il set in 2 in ogni fase leggendo l'elemento al centro e vedere se è più o meno di 'X'), ma mi chiedo se non v'è alcuni container ready-made ho potuto usare senza reinventare la ruota?
Soluzione
Boost.Multi-Index permette di gestire con diversi indice e implementa l'inferiore limite come per std :: set / carta. Sarà necessario selezionare l'indice corrispondente al campo e poi fare come se fosse una mappa o di un insieme.
Avanti segue una funzione generica che potrebbe essere utilizzato per ottenere un paio di iteratori, il pugno alla prima voce a partire da un determinato prefisso, il secondo il primo elemento a partire dal prossimo prefisso, ovvero la fine della ricerca
template <typename SortedAssociateveContainer>
std::pair<typename SortedAssociateveContainer::iterator,
typename SortedAssociateveContainer::iterator>
starts_with(
SortedAssociateveContainer const& coll,
typename SortedAssociateveContainer::key_type const& k)
{
return make_pair(coll.lower_bound(k),
coll.lower_bound(next_prefix(k));
}
dove
- next_prefix ottiene il prefisso successiva utilizzando ordine lessicografico basato sul comparatore SortedAssociateveContainer (ovviamente questa funzione necessita più argomenti essere completamente generico, vedere la domanda ).
Il risultato di starts_with
può essere utilizzato su qualsiasi algoritmo di gamma (vedi Boost.Range )
Altri suggerimenti
std::map
va bene, o std::set
se non ci sono dati diversi stringa. Passare il tuo stringa di prefisso in lower_bound
per ottenere la prima stringa che ordina in corrispondenza o dopo quel punto. Poi iterate in avanti attraverso la mappa fino a colpire alla fine o trova un elemento che non inizia con il prefisso.