Question

Je cherche une STL, coup de pouce, ou d'un conteneur similaire à utiliser le même index sont utilisés à des bases de données pour rechercher enregistrement à l'aide d'une requête comme ceci:

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

ou

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

Je pensais que sur l'utilisation std :: carte, mais je ne peux pas parce que je dois rechercher des champs « commençant par » un texte, et non ceux qui sont « égal à ». A côté de cela, j'ai besoin de travailler sur plusieurs champs (chaque « enregistrement » a 6 champs, par exemple), donc je besoin d'un std :: carte séparée pour chacun.

Je pourrais créer un vecteur de tri ou de liste et utiliser la recherche binaire (briser le jeu en 2 à chaque étape en lisant l'élément au milieu et voir si elle est plus ou moins « X »), mais je me demande s'il y a certains conteneurs ready-made je pouvais utiliser sans réinventer la roue?

Était-ce utile?

La solution

Boost.Multi-Index vous permet de gérer avec plusieurs index et met en œuvre les lower_bound que pour std :: set / carte. Vous devrez sélectionner l'index correspondant au champ, puis faire comme si elle était une carte ou un ensemble.

Ensuite suit une fonction générique qui pourrait être utilisé pour obtenir un couple de itérateurs, le poing au premier élément commençant par un préfixe donné, le second, le premier élément commençant par le préfixe suivant, à savoir la fin de la recherche

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

  • next_prefix obtient le préfixe suivant l'ordre lexicographique en fonction du comparateur SortedAssociateveContainer (bien sûr cette fonction a besoin de plus d'arguments pour être complètement générique, voir le question ).

Le résultat de starts_with peut être utilisé sur tout algorithme de plage (voir

Autres conseils

std::map est bien, ou std::set s'il n'y a pas de données autres que la chaîne. Passez votre chaîne de préfixe en lower_bound pour obtenir la première chaîne qui trie ou après ce moment-là. Puis itérer vers l'avant à travers la carte jusqu'à ce que vous appuyez sur la fin ou de trouver un élément qui ne commence pas par le préfixe.

scroll top