エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

ソート済みの定数配列

後から拡張もせず、参照するだけなので定数配列で充分なんだけど、要素はソートされていてほしい…というときのために。
本当はコンパイル時に要素がソートされるといいんですが、思いつかなかったので次善の策として。


2009/06/16 訂正:operator []constになってませんでした。「定数」とか言っておきながらconstになってなかったら定数オブジェクトとして扱えないだろうに。


以下コード。

// ConstSortedArray.h

#ifndef CONSTSORTEDARRAY_H
#define CONSTSORTEDARRAY_H

#include "qsort.h"

#include <stdexcept>
#include <cassert>

namespace emattsan
{

template<typename T, int N>
class ConstSortedArray
{
public:
    struct Elem
    {
        const T* value;

        bool operator <  (const Elem& rhs) const
        {
            assert((this->value != 0) && (rhs.value != 0));
            return (*this->value < *rhs.value);
        }
    };

    explicit ConstSortedArray(const T (&array)[N])
    {
        for(int i = 0; i < N; ++i)
        {
            elems_[i].value = array + i;
        }
        qsort(elems_, elems_ + N);
    }

    const T& operator [] (int index) const
    {
        if((0 <= index) && (index < N))
        {
            return *elems_[index].value;
        }
        else
        {
            throw std::out_of_range("ConstSortedArray::operator []");
        }
    }

private:
    Elem elems_[N];
};

} //namespace emattsan

#endif//CONSTSORTEDARRAY_H


テスト。

#include "ConstSortedArray.h"

#include <iostream>
#include <iterator>
#include <algorithm>

namespace
{
template<typename T, int N>
char (&numberof_(T (&array)[N]))[N];
}

#define numberof(array) sizeof(numberof_(array))

struct Item
{
    int         id;
    const char* name;
};

bool operator == (const Item& lhs, const Item& rhs)
{
    return lhs.id == rhs.id;
}

bool operator < (const Item& lhs, const Item& rhs)
{
    return lhs.id < rhs.id;
}

std::ostream& operator << (std::ostream& out, const Item& item)
{
    return out << "(" << item.id << "," << item.name << ")";
}

int main(int, char* [])
{
    static const int a[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };

    emattsan::ConstSortedArray<int, numberof(a)> sa(a);

    for(int i = 0; i < numberof(a); ++i)
    {
        std::cout << sa[i] << ' ';
    }
    std::cout << std::endl;

    static const Item items[] =
    {
        { 3, "three" },
        { 1, "one"   },
        { 4, "four"  },
        { 1, "one"   },
        { 5, "five"  },
        { 9, "nine"  },
        { 2, "two"   },
        { 6, "six"   },
        { 5, "five"  }
    };

    emattsan::ConstSortedArray<Item, numberof(items)> sortedItems(items);
 
    for(int i = 0; i < numberof(items); ++i)
    {
        std::cout << sortedItems[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}


QuickSortもヘッダファイルにしたものを再掲。

// qsort.h

#ifndef QSORT_H
#define QSORT_H

namespace emattsan
{

template<typename T>
void swap(T& lhs, T& rhs)
{
    T temp(lhs);
    lhs = rhs;
    rhs = temp;
}

template<typename T>
bool operator <= (const T& lhs, const T& rhs)
{
    return ! (rhs < lhs);
}

template<typename iterator_t>
void qsort(iterator_t begin, iterator_t end)
{
    if((end - begin) <= 1)
        return;

    iterator_t left  = begin;
    iterator_t right = end - 1;
    iterator_t pivot = end - 1;

    while(left < right)
    {
        while((left < right) && (*left < *pivot))
            ++left;
        if(left == right)
            break;

        while((left < right) && (*pivot <= *right))
            --right;
        if(left == right)
            break;

        swap(*left, *right);
    }

    swap(*left, *pivot);

    qsort(begin, left);
    qsort(left + 1, end);
}

} // namespace emattsan

#endif//QSORT_H