「プログラミング」カテゴリーアーカイブ

notepad

コメントを残す

先週末にメンテナンスでサーバの電源を切ってました．
アクセスしてくれた人(いたら)すいません．

———-
友人からブラウザ上で動くメモ帳を作って，と言われたので作ってみました．
notepad

ものすごくシンプルにしてくれと言われたので，ものすごくシンプルにしました．
メモ帳を起動するのが面倒だから，ブラウザのタブにずっと出しておくつもりらしいです．

機能追加，改善案などあれば連絡ください．

unordered_map

コメントを残す

備忘録
C++11で新しく標準化されたunordered_map(ハッシュマップ)の使い方を調べたのでまとめておきます．

———-
基本的な使い方はmapと同じで，[]演算子を使った要素へのアクセスができます．
ハッシュマップのバケットに関するメソッドがいくつか定義されていて以下のようなものなどがあります．
bucket_count() : バケット数
bucket_size(int n) : 引数で指定したバケットに入っている要素数
rehash(int n) : バケット数をnに変更

unordered_map<string, int> hashmap;

// 基本的な使い方はmap等と一緒
hashmap["taro"] = 16;
hashmap["jiro"] = 14;
cout << "taro : " << hashmap["taro"] << std::endl;  // "taro : 16"
cout << "jiro : " << hashmap["jiro"] << std::endl;    // "jiro : 14"

// 各バケットのサイズを調べる
cout << "--- buckets ---" << endl;
for( size_t i = 0; i < hashmap.bucket_count(); i++ ){
  cout << i << " : " << hashmap.bucket_size( i ) << endl;
}

// バケットを10個にリハッシュ，バケットの最小値は8
hashmap.rehash( 10 );
// コンストラクタでバケット数を12に指定
unordered_map<string, int> hashmap2( begin(hashmap), end(hashmap), 12 );

バケット数には最小値が決められているようで，自分の環境(VS2010)では最小数は8となっていました．
最小値未満のバケット数を指定しても無視されて，バケット数は最小値になりました．

自作クラスをキーにするには以下のことをする必要があります．

自作クラスに operator== を定義する
自作クラスのハッシュ関数を作成する

ハッシュ関数を作成するには以下の方法があります．

自作クラスを受け取り，size_tを返すファンクタを作る
std::hashクラスを自作クラスに特殊化する

// 自作クラス
class Name{
const string name;
public:
Name( string n ) : name( n ) {}

  bool operator == ( const Name& rhs ) const {
    return rhs.name == name;
  }
};


// 方法1 : 自作ファンクタ
class MyHash{
public:
  size_t operator() (const Name& val ) const {
    return 1;  // テスト用の悪いハッシュ関数
  }
};

// 方法2 : std::hashの特殊化
template<>
struct std::hash<Name> : public unary_function<Name, size_t> {
  size_t operator()(Name val) const {
    return 2; // テスト用の悪いハッシュ関数
  }
};


// 特殊化されたstd::hashが使用される
unordered_map<Name, int> hashmap;
// 自作のファンクタが使用される
unordered_map<Name, int, MyHash> hashmap2();

hashクラスにはデフォルトのハッシュ関数が定義されているのですが，そこではキー値をsize_t型にキャストしています．なので，size_t型にキャスト可能な新たにハッシュ関数を定義しなくてもunordered_mapのキーにすることができます．
また，hashクラスは最初から string, wstring に対して特殊化されていたので(VS2010)，これらはデフォルトで使用することができます．

———-
とりあえず，自作クラスをキーにする方法などを調べましたが，ハッシュ関数の作成は色々と気を使う必要があってしんどいので個人的にはstringをキーにすることしかなさそうです．

迷路ソルバ

コメントを残す

思わず保存した画像スレ:哲学ニュースnwkにあった迷路画像が見ていておもしろかったので，迷路を解くプログラムを作成してみました．
↓が問題の迷路

基本的にはスタート地点からゴールに到達するまで単純な全幅探索を行なうだけです．
迷路の枠の抽出とかにはOpenCVを使いました．

で，プログラムに解かせた時の様子が↓

mazeA

ほかのカオスな迷路を解かせた時↓

mazeB

stringの罠

コメントを残す

つまらない事でつまづいたので覚え書き．
c++でstringをキーとしたmapを使用したのですが，mapの要素にアクセスしようとするとコンパイルエラーが発生．

#include <map>
using namespace std;
...
map< string, int > m;
m["piyo"] = 1;              // エラー，コメントアウトするとコンパイルは通る

「二項演算子'<‘:const std::stringは，…(略)…定義を行いません．」とのこと．
stringの定義がうまくいってないのかな，と思ったのですがmの定義時にstringを使用しているからstringは定義できているはず．しかも，違うソースファイルに同じ処理を書くと正しくコンパイルされる…
と，かなり悩んだ結果<string>のincludeを行っていないことが原因と判明．

VCではstring，basic_string自体は<xstring>に書かれており，<iostream>や<map>などをincludeするだけで使用可能になります．しかし，stringの<<演算子の定義などは<string>に書かれているようで，演算子を使用しようとすると演算子が定義されていないとのエラーがでるということみたいです．
なので，下のようなソースはコンパイルに通りますが，コメントを外すとコンパイルエラーになります．

#include <iostream>

int main(){
std::string str = "piyo";
//  std::cout << str << std::endl;        // コメントを外すとエラー
}

gccはさらにゆるくて，上のソースのコメントを外してもコンパイルが通ります．(cygwinのgcc 4.5.3)

templateのエラーのわかりづらさとあいまって，つまらない事で(つまらないことだからこそ?)かなりの時間を潰してしまいました．
もう，stringはincludeしてなければエラーが出るようにして欲しい．