Contenitore per le ricerche di database-like

Question

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?

Answer 1

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 )

Answer 2

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.