「CPP-assign-2009-06-10」の編集履歴（バックアップ）一覧はこちら
CPP-assign-2009-06-10 - (2009/06/12 (金) 13:55:08) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
*テンプレートやべえ
基数ソートと関係ないんですけど
#codehighlight(c++){{
template <class T>
class radixsort_list
{
public:
radixsort_list();
~radixsort_list();
//void input(std::vector<T>& arr);
void input(T *arr, int arr_length);
//void output();
friend std::ostream &operator<<(std::ostream &stream, radixsort_list<T> &obj)
{
// この下の行のイテレータの中のTでコンパイルエラー
for(std::vector<std::deque<T> >::iterator i = obj.data.begin();
i != obj.data.end(); ++i)
for(std::deque<T>::iterator j = i->begin();
j != i->end(); ++j)
stream << *j << std::endl;
return stream;
};
private:
std::vector<std::deque<T> > data, temp;
};
}}
と書くと
#codehighlight(){{
radixsort_byte.cpp: In function ‘std::ostream& operator<<(std::ostream&, radixsort_list<T>&)’:
radixsort_byte.cpp:18: error: expected `;' before ‘i’
radixsort_byte.cpp:19: error: ‘i’ was not declared in this scope
radixsort_byte.cpp:20: error: expected `;' before ‘j’
radixsort_byte.cpp:21: error: ‘j’ was not declared in this scope
radixsort_byte.cpp: In function ‘std::ostream& operator<<(std::ostream&, radixsort_list<unsigned int>&)’:
radixsort_byte.cpp:66: instantiated from here
radixsort_byte.cpp:18: error: dependent-name ‘std::vector::iterator’ is parsed as a non-type, but instantiation yields a type
radixsort_byte.cpp:18: note: say ‘typename std::vector::iterator’ if a type is meant
radixsort_byte.cpp:20: error: dependent-name ‘std::deque::iterator’ is parsed as a non-type, but instantiation yields a type
radixsort_byte.cpp:20: note: say ‘typename std::deque::iterator’ if a type is meant
}}
このようなエラーが吐かれる。しかたがないからTを実際に使うunsigned intと書き換えてるんだけど何の意味もない…しかたがないので
#codehighlight(c++){{
for(int i = 0; i < obj.data.size(); ++i)
for(int j = 0;j < obj.data[i].size(); ++j)
stream << data[i][j] << std::endl;
}}
と書くことに。
**救世主
@yuyarinに投げたところ解答をいただいたので記す。
***typename
>エラー嫁
エラーをよく見ると
>
say ‘typename std::deque::iterator’ if a type is meant
とある。つまり、typenameとしていすれば型名であることが示されるということ。結局答えは自明という……！鬱だしのう
***構造
STLのソートのようにイテレータ関数として実装せよとのこと、言われてみればそうなのでこれは書きかえるべき。どれくらいかと言えば実験一日潰すくらい。
以下全文。
#codehighlight(c++){{
#include <iostream>
#include <vector>
#include <deque>
#include <cstdlib>
#include <ctime>
#define LENGTH(x) (sizeof(x)/sizeof((x)[0]))
template <class T>
class radixsort_list
{
public:
radixsort_list();
~radixsort_list();
void input(T *arr, int arr_length);
friend std::ostream &operator<<(std::ostream &stream, radixsort_list<T> &obj)
{
for(int i=0; i<obj.data.size(); ++i)
for(int j=0; j<obj.data[i].size(); ++j)
stream << obj.data[i][j] << ',';
stream << std::endl;
return stream;
};
private:
std::vector<std::deque<T> > data, temp;
const static int SEG = 8;
};
template <class T>
radixsort_list<T>::radixsort_list(void)
{
}
template <class T>
radixsort_list<T>::~radixsort_list(void)
{
}
template <class T>
void radixsort_list<T>::input(T *arr, int arr_length)
{
const int seg_width = sizeof(T) * 8 / SEG;
T mask = (T)~(~0x0 << SEG);
data.resize(0x1 << SEG);
for(int i=0; i<arr_length; ++i)
data[arr[i] & mask].push_back(arr[i]);
mask <<= SEG;
for(int loop = 1; loop < seg_width; mask <<= SEG, ++loop)
{
temp.resize(0x1 << SEG);
for(int i=0; i < data.size(); ++i)
for(int j=0; j < data[i].size(); ++j)
temp[(data[i][j] & mask) >> (SEG * loop)].push_back(data[i][j]);
swap(data, temp);
temp.clear();
}
}
int main()
{
//unsigned int array[] = {31,41,59,26,53,58,97,93,23,84,62,64,33,83,27,95,02,88};
unsigned seed(time(NULL));
srand(seed);
std::cerr << "seed:" << seed << std::endl;
unsigned long array[10000];
for(int i=0; i < (int)LENGTH(array); ++i)
array[i] = (unsigned long)rand();
radixsort_list<unsigned long> *pSort;
pSort = new radixsort_list<unsigned long>;
pSort->input(array, LENGTH(array));
std::cout << *pSort;
delete pSort;
char str[] = "The quick brown fox jumps over a lazy dog.";
radixsort_list<char> *pSort2;
pSort2 = new radixsort_list<char>;
pSort2->input(str, LENGTH(str));
std::cout << *pSort2;
delete pSort2;
}
}}
*基数ソート
**テンプレートやべえ
解決したので簡単にまとめます。
#codehighlight(c++){{
template <class T>
class radixsort_list
{
public:
//略
friend std::ostream &operator<<(std::ostream &stream, radixsort_list<T> &obj)
{
//エラー出る。
for(std::vector<std::deque<T> >::iterator i = obj.data.begin();
i != obj.data.end(); ++i)
for(std::deque<T>::iterator j = i->begin();
j != i->end(); ++j)
stream << *j << std::endl;
return stream;
};
//略
};
}}
と書くと
#codehighlight(){{
radixsort_byte.cpp: In function ‘std::ostream& operator<<(std::ostream&, radixsort_list<T>&)’:
radixsort_byte.cpp:18: error: expected `;' before ‘i’
radixsort_byte.cpp:19: error: ‘i’ was not declared in this scope
radixsort_byte.cpp:20: error: expected `;' before ‘j’
radixsort_byte.cpp:21: error: ‘j’ was not declared in this scope
radixsort_byte.cpp: In function ‘std::ostream& operator<<(std::ostream&, radixsort_list<unsigned int>&)’:
radixsort_byte.cpp:66: instantiated from here
radixsort_byte.cpp:18: error: dependent-name ‘std::vector::iterator’ is parsed as a non-type, but instantiation yields a type
radixsort_byte.cpp:18: note: say ‘typename std::vector::iterator’ if a type is meant
radixsort_byte.cpp:20: error: dependent-name ‘std::deque::iterator’ is parsed as a non-type, but instantiation yields a type
radixsort_byte.cpp:20: note: say ‘typename std::deque::iterator’ if a type is meant
}}
このようなエラーが吐かれる。
**救いの光が！
@yuyarinに投げたところ解答をいただいたので記す。
***typename
>エラー嫁
エラーをよく見ると
>
say ‘typename std::deque::iterator’ if a type is meant
とある。つまり、typenameとしていすれば型名であることが示されるということ。結局答えは自明ということでしたorz.ちなみに実際にはtypename使えとアドバイスをくださいました。
***構造
STLのソートのようにイテレータ関数として実装せよとのことなので書き直した。
**ソース
radixsort.h
#codehighlight(c++){{
#include <iterator>
#include <vector>
#include <deque>
struct EXCEPT_SORT_OVERFLOW
{
} EXCEPT_SORT_OVERFLOW_;
template <class Iterator>
void radixsort(Iterator begin, Iterator end)
{
typedef typename std::iterator_traits<Iterator>::value_type T;
// data
std::vector<std::deque<T> > data, temp;
// bit operation
const int SEG = 8;
const int WIDTH = sizeof(T) * 8 / SEG;
T mask = (T)~(~0x0 << SEG);
//read & sort
data.resize(0x1 << SEG);
for(Iterator i=begin; i != end; ++i)
data[*i & mask].push_back(*i);
mask <<= SEG;
for(int loop = 1; loop < WIDTH; mask <<= SEG, ++loop)
{
temp.resize(0x1 << SEG);
for(typename std::vector<std::deque<T> >::iterator i = data.begin();
i != data.end(); ++i)
for(typename std::deque<T>::iterator j = i->begin();
j != i->end(); ++j)
temp[(*j & mask) >> (SEG * loop)].push_back(*j);
swap(data, temp);
temp.clear();
}
//write
Iterator target = begin;
for(typename std::vector<std::deque<T> >::iterator i = data.begin();
i != data.end(); ++i)
for(typename std::deque<T>::iterator j = i->begin();
j != i->end(); ++j)
{
if(target == end)
throw EXCEPT_SORT_OVERFLOW_;
*target = *j, ++target;
}
}
}}
wrapper.cpp
#codehighlight(c++){{
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include "radixsort.h"
#define LENGTH(x) (sizeof(x)/sizeof((x)[0]))
template <class T>
class wrapper_vector
{
public:
void input(T *arr, int arr_length);
friend std::ostream &operator<<(std::ostream &stream, wrapper_vector<T> &obj)
{
for(typename std::vector<T>::iterator j = obj.data.begin();
j != obj.data.end(); ++j)
stream << *j << " , ";
stream << std::endl;
return stream;
};
private:
std::vector<T> data;
//const static int SEG = 8;
};
template <class T>
void wrapper_vector<T>::input(T *arr, int arr_length)
{
data.resize(arr_length);
for(int i=0; i < arr_length; ++i)
data[i] = arr[i];
try
{
radixsort(data.begin(), data.end());
}
catch(EXCEPT_SORT_OVERFLOW)
{
std::cerr << "なぜか数が合いません" << std::endl;
}
}
int main()
{
//unsigned int array[] = {31,41,59,26,53,58,97,93,23,84,62,64,33,83,27,95,02,88};
unsigned seed(time(NULL));
srand(seed);
std::cerr << "seed:" << seed << std::endl;
unsigned long array[1000];
for(int i=0; i < (int)LENGTH(array); ++i)
array[i] = (unsigned long)rand();
wrapper_vector<unsigned long> *pSort;
pSort = new wrapper_vector<unsigned long>;
pSort->input(array, LENGTH(array));
std::cout << *pSort;
delete pSort;
char str[] = "The quick brown fox jumps over a lazy dog.";
wrapper_vector<char> *pSort2;
pSort2 = new wrapper_vector<char>;
pSort2->input(str, LENGTH(str));
std::cout << *pSort2;
delete pSort2;
}
}}
表示オプション
横に並べて表示：
変化行の前後のみ表示：
