Quick Sort at Compilation Time Using C++11 Variadic Templates

Quick sort at compilation time using C++11 variadic templates

Have you also looked at its memory consumption? Note that quicksort itself is worse than linear, with a quite bad worse case runtime. This multiplies with the worse than linear runtime behaviour of certain steps of template compilation and instantiation (sometimes those are exponentional). You should maybe graph your compiletime for various datasets to observe the real complexity class for your code. Usually template metaprogramming with such large datasets is not feasible.

Edit:
Out of curiosity I tried the code out and found that up until ~500 it follows roughly the formula pow(N*log(N),1.47)*0.0004+0.6 but then starts to get incredibly much slower, with 155 seconds for 700 items. Also at around that it starts eating very much ram (3GiB for 600) which leads me to the conclusion that for 1000 elements it will need more ram than most people have and will take hours to compile.

Further note that the code does not work when not every element is unique.

Sorting list of ints. TMP

Since C++ template system is known to be turing-complete, you can in principle compute everything that is computable at compile time. That includes sorting algorithms.

build and pass list of types to variadic templates

Big fat warning: don't do this.

The reason I'm saying, it'll change during the code. As you gradually add types, you'll end up defaultTypeList having multiple meanings in different places of the code.

That said... Can it be done? Of course,

#define DEFAULT_TYPE_LIST typelist<>()

// ...
#ifdef MACRO1
static constexpr auto macro1_prev_dtl = DEFAULT_TYPE_LIST;
#undef DEFAULT_TYPE_LIST
#define DEFAULT_TYPE_LIST concat(macro1_prev_dtl, typelist<Class2>())
#endif

// ...
#ifdef MACRO2
static constexpr auto macro2_prev_dtl = DEFAULT_TYPE_LIST;
#undef DEFAULT_TYPE_LIST
#define DEFAULT_TYPE_LIST concat(macro2_prev_dtl, typelist<Class3>())
#endif

... then use DEFAULT_TYPE_LIST wherever you'd like to access the current state of the list.

Sorting non-type template parameter pack in C++11 or C++1y?

I suppose you can use Boost MPL's sort "function": http://www.boost.org/doc/libs/1_51_0/libs/mpl/doc/refmanual/sort.html

Given a list of values as template parameters, plus a predicate (which defaults to less as is customary), it will produce a "copy" in sorted order. The claimed complexity is O(n log(n)) "on average", O(n^2) worst-case; making it similar to Quicksort (and in fact, it appears to actually use Quicksort).

You asked about this function's "internal architecture." About that, I surely have no idea, but given the maturity of Boost MPL and my prior experience using it, I'd say give it a try and if it does what you need, you'll probably find it about as satisfying as you find any other C++ template meta-programming.

Why does my variadic template argument verifier refuse to evaluate at compile time?

The perfect-forwarding is not-guilty.

As pointed by Caramiriel, you can't use a function parameter in a static_assert() test.

I know that the constructor is constexpr, but a constexpr constructor (like any other constexpr function) can be executed compile-time or run-time, according to the circumstances.

So a static_assert() test with values potentially known only run-time is an error.

Moreover, in your particular case

MyClass<5> b(1,2,3,4); 

you don't define b as constexpr so the compiler, even if can choose to execute it compile-time, usually execute it run-time.

If you want execute a static_assert() you have to make the values available compile time. The way I know is pass the values as template values. Unfortunately there isn't a way to explicit a template value for a contructor, so I see two possible ways

1) pass the vals... as class template parameters.

Something as follows (caution: code not tested)

 template<int MaxVal, int ... vals> class MyClass
 {
 public:
    constexpr MyClass ()
    {
       // verify at compile-time that all values in (vals) are <= MaxVal
       static_assert(returnZeroIffValuesAreNotTooBig<MaxVal>(vals...)==0,
                     "why doesn't this compile?");
    }
 };

MyClass<5, 1, 2, 3, 4>  b;

In this case you can also place the static_assert() in the body of the class, not necessarily in the body of the constructor.

2) pass the vals... as template parameter in a std::integer_sequence (available only starting from C++14, but is trivial substitute it with a custom class in C++11) constructor argument.

Something as follows (caution: code not tested)

 template<int MaxVal> class MyClass
 {
 public:
    template <int ... vals>
    constexpr MyClass (std::integer_sequence<int, vals...> const &)
    {
       // verify at compile-time that all values in (vals) are <= MaxVal
       static_assert(returnZeroIffValuesAreNotTooBig<MaxVal>(vals...)==0,
                     "why doesn't this compile?");
    }
 }; 

MyClass<5> b(std::integer_sequence<int, 1, 2, 3, 4>{});

How to form a string using variadic templates without recursion in c++ 11

You don't need to use recursion to make this work.

You can create fake array with expanding parameters pack when filling it:

template<class ... Args>
std::string makeString(Args...args){
    std::string s;
    int temp[] = { (s += toString(args),0)... }; // concatenation
    static_cast<void>(temp);
    return s;
}

for toString you provide overloads for handling all types you want.

For example:

template<class T>
std::string toString(T t){
    return std::to_string(t);   // for numbers 
}

std::string toString(const std::string& str){
    return str;
}

std::string toString(const char* str){
    return str;
}

Full demo

---

Hmm, you don't even use toString, version with ostringstream is:

template<class ... Args>
std::string makeString(Args&&...args){
    std::ostringstream os;
    int temp[] = { ((os << std::forward<Args>(args)),0)... };
    static_cast<void>(temp);
    return os.str();
}

C++11: Compile-time Array with Logarithmic Evaluation Depth

If what you're using in the code is a weird form of the indices trick, here's an implementation that has O(log N) instantiations:

// using aliases for cleaner syntax
template<class T> using Invoke = typename T::type;

template<unsigned...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<unsigned... I1, unsigned... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., (sizeof...(I1)+I2)...>{};

template<class S1, class S2>
using Concat = Invoke<concat<S1, S2>>;

template<unsigned N> struct gen_seq;
template<unsigned N> using GenSeq = Invoke<gen_seq<N>>;

template<unsigned N>
struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

template<> struct gen_seq<0> : seq<>{};
template<> struct gen_seq<1> : seq<0>{};

// example

template<unsigned... Is>
void f(seq<Is...>);

int main(){
  f(gen_seq<6>());
}

Live example.

Making a tuple-like compile-time linked-list with variadic templates

The primary template definition of TupleLite specifies that it requires at least one template argument, FirstType. Since that isn't what you want to express, provide a primary template defition which ends up also handling the empty case like this:

template <typename...>
class TupleLite{};

And one partial specializations:

template <typename FirstType, typename... OtherTypes>
class TupleLite<FirstType, OtherTypes...>
{
  public:
    FirstType type_;
    TupleLite<OtherTypes...> other_types_;
};

Coliru Demo.

EDIT : Thanks to Nikos for pointing out that the empty spec was not needed in this case.

---

Related Topics