Container für Datenbank-ähnliche Suche

Question

Ich interessiere mich für einige STL, Boost, oder ähnliche Behälter die gleiche Art und Weise Indizes in Datenbanken verwendet werden, zu verwenden, für die Aufzeichnung mit einer Abfrage wie folgt zu:

select * from table1 where field1 starting with 'X';

oder

select * from table1 where field1 like 'X%';

Ich dachte über std :: map, aber ich kann nicht, weil ich brauche für Felder zu suchen, dass etwas Text „mit Start“, und nicht diejenigen, die „gleich“ sind. Außer, dass ich brauche es, um die Arbeit an mehreren Feldern (jeweils „record“ hat 6 Felder, zum Beispiel), so dass ich für jeden eine separate std :: map brauchen würde.

Ich konnte eine sortierte Vektor oder eine Liste erstellen und binäre Suche verwenden (Brechen des Satzes in 2 in jedem Schritt, indem das Element in der Mitte zu lesen und zu sehen, ob es mehr oder weniger als ‚X‘ ist), aber ich frage mich, ob es einige fertigen Behälter ich ohne das Rad neu erfinden verwenden könnte?

Answer 1

Boost.Multi-Index ermöglicht es Ihnen, mit mehreren Index und implementiert die lower_bound wie für std :: set / Karte zu verwalten. Sie müssen den Index entsprechend dem Feld auszuwählen und dann zu tun, als ob es sich um eine Karte oder ein Satz war.

Als nächstes eine generische Funktion folgt, die verwendet werden, um ein Paar von Iteratoren zu bekommen, die Faust auf das erste Element mit einem bestimmten Präfix beginnen, die zweite das erste Element mit dem nächsten Präfix beginnen, dh das Ende der Suche

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

Dabei steht

• next_prefix erhält den nächsten Präfix lexicographic Reihenfolge basierend auf dem SortedAssociateveContainer Komparator (natürlich diese Funktion mehr Argumente muss vollständig generisch sein, finden Sie in die Frage ).

Das Ergebnis starts_with kann auf einem beliebigen Bereich Algorithmus verwendet werden (siehe

Answer 2

std::map ist in Ordnung, oder std::set wenn es keine anderen Daten als die Zeichenfolge ist. Fahren Sie mit Präfixzeichenfolge in lower_bound den ersten String zu erhalten, die an oder nach diesem Zeitpunkt sortiert. Dann Iterierte vorwärts durch die Karte, bis Sie das Ende treffen oder ein Element finden, die nicht mit dem Präfix beginnt.

Answer 3

std::map ist in Ordnung, oder std::set wenn es keine anderen Daten als die Zeichenfolge ist. Fahren Sie mit Präfixzeichenfolge in lower_bound den ersten String zu erhalten, die an oder nach diesem Zeitpunkt sortiert. Dann Iterierte vorwärts durch die Karte, bis Sie das Ende treffen oder ein Element finden, die nicht mit dem Präfix beginnt.