C ++ - Общее программирование - Выбор типа - PullRequest
Новая
       31

C ++ - Общее программирование - Выбор типа

0 голосов
/ 24 июня 2009

Следующий фрагмент возвращает следующую наивысшую степень двух для (предполагаемого беззнакового) целого числа типа T. Он делает это путем многократного сдвига битов.

Для всех намерений и целей беззнаковый тип i, используемый в цикле сдвига битов, является достаточно большим, чтобы представлять (номинально) 65536 битовых чисел. Таким образом, практически можно оставить все как есть. 

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

Чтобы выполнить профессиональную работу, тип счетчика циклов следует выбирать во время компиляции, чтобы он гарантировал возможность расширения до sizeof (T) * 8 без переполнения.

Можно ли это сделать во время компиляции, используя std :: numeric_traits? Если так, то как?

Концептуально я хотел бы написать что-то вроде: 

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;
...

На основании приведенных ниже обсуждений я решил добавить следующий контекст.

Другими словами:

Как мы можем гарантировать выбор эффективных (только таких больших, как они должны быть) и подходящих типов для внутренней работы кода шаблона во время компиляции? Если мы обнаружим, что используем конкретные типы в коде шаблона, мы можем делать непреднамеренные предположения о типах шаблонов через потенциально непрозрачный маршрут.

Например, если мы будем придерживаться (скажем) значения int для счетчика, все будет работать нормально, пока кто-то не использует код шаблона в своей библиотеке bigint. Это может представлять целые числа с большим количеством двоичных цифр, чем может быть представлено int. Должны ли мы поэтому сделать тип unsigned long long? Конечно, это только задерживает проблему (хотя и надолго)? В этом решении есть оттенки «640K - достаточно большие для всех» или статические размеры массивов.

Очевидный, но несколько неэффективный выбор в этом случае состоит в том, чтобы установить тип счетчика таким же, как тип числа k. Это (в принципе) неэффективно, так как мы только требуем, чтобы счетчик мог представлять число, соответствующее количеству битов k. Может случиться так, что в других ситуациях это неправильно.

А как насчет общего случая? Похоже, что метапрограммирование является подходящим подходом. Как сохранить это в здравом уме? Возможно, формально требование состоит в том, чтобы функция времени компиляции отображала (потенциально производные) требования абстрактных типов на типы.

Возможно, это работа для YABL (еще одна библиотека повышения)!

[Извинения за бессвязные слова]

Ответы [ 5 ]

1 голос
/ 24 июня 2009

На самом деле, вы правы.

Но на самом деле, если ваш T будет 128-битным, наибольшее количество операций сдвига будет 127, аккуратно вписываясь в char ...

Так вы не слишком перегружаете тип переменной цикла? (Может быть из-за оператора сдвига, то есть обычного приращения, как указано litb)

1 голос
/ 24 июня 2009

Я полагаю, вы хотели написать свой цикл как 

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

Int может по крайней мере хранить значения до 2^15-1, что более чем достаточно для этого. Тем не менее, вот как я это делаю 

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

Вы можете сделать это и с unsigned long long, если у вас есть этот тип в вашем компиляторе.

0 голосов
/ 24 июня 2009

Вы можете использовать метапрограммирование: 

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;
0 голосов
/ 24 июня 2009

Это можно сделать с помощью реализации черт. Примерно так: 

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

Пожалуйста, прости меня, если я неправильно понял синтаксис, мне всегда нужно искать синтаксис шаблона. Общая идея здесь.

0 голосов
/ 24 июня 2009

Проверьте на статические утверждения , это может быть решением вашей проблемы. 

#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
...