C / C ++: commutateur pour les non-entiers

Question

Souvent j'ai besoin de choisir quoi faire en fonction de la valeur de non-POD élément constant, quelque chose comme ceci:

switch( str ) {
  case "foo": ...
  case "bar": ...
  default:    ...
}

Malheureusement, switch peut être utilisé uniquement avec des entiers: error: switch quantity not an integer.

Les plus triviaux de la façon de mettre en œuvre une telle chose est d'avoir une séquence de ifs:

if( str == "foo" )      ...
else if( str == "bar" ) ...
else                    ...

Mais cette solution a l'air sale, et le prix est de O(n), où n est le nombre de cas, alors que ce morceau de code pourrait coûter O(log n) dans le pire des cas avec une recherche binaire.

À l'aide de certaines données des structures (comme les Cartes), il pourrait être possible d'obtenir un nombre entier représentant la chaîne ( O(log n) ), et ensuite utiliser un O(1) switch, ou l'on pourrait mettre en œuvre un binaire statique trier par imbrication ifs dans le droit chemin, mais encore ces hacks exigerait beaucoup de codage, rendant le tout plus complexe et plus difficile à maintenir.

Quelle est la meilleure façon de le faire? (rapide, propre et simple, comme l' switch déclaration est)

Answer 1

À l'aide de quelques méchants macro et le modèle de la magie, il est possible d'obtenir un déroulé de recherche binaire à compile-time avec de jolies syntaxe -- mais les MATCHES ("cas") doivent être triés: fastmatch.h

NEWMATCH
MATCH("asd")
  some c++ code
MATCH("bqr")
  ... the buffer for the match is in _buf
MATCH("zzz")
  ...  user.YOURSTUFF 
/*ELSE 
  optional
*/
ENDMATCH(xy_match)

Cela va générer (à peu près) une fonction bool xy_match(char *&_buf,T &user), de sorte qu'il doit être au niveau externe. Appel par exemple avec:

xy_match("bqr",youruserdata);

Et l' breaks sont implicites, vous ne pouvez pas tomber-thru. Il n'est également pas fortement documenté, désolé. Mais vous trouverez qu'il ya un peu plus de l'utilisation des possibilités, un coup d'oeil. REMARQUE: testé Uniquement avec g++.

Mise À Jour De C++11:

Les Lambdas et initializier liste de rendre les choses beaucoup plus joli (pas de macros impliqué!):

#include <utility>
#include <algorithm>
#include <initializer_list>

template <typename KeyType,typename FunPtrType,typename Comp>
void Switch(const KeyType &value,std::initializer_list<std::pair<const KeyType,FunPtrType>> sws,Comp comp) {
  typedef std::pair<const KeyType &,FunPtrType> KVT;
  auto cmp=[&comp](const KVT &a,const KVT &b){ return comp(a.first,b.first); };
  auto val=KVT(value,FunPtrType());
  auto r=std::lower_bound(sws.begin(),sws.end(),val,cmp);
  if ( (r!=sws.end())&&(!cmp(val,*r)) ) {
    r->second();
  } // else: not found
}

#include <string.h>
#include <stdio.h>
int main()
{
  Switch<const char *,void (*)()>("ger",{ // sorted:                      
    {"asdf",[]{ printf("0\n"); }},
    {"bde",[]{ printf("1\n"); }},
    {"ger",[]{ printf("2\n"); }}
  },[](const char *a,const char *b){ return strcmp(a,b)<0;});           
  return 0;
}

C'est l'idée. Une implémentation plus complète peut être trouvée ici: commutateur.hpp.

Answer 2

En C++, vous pouvez obtenir de l' O(lg n) de la performance en ayant une std::map<std::string, functionPointerType>. (En C, vous pourriez mettre en œuvre ce qui était essentiellement le même, mais il serait plus difficile) retirer le droit de pointeur de fonction à l'aide de std::map<k, v>::find, et d'appeler le pointeur. Bien sûr, cela ne va pas être aussi simple que d'une langue prise en charge de l'instruction switch. D'autre part, si vous avez assez d'éléments qu'il va y avoir une énorme différence entre O(n) et O(lg n), c'est probablement une indication que vous devez aller pour un design différent en premier lieu.

Personnellement, j'ai toujours trouvé le ELSEIF chaîne plus lisible de toute façon.

Answer 3

Vous pouvez y arriver sans utiliser aucune carte ou unordered_map comme ci-dessous. Comparez seul le premier caractère pour identifier quelle chaîne. Si plusieurs correspondances, vous pouvez alors utiliser la chaîne if / else dans cette instruction case. Le nombre de comparaisons sera grandement réduit si pas plusieurs chaînes commençant par la même lettre.

 char *str = "foo";
switch(*str)
{
case 'f':
    //do something for foo
    cout<<"Foo";
    break;
case 'b':
    //do something for bar
    break;
case 'c':
    if(strcmp(str, "cat") == 0)
    {
        //do something for cat
    }
    else if(strcmp(str, "camel") == 0)
    {
        //do something for camel
    }
}
 

Cela semble être une solution optimale sans aucun coût, même si ce n’est pas standard.

Answer 4

Utiliser un if...else block. Vous n'avez pas vraiment besoin d'une raison impérieuse de ne pas, en plus de ne pas être joli à regarder, et l' if...else bloc est le mostr solution simple et efficace.

Tout le reste nécessite un code supplémentaire qui comme le disent les disent augmente la complexité. Et il se déplace à la laideur d'ailleurs. Mais à un certain niveau, une comparaison de chaîne doit encore arriver. Maintenant, vous avez juste couvert avec plus de code.

Vous pourriez gagner quelques augmentations de rendement par l'utilisation d'une carte ou d'un hachage de la carte, mais vous pouvez également gagner similaire si ce n'est mieux gains en choisissant simplement une smart afin d'évaluer votre if...else blocs. Et de passer à une carte pour des raisons de performance est vraiment prématuré de la micro-optimisation.

Answer 5

En C, il existe deux solutions communes. La première est de garder vos mots-clés dans un tableau trié, dire

typedef struct Keyword {
    const char *word;
    int         sub;
    int         type;
} Keyword;

Keyword keywords[] ={   /* keep sorted: binary searched */
    { "BEGIN", XBEGIN, XBEGIN },
    { "END",   XEND,   XEND },
    { "NF",    VARNF,  VARNF },
    { "atan2", FATAN,  BLTIN },
    ...
};

et faire une recherche binaire sur eux. Le précédent est directement à partir du code source de awk par C le grand maître de Brian W. Kernighan.

L'autre solution, qui est en O(min(m, n)) si n est la longueur de votre chaîne d'entrée et m la longueur du plus long mot-clé, est d'utiliser un finite-state solution comme une Lex programme.