C++ - Programmation générique - Sélection du type

Question

Le fragment suivant renvoie la deuxième puissance la plus élevée de deux pour un entier (supposé non signé) de type T. Il le fait en déplaçant les bits de façon répétée. Pour toutes fins utiles, le type non signé utilisé dans la boucle de décalage de bits est suffisamment grand pour représenter un nombre (nominalement) de 65 536 bits. Pratiquement donc c'est bien de le laisser tel quel.

template <class T> 
T supremum_2(T k) { 
    if (k == T(0)) return T(1); 
    k--; 
    for (int i=1; i<sizeof(T)*8; i++) k |= k >> i; 
    return k+1; 
} 

Pour faire un travail professionnel, le type de compteur de boucle doit être choisie au moment de la compilation afin qu'il garantit de pouvoir couvrir jusqu'à sizeof (T) * 8 sans trop-plein. Cela peut-il être fait à la compilation en utilisant std :: numeric_traits?

Si c'est le cas, comment?

Conceptuellement Je voudrais pouvoir écrire quelque chose comme:

typedef unsigned_type_that_can_represent<sizeof(T)*8> counter_type; 

... 
... 

for (counter_type i(1); i<sizeof(T)*8; i<<=1) k = k | k >> i; 
... 

Sur la base des discussions ci-dessous j'ai décidé d'ajouter le contexte suivant.

Autrement dit:

Comment pouvons-nous garantir pour sélectionner efficace (seulement aussi grand que ils ont besoin d'être) et les types appropriés pour le fonctionnement interne du code du modèle au moment de la compilation? Si nous nous trouvons en utilisant des types concrets dans le code de modèle nous pouvons faire des suppositions par inadvertance au sujet des types des calibres par l'intermédiaire d'une route potentiellement opaque. Par exemple, si nous devions coller (par exemple) un int pour le compteur, tout ira bien jusqu'à ce que quelqu'un utilise le code du template avec sa bibliothèque bigint. Cela pourrait représenter des entiers avec plus de chiffres binaires que ce qui peut être représenté par un int. Devrions-nous donc faire le type non signé longtemps? Cela ne fait que retarder le problème (mais pour longtemps)? Il y a des nuances de "640K - assez grand pour tout le monde" ou des tailles de tableaux statiques sur cette solution.

Le choix évident, mais quelque peu inefficace, dans ce cas est de définir le type du compteur comme étant le même que le type du nombre k. Il est (en principe) inefficace puisque nous demandons seulement que le compteur puisse représenter un nombre correspondant au nombre de bits de k. Il se peut que pour d'autres situations, ce soit la mauvaise chose à assumer.

Qu'en est-il du cas général? Il semble que la méta-programmation soit une approche appropriée. Comment garder ce "sens"? Peut-être, formellement, l'exigence est pour une fonction de compilation de mapper des exigences de type abstrait (potentiellement dérivées) sur les types.

Peut-être que c'est un travail pour YABL (Yet Another Boost Library)!

[Toutes mes excuses pour décousu]

Answer 1

Vérifiez sur static asserts, qui pourrait être une solution à votre problème.

#include <climits> 
#include <cwchar> 
#include <limits> 
#include <boost/static_assert.hpp> 

namespace my_conditions { 

    BOOST_STATIC_ASSERT(std::numeric_limits<int>::digits >= 32); 
    BOOST_STATIC_ASSERT(WCHAR_MIN >= 0); 

} // namespace my_conditions 

Answer 2

Vous pouvez utiliser méta proramming:

template <bool g, typename T, typename E> 
struct IF { 
    typedef T RET; 
}; 

template < typename T, typename E> 
struct IF<false, T, E> { 
    typedef E RET; 
}; 

// if sizeof(int) < sizeof(long) then use long else use int 
IF< sizeof(int)<sizeof(long), long, int>::RET i; 

Answer 3

Cela peut être fait en utilisant une implémentation de traits.Quelque chose comme ceci:

// base type for template 
template <class T> 
struct counter_type 
{ 
}; 

// specialisation for unsigned integer 
template <> 
struct counter_type <unsigned> 
{ 
    typedef unsigned long long value_type; // or whatever 
}; 

template <class T> 
T supremum_2(T k) { 
    if (k == T(0)) return T(1); 
    k--; 
    /* Determined by repeated bit shifting. */ 
    for (counter_type<T>::value_type i=1; i<sizeof(T)*8; i<<=1) k = k | k >> i; 
    return k+1; 
} 

S'il vous plaît pardonnez-moi si je reçois la syntaxe mal, je dois toujours regarder la syntaxe du modèle. L'idée générale est ici.

Answer 4

Je crois que vous vouliez écrire votre boucle comme

for (int i=1; i<sizeof(T)*8; i++) k |= k >> i; 
return k+1; 

Un int peut au moins les valeurs de stocker jusqu'à 2^15-1, qui est plus que suffisant pour cela. Quoi qu'il en soit, voici comment je le fais

template<int N, bool B8 = (N>8), 
       bool B16 = (N>16), 
       bool B32 = (N>32)> 
struct select_t; 

template<int N> 
struct select_t<N, false, false, false> { typedef unsigned char type; }; 

template<int N> 
struct select_t<N, true, false, false> { typedef unsigned short type; }; 

template<int N> 
struct select_t<N, true, true, false> { typedef unsigned long type; }; 

int main() { select_t<32>::type i = 0; } // unsigned long 

Vous pourriez le faire avec unsigned long long aussi, si vous arrive d'avoir ce type disponible dans votre compilateur.

Answer 5

En fait, vous avez raison.

Mais en réalité, si votre T serait 128 bits, le plus grand nombre d'opérations de changement serait 127, le montage proprement un char ...

ne sont donc pas vous over-engineering du type variable en boucle une bit? (Peut être dû à l'incrément de l'opérateur de décalage i.s.o., comme indiqué par litb)