dendibakh Sep 6 2013 at 10:27

Вычисление максимального числа в массиве на этапе компиляции

3 min

7.9K

Здравствуй хабр!

Не так давно понадобилось вычислить максимальную длину из нескольких заданных строк на этапе компиляции. Нужно выделить память под массив char[], так чтобы в нем уместилась любая строка из заданных. Логично предположить, что если система спроектирована хорошо, никаких вычислений на этапе компиляции не нужно, можно воспользоваться динамическим выделением используя std::auto_ptr или std::string, но это не тот случай. Структура в которой хранится буфер char[] должна быть POD-типом.

По сути задача сводится к определению максимального числа в массиве на этапе компиляции. В данном топике я покажу как это сделать в стандарте c++03 и c++11. В ходе поиска решений нашел две статьи, которые помогли мне решить проблему: habrahabr.ru/post/166201, habrahabr.ru/post/38622.

Итак, чтобы обойти все заданные строки, сложим их в массив:

const char str1[] = "Anna";
const char str2[] = "Denis";
const char str3[] = "Vladimir";
const char str4[] = "Alexey";

const char *arr[] = { str1, str2, str3, str4 };

Теперь, sizeof(arr) вернет 16, а sizeof(arr[2]) вернет 4. Увы, мы потеряли информацию о размере строк в каждом элементе массива arr. Трюк с тем чтобы положить результаты sizeof каждой строки в массив тоже не прокатит, так как на этапе компиляции не разрешены операции разыменовывания указателей. Вообщем нужно искать что-то помощнее обычных массивов…
Решение данной проблемы – это сделать эмуляцию массива с помощью структур. Сложим длины всех строк в отдельные структуры и свяжем их с помощью Loki::TypeList.

struct str_1 { static const int size = sizeof(str1); };
struct str_2 { static const int size = sizeof(str2); };
struct str_3 { static const int size = sizeof(str3); };
struct str_4 { static const int size = sizeof(str4); };
                                                                
typedef LOKI_TYPELIST_4(str_1, str_2, str_3, str_4) List;

Теперь мы можем обойти данный список типов и у каждого из них выдернуть размер.

Итоговый вариант с++03

struct str_1 { static const int size = sizeof(str1); };
struct str_2 { static const int size = sizeof(str2); };
struct str_3 { static const int size = sizeof(str3); };
struct str_4 { static const int size = sizeof(str4); };
                                                                
typedef LOKI_TYPELIST_4(str_1, str_2, str_3, str_4) List;       

#define GetMaxLen(TypeList) \
\
template<class Cur_Type> \
struct len               \
{                        \
    static const int cur_size = Cur_Type::Head::size;                                   \
    static const int next_size = len<Cur_Type::Tail>::max_size;                         \
    static const int max_size = cur_size > next_size ? cur_size : next_size ;           \
};                                                                                      \
                                                                                        \
template<>                                                                              \
struct len<NullType>                                                                    \
{                                                                                       \
    static const int max_size = 0;                                                      \
};                                                                                      \
                                                                                        \
static const int ml = len<TypeList>::max_size;                                          \

GetMaxLen(List);

// в *.cpp
// LOKI_STATIC_CHECK((ml == sizeof(str3)), size_is_wrong);

Данный вариант не самый удобный, так как такую структуру легко поддерживать при относительно небольшом количестве строк. Однако с увеличением данного количества существует вероятность просто забыть добавить соответствующую структуру для строки.
На стандарте c++11 получается все намного красивее и удобнее. Плюс не нужно «извращаться» со структурами и списками типов. Нам разрешено разыменовывать указатели, но только constexpr и внутри constexpr функции.

Итоговый вариант с++11

constexpr const char str1[] = "Anna";
constexpr const char str2[] = "Denis";
constexpr const char str3[] = "Vladimir";
constexpr const char str4[] = "Alexey";

constexpr const char *arr[] = { str1, str2, str3, str4 };

#define GetMaxLenght(array) \
constexpr unsigned char str_len(const char* const str) \
{\
   return *str ? (1 + str_len(str + 1)) : 0;\
}\
\
template <int index> \
struct MaxLenght\
{\
    static const int prev_size = MaxLenght<index-1>::max_size;\
    static const int cur_size = str_len(array[index]);\
    static const int max_size = cur_size > prev_size ? cur_size : prev_size;\
};\
\
template <>\
struct MaxLenght<-1>\
{\
    static const int max_size = 0;\
};\
static const int AmountStr = sizeof(array) / sizeof(array[0]);\
static const int array##_max_size = MaxLenght<AmountStr-1>::max_size;
GetMaxLenght(arr);

//   в *.cpp
//   static_assert((arr_max_size == 8), "Error");

P.S. Надеюсь данная статья кому-то поможет.
P.P.S. Буду рад, если кто-то предложит решение с помощью boost или еще каких-либо инструментов.

Tags:

Hubs: