Hatena::ブログ(Diary)

みずぴー日記

2010-03-24(水)

C++で単方向リスト

| C++で単方向リスト - みずぴー日記 を含むブックマーク

30分プログラム、その745。C++で単方向リストを書いてみた。

さっきBoostインストールを開始したんですが、なかなか時間かかりますね。で、その間の暇つぶしに単方向リスト書いてました。

いたるところでnewしてますが、まったくdeleteしてません。だって、Boostインストールが完了してないから、shared_ptrが使えないんですもん。ごめんなさい。

使い方

list<int>* xs = cons(1, cons(2, cons(3, nil<int>())));

cout << length(xs) << endl;

ソースコード

#include <iostream>

template <typename T>
struct list{
  T value;

  // fix later
  list* next;

  list(T value, list<T>* next)
    :value(value), next(next)
  {}
};

template <typename T>
inline list<T>* nil(){
  return 0;
}

template <typename T>
list<T>* cons(T value, list<T>* next){
  return new list<T>(value, next);
}

template <typename T>
T head(list<T>* xs){
  return xs->value;
}

template <typename T>
list<T>* tail(list<T>* xs){
  return xs->next;
}

template <typename T>
int length(list<T>* xs){
  if(xs == nil<T>()){
    return 0;
  }else{
    return 1 + length(tail(xs));
  }
}

template <typename T>
list<T>* append(list<T>* xs, list<T>* ys){
  if(xs == nil<T>()){
    return ys;
  }else{
    return cons(head(xs), append(tail(xs),ys));
  }
}

template <typename T, typename F>
void for_each(F f, list<T>* xs){
  if(xs != nil<T>()) {
    f(head(xs));
    for_each(f, tail(xs));
  }
}

void puti(int d){
  printf("%d ",d);
}

int main(int argc, char *argv[])
{
  using namespace std;

  list<int>* xs = cons(1, cons(2, cons(3, nil<int>())));
  list<int>* ys = cons(4, cons(5, cons(6, nil<int>())));

  cout << length(xs) << endl;
  cout << length(append(xs,ys)) << endl;

  for_each(puti, xs);
  puts("");

  for_each(puti, append(xs, ys));
  puts("");
  return 0;
}

参考

2010-02-11(木)

分数クラス

| 分数クラス - みずぴー日記 を含むブックマーク

30分プログラム、その736。演算子オーバーロードを使ってみたかったので、分数クラスを作ってみました。

テンプレートを使って、整数の分数とか浮動少数の分数とかできるのを目指してました。が、約分するときに%を使ってるので、int以外の型を引数として与えるとコンパイルエラーがでます。

使い方

rational<int> r1(1,2);
rational<int> r2(2,3);

cout << (r1 + r2) << endl; // => 7/6
cout << (r1 - r2) << endl; // => -1/6
cout << (r1 * r2) << endl; // => 1/3
cout << (r1 / r2) << endl; // => 3/4

ソースコード

#include <iostream>

template <class T>
class rational {
private:
  T num;
  T denom;

public:
  rational(T num, T denom) {
    T r =  gcd(num,denom);
    this->num = num / r;
    this->denom = denom / r;
  }

  T numerator() const {
    return num;
  }

  T denominator() const {
    return denom;
  }

  rational<T> operator+(const rational<T>& that) const {
    T n = numerator() * that.denominator() + that.numerator() * denominator();
    T d = denominator() * that.denominator();
    return rational<T>(n,d);
  }

  rational<T> operator-() const{
    return rational<T>( - numerator(), denominator());
  }

  rational<T> operator-(const rational<T>& that) const{
    return *this + (- that);
  }

  rational<T> operator*(const rational<T>& that) const {
    return rational<T>(numerator()   * that.numerator(),
		       denominator() * that.denominator());
  }

  rational<T> operator/(const rational<T>& that) const {
    return rational<T>(numerator()   * that.denominator(),
		       denominator() * that.numerator());
  }

private:
  T gcd(T a, T b){
    if(b == 0){
      return a;
    }else{
      return gcd(b, a % b);
    }
  }
};

template <typename T>
std::ostream& operator<< (std::ostream& out, const rational<T>& r ){
  if(r.denominator() < 0) {
    return out << "-" << r.numerator() << "/" << (- r.denominator());
  }else{
    return out << r.numerator() << "/" << r.denominator();
  }
}

int main(int argc, char *argv[])
{
  using namespace std;
  rational<int> r1(1,2);
  rational<int> r2(2,3);

  cout << (r1 + r2) << endl;
  cout << (r1 - r2) << endl;
  cout << (r1 * r2) << endl;
  cout << (r1 / r2) << endl;

  return 0;
}

参考

2010-02-06(土)

更新日が古いダミーファイルを作るプログラム

| 更新日が古いダミーファイルを作るプログラム - みずぴー日記 を含むブックマーク

30分プログラム、その731。更新日(mtime)が古いダミーファイルを作ってみました。

動機は、

  • 一月以上前のファイルだけを消すシェルクスクリプトを書きたい
  • いきなり本番環境じゃ動かせない
  • ダミーファイルを作ろう

という感じです。

作ってる途中でtouchコマンドの-tで更新時刻を設定できることに気がつきました。これで十分だよなぁ、と思いつつも、最後まで作っちゃいました。

まあ、Boostを使うのは楽しいのでよしとしましょう。

使い方

$ g++ -I/opt/local/include -Wall mk-old-times.cxx
$ ./a.out 3
$ ls -l dummy-file-*
-r-x------   1 mzp      staff       0  2  6 22:08 dummy-file-0
--wxr-----   1 mzp      staff       0  2  5 22:08 dummy-file-1
--w-------   1 mzp      staff       0  2  4 22:08 dummy-file-2

ソースコード

// g++ -I/opt/local/include -Wall mk-old-times.cxx
#include <sys/time.h>
#include <fcntl.h>
#include <errno.h>
#include <string.h>
#include <iostream>
#include <string>
#include <boost/format.hpp>
#include <boost/lexical_cast.hpp>

void touch(const std::string &path, time_t t){
  const timeval ts[2] = { { t ,0},
			  { t ,0}};
  const int fd = open(path.c_str(), O_CREAT | O_WRONLY);
  if(futimes(fd, ts)){
    std::cerr << strerror(errno) << std::endl;
  }
  close(fd);
}

int main(int argc, char *argv[])
{
  using namespace std;
  using boost::lexical_cast;

  if(argc < 2){
    cout << "usage : " << argv[0] << " [count]\n";
    exit(0);
  }
  int n = lexical_cast<int>(argv[1]);
  int now = time(NULL);

  for (int i = 0; i < n; ++i)
  {
    boost::format s = boost::format("dummy-file-%1%") % i;
    cout << s << endl;
    touch( s.str(), now - i * 24*60*60);
  }
  return 0;
}

参考

2010-01-23(土)

C++でバブルソート

| C++でバブルソート - みずぴー日記 を含むブックマーク

30分プログラム、その726。C++でバブルソートを書いてみました。C++を使うのは久しぶりです。

久しぶりすぎてほとんど書けませんでした。ホントは、マージソートを書きたかったんですが、結局バブルソートになりました。あと、最初はイテレータを使って書いてたんですが、結局あきらめました。

あと、Boostを始めて使ったんですが、これすごいですね。

v += 1,2,3;

とか

for_each(v.begin(),v.end(), std::cout << _1 << '\n');

とか書けるんですもん。すごいですよね。

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <boost/function.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/swap.hpp>
#include <boost/assign.hpp>

using namespace std;

// functionは関数の型
// http://www.kmonos.net/alang/boost/classes/function.html
void bsort(vector<int>& v, boost::function<bool (int,int)> f) {
  int size = v.size();
  for(int i = 0; i < size; i++){
    for(int j = 1; j < size - i; j++){
      if(f(v[j],v[j-1])){

	// スワップ
	// http://www.kmonos.net/alang/boost/classes/swap.html
	boost::swap(v[j],v[j-1]);
      }
    }
  }
}

int main(int argc, char *argv[]) {
  using namespace boost::lambda;
  using namespace boost::assign;

  vector<int> v;

  // コンテナへの要素の追加
  // http://www.kmonos.net/alang/boost/classes/assign.html
  v += 1,10,12,0;

  // 無名関数
  // http://www.kmonos.net/alang/boost/classes/lambda.html
  bsort(v, _1 > _2);

  // ホントはstd::sortを使ったほうがラク
  // sort(v.begin(),v.end(), _1 > _2);

  for_each(v.begin(),v.end(), std::cout << _1 << '\n');
  return 0;
}

参考

2006-04-04(火)

max()マクロの解釈

| 17:29 | max()マクロの解釈 - みずぴー日記 を含むブックマーク

id:selvaggio:20060403が紹介していたコードを解釈してみる。

#define max(T) (((T)(-1)<0)?(((unsigned long long)(-1)>>(65-sizeof(T)*8))):((T)((unsigned long long)(-1))) )

T型で表現できる最大値を返す。

T型とは、[signed | unsigned][char | short | int | long | long long]

のこと。

まず、大量の括弧は演算子の優先度によって、マクロの意味がかわらないための工夫だから無視していいだろう。

あと、三項演算子(?:)はみづらいから、if文っぽく書き換えてみる。

if((T)(-1)<0){
  (unsigned long long)(-1) >> (65-sizeof(T)*8);
}else{
  (T)(unsigned long long)(-1);
}

まず、最初の条件分岐、(T)(-1) < 0 というのは、0xFFF...FFFが負の数と解釈されるかどうか、つまりunsignedなのかsignedなのかを調べている。

簡単だから、さきにunsignedなelse節を考える。この場合、0xFFF...FFFがそのまま最大値になるので、0xFFF...FFFを目的の型にキャストする。

最後に、signedな場合を考えてみる。これは、0xFFFF FFFF FFFF FFFF(-1)をキャストして、0x0FF...FFFのように最上位ビットが0な数字を作っている。

例えば、Tがlong longの場合で考えてみる。long longは8バイト(64ビット)なので、0x0FFF FFFF FFFF FFFFを作りたい。このためには0xFFFF FFFF FFFF FFFFを1個右にシフトすればいい。だから、65-sizeof(long long)*8で1という数字を求めている。


で、思ったんだけど、65という数字はlong longが8バイトであることに依存しているから、sizeof(long long)で書き換えたほうが移植しやすいんでない?

#define MAX_SIZE (sizeof(long long)+1)
#define max(T) (((T)(-1)<0)?(((unsigned long long)(-1)>>(MAX_SIZE-sizeof(T)*8))):((T)((unsigned long long)(-1))) )

selvaggioselvaggio 2006/04/04 19:30 *8も1byte=8bitに依存してるのさ。
sizeofはその通り。でももう少しマトモに書く方法があったっぽい。

2006-01-25(水)

C++でorを

| 17:52 | C++でorを - みずぴー日記 を含むブックマーク

Rubyでよくかくコード

ARGV.length > 0 or abort('usage:...')

C++でも書いてみよう。

#include <iostream>

void f(void)
{
  return;
}
int main(int argc,char** argv) {
  using std::cout;
  using std::endl;
  
  (argc > 1) or (f(),cout << "usage:..." << endl);
  
  return 0;
}

id:selvaggio作。