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