LINUX.ORG.RU

C++ сортировка произвольных типов.

 , ,


2

2

Как сравнивать произвольные типы? Точнее мне нужно их сортировать, но для этого достаточно научиться их сравнивать.

У меня есть некий темплейт, который принимает произвольное количество классов (окей, я могу менять эти классы, но лучше этого не делать).

foo<C1, C2, C3>
foo<C8, C4>

Я хочу, чтобы foo<C1, C3, C5>::type и foo<C5, C1, C3>::type был один и тот же тип Boo<C1, C2, C5>, порядок не важен, главное, чтобы он был всегда одинаковый.

Единственное решение, которая я вижу - это нумеровать каждый класс. Как нумеровать автоматически, я не знаю.

class C1 {
  constexpr static int value = 1;
}
class C2 {
  constexpr static int value = 2;
}
...

type_info::before почему-то не constexpr.

★★

Я хочу, чтобы foo<C1, C3, C5>::type и foo<C5, C1, C3>::type был один и тот же тип Boo<C1, C2, C5>,

не распарсил. Можно подробнее?

Progressive ()

Сравнивай по typeid (можешь брать хэш, если жалко времени).

E ★★★ ()
Ответ на: комментарий от Progressive

Мне нужно сортировать типы.

foo<int, float, double>::type // должно раскрываться в Boo<float, int, double>

foo<float, double, int>::type // должно раскрываться в Boo<float, int, double>

foo<double, int>::type // должно раскрываться в Boo<int, double>

Вместо float, double и int у меня свои типы: C1, C2 ... которые я могу менять.

Kuzy ★★ ()
Последнее исправление: Kuzy (всего исправлений: 1)
Ответ на: комментарий от E

Не constexpr. Если так, то можно юзать type_info::before, но он тоже не constexpr. Мне нужно это в параметр шаблона передавать.

Kuzy ★★ ()
Ответ на: комментарий от Kuzy

не представляю, как ты собрался их сортировать, но нумеровать можно если запилить traits-класс. Тогда не придется их менять.

Progressive ()
Ответ на: комментарий от Kuzy

Ты не понял. Это разные типы с точки зрения компилятора, настолько, что встроенными средствами ты их не сведёшь даже друг к другу. Чиселки твои ничем не помогут. Придётся проверять их эквивалентность n! функциями для каждого возможного (!) набора - либо пилить их вручную, либо сводить их рекурсивно к каким-то общим случаям, типа C<A, B> === C<B, A> и плясать отсюда, но получившийся бинарь будет раздут в такой же степени. А если у тебя десятки, сотни типов - это O(n^2) увеличение.

А можно проверять их эквивалентность какой-нибудь функцией в рантайме - на мой взгляд, это решение более эффективное. Можно, допустим, попытаться вычислить хэш typeid на этапе компиляции или взять __LINE__, если они в одном файле, составить множество и взять хэш от него - это если тебе очень-очень хочется избавиться от лишнего рантайма.

E ★★★ ()

как уже предложили.

использовать ароматы классов как префикс ключа

тогда в результате обычного sdt::sort у тя будет разделено упорядочены .

но вообще зачем в контейнере держать разные типы - так не угодно Страуструпу и Комитету.

qulinxao ★★☆ ()
Ответ на: комментарий от Progressive

представляю, как ты собрался их сортировать

boost::mpl::sort

но нумеровать можно если запилить traits-класс.

Как?

Kuzy ★★ ()
Ответ на: комментарий от E

О чем ты.

Придётся проверять их эквивалентность n! функциями для каждого возможного (!) набора - либо пилить их вручную

У тебя есть список.

[1, 3, 2, 4]
Как проверить эквивалентен ли он [1, 3, 2, 4]?! Полный перебор займет n! (!).

Теперь расскажи мне чем он отличается от:

foo<1, 3, 2, 4>

А потом, чем предыдущий от:

foo<C1::value, C3::value, C2::value, C4::value>

И наконец от:

foo<C1, C3, C2, C4>

Kuzy ★★ ()
Ответ на: комментарий от Kuzy

boost::mpl::sort

жесть

Как?

template <typename T> class NumberTrait
{
public:
  constexpr static int value = -1;
};

далее специализируй для каждого своего класса
потом юзай NumberTrait<твойкласс>::value

Progressive ()
Ответ на: комментарий от Progressive

Что-то все равно не понял, мне нужно что бы в каждом классе числа были разные.

Похоже я очень плохо сформулировал, то, что нужно.

Kuzy ★★ ()
Ответ на: комментарий от Kuzy

Что-то все равно не понял, мне нужно что бы в каждом классе числа были разные.

template<> class NumberTrain<C1>
{
public:
  constexpr static int value = 1;
};

template<> class NumberTrain<C2>
{
public:
  constexpr static int value = 2;
};

итд

Progressive ()
Ответ на: комментарий от E

Вообще с __LINE__ - норм идея, только они не в одном файле.

Kuzy ★★ ()
Ответ на: комментарий от Kuzy

Нестандартен и тоже работает в пределах одного файла. Можно, в принципе, объединить его с __LINE__, но всё равно не гарантирует, что где-то в другом файле на строчке 56 тоже не будет объявлен третий по счёту класс.

Можно сделать через traits и объявлять их все в одном файле, скажем, для всех используемых в проекте типов. Костыльно, но прокатит.

E ★★★ ()
Ответ на: комментарий от Kuzy

Похоже я очень плохо сформулировал, то, что нужно.

несомненно. для начала расскажи, чем не устроил std::sort

anonymous ()
Ответ на: комментарий от E

Нестандартен и тоже работает в пределах одного файла.

У меня работает с несколькими файлами нормально, у тебя нет?

Kuzy ★★ ()
Ответ на: комментарий от Kuzy

А у меня нет. В каждом препроцессированном файле (единице трансляции) счёт начинается заново.

E ★★★ ()
Ответ на: комментарий от E

единице трансляции

__LINE__ - именно номер строки в каждом файле, а не в простыне после препроцессора.

Kuzy ★★ ()

Хм, а если эти C1, C2 etc тоже будут инстансами шаблонов?

Miguel ★★★★★ ()
Ответ на: комментарий от Kuzy

Я не знаю, получится ли, но я бы попробовал поиграть с моментами инстанцирования шаблонов. То есть, завести какой-то шаблон INDEX<class C>, и сравнивать, какой из инстансов более ранний, INDEX<C1> или INDEX<C2>.

Шансов, имхо, при этом мало, но вдруг.

Miguel ★★★★★ ()
Ответ на: комментарий от Miguel

Вот вам и тьюринг-полнота шаблонов. буллшит :(

anonymous ()
Ответ на: комментарий от Miguel

А как узнать момент инстанса?

ТС-у - почитайте Вандервуда, если это можно сделать прямо то у него это есть;-)

А так, повесить на каждый класс целое число I, и рассматривать в качестве параметра 1<<I собранные через побитовые или.

AIv ★★★★★ ()
Ответ на: комментарий от AIv

А как узнать момент инстанса?

Никак. Но, может быть, удастся как-то понять, ЕСТЬ ли этот инстанс.

В общем, ИМХО, это дохлый номер, и даже если возможно, потребует сурового C++-fu.

Miguel ★★★★★ ()

Развлёкся вашей задачей, ниже реализация для количества типов <= 64, (по количеству битов в uint64_t), для общего случая шаблоны будут забористее. Идея простая: задать для каждого типа уникальное число [0..63] и через логическое ИЛИ просуммировать. Число есть порядковый номер типа в std::tuple Reference. Если сумма совпадает, значит и типы были те же, порядок неважен.

#include <tuple>
#include <type_traits>
#include <iostream>
#include <cstdint>


typedef std::tuple<int, float, bool, double> Reference;


template <bool Same, int I, typename T> struct IndexOfTypeRecursive;

template <int i, typename T>
struct IndexOfTypeRecursive<true, i, T>
{
	static constexpr int value = i;
};

template <int i, typename T>
struct IndexOfTypeRecursive<false, i, T>
{
	static_assert(i < std::tuple_size<Reference>::value, "No such type in Reference");
	static constexpr int value = IndexOfTypeRecursive<std::is_same<typename std::tuple_element<i + 1, Reference>::type, T>::value, i + 1, T>::value;
};

template <typename T>
struct IndexOfType
{
	static constexpr int value = IndexOfTypeRecursive<std::is_same<typename std::tuple_element<0, Reference>::type, T>::value, 0, T>::value;
};


template <int Size, typename... Types> struct SignatureForTypesImp;

template <>
struct SignatureForTypesImp<0>
{
	static constexpr std::uint64_t get(std::uint64_t s) { return s; }
};

template <int Size, typename T, typename... Types>
struct SignatureForTypesImp<Size, T, Types...>
{
	static constexpr std::uint64_t get(std::uint64_t s)
	{
		return SignatureForTypesImp<Size - 1, Types...>::get(s | (std::uint64_t(1) << IndexOfType<T>::value));
	}
};

template <typename... Types>
constexpr std::uint64_t signatureForTypes()
{
	return SignatureForTypesImp<sizeof...(Types), Types...>::get(0);
}


int main(int, char **)
{
	std::cout << "int, float: " << signatureForTypes<int, float>() << "\n";
	std::cout << "float, int: " << signatureForTypes<float, int>() << "\n";
	std::cout << "double, int, bool: " << signatureForTypes<double, int, bool>() << "\n";
	std::cout << "int, double, bool: " << signatureForTypes<int, double, bool>() << "\n";
	std::cout << "bool, int, double: " << signatureForTypes<bool, int, double>() << "\n";
	return 0;
}

Выхлоп:

int, float: 3
float, int: 3
double, int, bool: 13
int, double, bool: 13
bool, int, double: 13
Dendy ★★★★★ ()
Ответ на: комментарий от Miguel

Никак. Но, может быть, удастся как-то понять, ЕСТЬ ли этот инстанс.

Попытался сделать так, но не удалось, не знаю как определить.

template <int N>
struct help {};

template <>
struct help<0> {};

template <>
struct help<1> : help<0> {};


template <int N>
struct is_n {
	static constexpr bool value = std::is_base_of<help<N>, help<N + 1>>::value;
};

template <bool B, int N>
struct get_count {
	static constexpr int value = get_count<is_n<N>::value, N + 1>::value;
};

template <int N>
struct get_count<false, N> {
	static constexpr int value = N - 1;
};

// находит последний инстанс
const int tmp = get_count<true, 0>::value;

// не получается добавить новый.
// error: redefinition of 'help<1>'
template <>
struct help<get_count<true, 0>::value> : help<get_count<true, 0>::value + 1> {};

Нашел зубодробительный вариант для нахождения последней перегрузки фунуции: http://stackoverflow.com/questions/6166337/does-c-support-compile-time-counters

Kuzy ★★ ()
Ответ на: комментарий от Dendy

для общего случая шаблоны будут забористее

Я, в итоге, сделал метафункцию добавления нового элемента в список (тип, приоритет), типы повторяться не могут, если добавить тот же тип с приоритетом выше - он его заменит.

Почти прямая трансляция

add :: Eq a => (a, Integer) -> [(a, Integer)] -> [(a, Integer)]
add e [] = [e]
add (x, n) ((y, m) : xs) | x == y    = if m < n then add (x, n) xs
                                                else (y, m) : xs
                         | otherwise = if m < n then (y, m) : (add (x, n) xs)
                                                else (x, n) : (y, m) : xs

в

template <typename Element, typename List>
struct ordered_set_add {};

template <typename Element>
struct ordered_set_add<Element, nil> 
    : cons<Element, nil> {};

template <typename X, typename N, typename M, typename Tail>
struct ordered_set_add<cons<X, N>, cons<cons<X, M>, Tail>> 
    : if_<typename less<M, N>::type, ordered_set_add<cons<X, N>, Tail>
                                   , cons<cons<X, M>, Tail>> {};

template <typename X, typename Y, typename N, typename M, typename Tail>
struct ordered_set_add<cons<X, N>, cons<cons<Y, M>, Tail>> 
    : if_<typename less<M, N>::type, lazy<cons<cons<Y, M>, ordered_set_add<cons<X, N>, Tail>>>
                                   , cons<cons<X, N>, cons<cons<Y, M>, Tail>>> {};

Kuzy ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.