Compile-Time std::map

Daniel Keep daniel.keep.lists at gmail.com
Sat Apr 28 07:34:41 PDT 2007


NN wrote:
> Ok, from the beginning :)
> While writing I think all problems are solved, but I'm not sure.
> 
> I want to do binary search on any array:
> 
> int[] sorted_array = {1,2,3};
> binary_search(sorted_array, 1); // complexity O(log N)
> 
> But i can do it only if array is sorted.
> I want to write any array and sort it in compile time:
> 
> int[] sorted_array = compile_time_sort({3,2,1});
> 
> Is it possible ?

I haven't been able to test this yet since I haven't updated to DMD
1.014 yet.  Also, YES I know it's not exactly an efficient sort, but
it's at compile time, and if *this* works, getting quicksort to work
shouldn't be too hard.

T[] compile_time_sort(T)(T[] arr)
{
    if( arr.length == 0 || arr.length == 1 )
        return arr;
    else
        return insert_into(arr[0], compile_time_sort(arr[1..$]));
}

T[] insert_into(T)(T v, T[] arr)
{
    if( arr.length == 0 )
        return [v];
    else
    {
        if( v <= arr[0] )
            return [v] ~ arr;
        else
            return arr[0..1] ~ insert_into(v, arr[1..$]);
    }
}

int[] sorted_array = compile_time_sort([3,2,1]);

import std.stdio;

void main()
{
    writefln("%s", sorted_array);
}

-- 
int getRandomNumber()
{
    return 4; // chosen by fair dice roll.
              // guaranteed to be random.
}

http://xkcd.com/

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D
i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP  http://hackerkey.com/



More information about the Digitalmars-d mailing list