CPP-assign-2009-06-10 - alabama_country @Wiki

基数ソート

テンプレートやべえ

解決したので簡単にまとめます。

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;
  };
  //略
};

と書くと

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

#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

#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;
}