unique_ptr で今風な C++ コードを書こう！！

C++ unique_ptr

はじめに

お久しぶりです。KMC OB の id:nojima です。

この記事は KMC Advent Calendar 2014 の10日目の記事です。 昨日は id:murata さんの「受験生応援！Javascriptでひねくれ数列」 でした。

今日は C++ の unique_ptr の話です。 （最初は rvalue について書こうと思っていたのですが、書いてみると unique_ptr だらけになったのでタイトルを変えました。なので、KMC Advent Calendar 2014 に書いてあるタイトルとは食い違っています。すみません）

個人的には C++03 ではなく C++11 を使う最大の理由は unique_ptr の存在だと思っています。

  • 例外発生時にももれなく delete してくれる。
  • 生ポインタとパフォーマンスが同じ。(最適化されている場合)
  • 所有権を型として表明できる。

など、様々なメリットがあり、ソースコードに unique_ptr という文字列が存在するだけで何となく今風な雰囲気が漂ってくる優れものです。

ということで、今回は unique_ptr にまつわる tips 集です。

生ポインタではなく unique_ptr を返す関数を書こう

ゲームを制作している状況を考えます。 ステージのレベルに合わせて Enemy を作成して返す関数 CreateEnemy は以下のように書くことができます。

unique_ptr<Enemy> CreateEnemy(int level) {
    if (level <= 5)
        return unique_ptr<Enemy>(new WeakEnemy());    // 低い階層では弱い敵を返す
    else
        return unique_ptr<Enemy>(new StrongEnemy());  // 高い階層では強い敵を返す
}

...

unique_ptr<Enemy> enemy = CreateEnemy(10);

CreateEnemy をこのように unique_ptr を使って書くメリットは２つあります。

  • Enemy* が登場しないので、メモリリークを心配する必要はありません。 unique_ptr を使っている限り、適切なタイミングでメモリが解放されることが保証されます。 もちろん、CreateEnemy の利用者側で unique_ptr の get 関数を呼び出して生のポインタを得た場合はこの限りではありませんが、その場合でも use-after-free の可能性を get を利用している箇所に限定でき、デバッグが容易になります。
  • 戻り値の型から Enemy を CreateEnemy の利用者側が delete すべきであることが簡単にわかります。 Enemy* を返す関数の場合、その関数の利用者が Enemy* を削除していいのかわかりません。 もしかすると、static な領域に Enemy を確保しており、それへのポインタを返している可能性もありますし、複数回の関数コールでメモリ領域を共有しているため、簡単には delete できないかもしれません。 unique_ptr を返している場合は、型から利用者に delete の責任があることがわかるので、こういった心配をする必要はありません。

また、unique_ptr を返す関数を shared_ptr で受けることもできます。このため、複数の場所で Enemy を共有したい場合でも CreateEnemy の戻り値の型を shared_ptr に変更する必要はありません。

shared_ptr<Enemy> enemy = CreateEnemy(10);

unique_ptr&& を受け取って別の関数に渡すときは move しよう

unique_ptr を受け取って、それをそのまま別の関数に渡したい場合があります。 特に、クラスのコンストラクタで unique_ptr<T>&& を受け取って unique_ptr<T> 型のメンバ変数を初期化するようなことは頻繁に発生します。

ところが、普通に以下のように書くことはできません。

// 背景
class Background {
public:
     // 受け取った bitmap を利用してメンバ変数を初期化する。
     // unique_ptr はコピーできないので move したい。
     Background(unique_ptr<Bitmap>&& bitmap)
         : bitmap_(bitmap) {}

private:
     unique_ptr<Bitmap> bitmap_;
};

clang に書けると以下のようなエラーになります。

t.cpp:63:11: error: call to deleted constructor of 'unique_ptr<Bitmap>'
        : bitmap_(bitmap) {}
          ^       ~~~~~~
/usr/include/c++/4.8/bits/unique_ptr.h:273:7: note: 'unique_ptr' has been
      explicitly marked deleted here
      unique_ptr(const unique_ptr&) = delete;
      ^
1 error generated.

エラーメッセージにあるとおり、unique_ptr(unique_ptr&&) を呼びたかったのに、unique_ptr(const unique_ptr&) を呼んでしまっています。 しかし、bitmap の型は unique_ptr<Bitmap>&& のはずなのに、なぜ unique_ptr(unique_ptr&&) ではなくて unique_ptr(const unique_ptr&) が呼ばれてしまうのでしょうか？

その理由は、unique_ptr(unique_ptr&&) の方を呼ぶためには引数の型が rvalue reference であるだけでは不十分で、引数の式の value category が rvalue であることも要求されるからです。この場合は、引数の式の value category が lvalue なので、unique_ptr(const unique_ptr&) の方を呼びだそうとしてしまいます。 （lvalue は、bitmap や bitmap.width などの「名前のついたオブジェクト」を表す式です。rvalue は lvalue の逆で foo() や x + 1 といった「名前のないオブジェクト」を表す式です。）

これを解決するためには以下のように std::move 関数を使って引数の式を rvalue にすればよいです。

// 背景
class Background {
public:
     // 受け取った bitmap を利用してメンバ変数を初期化する。
     Background(unique_ptr<Bitmap>&& bitmap)
         : bitmap_(move(bitmap)) {}    // move すれば OK

private:
     unique_ptr<Bitmap> bitmap_;
};

vector<unique_ptr<...>> を使うときは make_move_iterator を活用しよう

unique_ptr の vector などを作っていると、各要素を move するような iterator が欲しいことがあります。 std::make_move_iterator 関数を使うと、まさにそのような iterator を作ってくれます。

またゲームの例ですが、2つの vector があって、片方の vector からもう片方の vector に要素を移動させたい場合を考えます。

// 全 Enemy を格納する vector
vector<unique_ptr<Enemy>> all_enemies;
// 現在のフレームで生成された Enemy を格納する vector
// (現在のフレームが終わるまでは all_enemies には登録されない)
vector<unique_ptr<Enemy>> new_enemies;

...

// new_enemies に入っている Enemy を全て all_enemies に移動させる。
all_enemies.insert(all_enemies.end(),
                   make_move_iterator(new_enemies.begin()),
                   make_move_iterator(new_enemies.end()));
new_enemies.clear();

こんな感じに、make_move_iterator と vector::insert で簡単に要素を移動させることができます。 また、<algorithm> の関数とも組み合わせることもできて便利なので、覚えておくといろんな所で役に立つと思います。

終わりに

ということで、unique_ptr を積極的に活用して delete をソースコードから駆逐しましょう！！

明日は id:nonylene さんの「電電宮にお参りした話」です。お楽しみに！！

追記 (12/10)

id:cos65535 さんの指摘により訂正

「メモリリークの可能性を get を利用している箇所に限定でき」
　　↓
「use-after-free の可能性を get を利用している箇所に限定でき」

ICFPC 2014 参戦記

C++

ICFP Programming Contest 2014 に @cos65535 さん, @qwerty__ さん, @seikichi さんとチームを組んで参加した。

25日(金)

  • 21:00　コンテスト開始。問題を読み始める。
    • パックマンみたいなゲームの AI を書け、という問題。
    • ただしゲームの AI は GCC という謎の LISP マシンの上で動く。（それ専用の機械語が定義されているので、それを使って AI を書かないといけない）
    • また、ゴーストの AI も書く必要がある。ゴーストの方は GHC というわりと普通な感じの機械語の上で動くが、メモリが 256 バイトしか使用できず、また、プログラムも 1024 命令しか実行できない。
  • 21:30　夕食を食べに行く。
  • 23:40　seikichi さんが到着。

26日(土)

  • 0:00　方針を決める。
    • AI を直接 GCC (与えられた Lisp マシンにおける機械語) で書くのはかなりキツい。高級言語からコンパイルしたい。
    • 機械語が Lisp っぽいので Lisp からコンパイルするのが自然なのではないか。Lisp なら構文解析が楽そうだし。ということで、Lisp から GCC へのコンパイラを作ることに。
    • また、与えられた機械語で配列（定数時間で任意のインデックスに読み書きもの）が実現できないことが判明する。2分木を使った配列もどきライブラリを作らないといけないという話になる。
    • ということで、以下の4つの作業を分担してやることになった。
      • Lisp から GCC へのコンパイラの作成
      • GCC のシミュレータの作成
      • ゲームのシミュレータの作成
      • Lisp 用のライブラリの作成
    • 自分はコンパイラを作ることになった。
  • 2:00　GCC の仕様書を読みながら幾つかのプログラムを手コンパイルしてみる。
    • DUM と RAP の意味がいまいちわからないが、一応コンパイラはなんとか作れそうな気分になる。
    • 実装言語を決める。速度はどうでも良さそうなので Python にした。
  • 5:00　構文解析まで実装終了。寝る。
  • 11:00　起きる。
  • 13:00　(+ 1 1) がコンパイルできるようになる。
  • 15:00　define の実装でつまる。
    • 以下のコードをどうやってコンパイルしたらいいかわからない。 
      ;; カリー化された add
(define add (lambda (x) (lambda (y) (+ x y))))
; 部分適用
(define inc (add 1))
;; 42 が返る。
(inc 41)
  • 16:00　DUM で予め領域を確保しておき、後から ST でクロージャを入れていけば define が実装できることに気付く。
    • lambda の中で define してもちゃんとレキシカルスコープ的に正しく動作する。
  • 17:00　lambdaの実装が完了。
  • 17:20　ifの実装が完了。
  • 17:30　ラベルをアドレスに変換する部分を実装し、Lisp コンパイラが完成。
  • 20:30　seikichi さんが Lisp でそれっぽい AI を実装し、ライトニングラウンドにサブミット。

27日(日)

土曜日の反動でだらだらしてしまった日。

  • 0:00　seikichi 先生が Gauche の macroexpand を使ってマクロを展開してからコンパイラに投げるプログラムを書く。
    • これにより、define-macroで簡単に構文を拡張できるようになる。
    • let, and, begin, cond などのおなじみのマクロが自由に使えるようになる。
    • さすが Lisp …。
  • 1:30　末尾関数呼び出しの最適化を実装。
  • 2:00　寝る。
  • 10:00　起きる。
  • 14:00　コンパイラのデバッグ + (define (foo x y) ...) のような構文の実装。
    • かなり普通の Scheme っぽく書けるようになってきた。ぱっと見では見分けがつかない。
  • 15:00　コンパイラでやることがなくなってきたので、GCC のシミュレータのデバッグを手伝う。
  • 18:00　GCC のシミュレータが動くようになる。
    • cos さんが作ったゲームのシミュレータと合わせると、Lambda Man の AI を動作させる環境が完全に揃ったことになる。
  • 20:00　再びやることがなくなってたので AI の作成を始める。
  • 21:30　BFS をする AI を書いた。が、バグっていて動かない。
  • 22:30　Scheme の関数の引数の数を間違っているところがあったのを修正。
  • 22:30　ゴーストが弱い場合はマップをクリアできるようになった。
    • AI は動くようになったがやけに重い。最初はシミュレータのパフォーマンスが悪いのかと疑ったが、実はそうではなく、BFS の実行に時間がかかりすぎているようだった。
    • 32x32 程度のマップを BFS するのに 170 万命令かかっていた。AI の 1 ステップの命令数の上限が 300 万命令程度なので、これはかなり危ない (というか 256x256 のマップが来たら即死する）状況だということを認識する。
    • とりあえず、適当に最適化をしてみたが、ほとんど改善しなかったので、qwerty さんにプロファイラの実装をお願いする。

28日(月)

  • 2:00　プロファイラのおかげで組み込み関数の呼び出しに時間がかかっていることが判明したので、コンパイラを改造して最適化。
    • この改修で 170 万命令 → 140 万命令。
    • 次のボトルネックはvector-refだが、作者が寝てしまっていたので、放置して寝ることにした。
  • 8:30　起きる。
  • 10:30　seikichi 先生がひたすら関数をマクロでインライン展開する。
    • 140 万命令 → 40 万命令。
  • 11:00　移動
  • 13:30　BFS AI のループ回数に上限をつけた。これで 256x256 のマップでも一応動作するようになった。
  • 14:00　近くにゴーストがいるときはゴーストからに逃げるようにした。
    • これで結構 AI っぽくなった。
  • 14:30　ゴーストを殺せるときは殺しに行くようにした。
  • 18:40　方向にスコア付けして一番高いスコアの方向に行くようにした。
    • 複数のゴーストに同時に襲われたときに逃げられる確率が上がった。たぶん。
    • Lambda-Man Hall of Fame の ghostbusters でランクインした。
  • 19:00　cos さんがいつの間にか DFS をするゴーストの AI を書いていた。
  • 19:45　フルーツを食べに行くようにした。(by seikichi 先生)
  • 20:30　パラメータの調整など
  • 20:50　AI 提出！！

まとめ

  • 最初はどうなることかと思ったが、意外とまともな AI を書けたような気がする。
    • やはり高級言語は偉大。
    • あと macroexpand 偉い。
  • プロファイル大事。
  • コンパイラのエラーチェックを真面目に作っておいたおかげでデバッグコストが結構低かった。
  • qwerty さんの予約してくれたホテルが快適だった。環境大事。

VirtualBoxにArch Linuxをインストールしたときのメモ

Linux

VirtualBoxにInstall media 2012.08.04 を使用してArch Linuxをインストールしたときのメモ．VMのディスクサイズは40GB，メモリは4GB．メモリサイズが1GB以上あるときはswap作らないほうがパフォーマンスがでるらしいのでswapなし．

いつの間にかインストーラが削除されていてArch Linuxのインストールが面倒になってました．

# loadkeys jp106
# parted
(parted) unit MiB
(parted) mklabel msdos
(parted) mkpart primary 1 10241
(parted) mkpart primary 10241 20481
(parted) mkpart primary 20481 20581
(parted) mkpart extended 20581 40959
(parted) mkpart logical 20582 40959
(parted) quit
# mkfs -t ext4 /dev/sda1
# mkfs -t reiserfs /dev/sda2
# mkfs -t ext2 /dev/sda3
# mkfs -t ext4 /dev/sda5
# mount -t ext4 /dev/sda1 /mnt
# mkdir /mnt/{var,boot,home}
# mount -t reiserfs /dev/sda2 /mnt/var
# mount -t ext2 /dev/sda3 /mnt/boot
# mount -t ext4 /dev/sda5 /mnt/home
# vi /etc/pacman.d/mirrorlist
日本のサーバをリストの一番上に持ってくる
# pacstrap /mnt base base-devel
# pacstrap /mnt grub-bios
# genfstab -p /mnt >> /mnt/etc/fstab
# arch-chroot /mnt
# vi /etc/hostname
arch-vm
# ln -s /usr/share/zoneinfo/Asia/Tokyo /etc/localtime
# vi /etc/locale.conf
LANG="en_US.UTF-8"
LC_COLLATE="C"
LC_TIME="en_DK.UTF-8"
# vi /etc/locale.gen
以下の3行のコメントアウトを解除
en_DK.UTF-8 UTF-8
en_US.UTF-8 UTF-8
ja_JP.UTF-8 UTF-8
# locale-gen
# mkinitcpio -p linux
# mv /boot/grub /boot/grub-legacy
# mkdir /backup
# dd if=/dev/sda of=/backup/mbr-backup bs=512 count=1
# modprobe dm-mod
# grub-install --target=i386-pc --recheck --debug /dev/sda
# mkdir -p /boot/grub/locale
# cp /usr/share/locale/en\@quot/LC_MESSAGES/grub.mo /boot/grub/locale/en.mo
# grub-mkconfig -o /boot/grub/grub.cfg
# vi /etc/rc.conf
次の行を追加
KEYMAP=jp106
# passwd
rootパスワードを設定
# exit
# umount /mnt/{var,boot,home,}
# reboot

# pacman -S zsh vim tmux git openssh sudo
# pacman -S virtualbox-archlinux-additions
# modprobe -a vboxguest vboxsf vboxvideo
# vim /etc/modules-load.d/vbox.conf
vboxguest
vboxsf
vboxvideo
# pacman -S dbus
# vim /etc/rc.conf
DAEMONSにdbusを加える
# rc.d start dbus
# pacman -S xorg
# pacman -S gnome
# pacman -S gdm
# pacman -S xorg-xinit xterm
# vim /etc/inittab
id3:initdefault: をコメントアウトして
id5:initdefault: のコメントアウトを解除
x:5:respawn:/usr/bin/xdm -nodaemon をコメントアウトして
x:5:respawn:/usr/bin/gdm -nodaemon のコメントアウトを解除
# vim /etc/skel/.xinitrc
VBoxClient-all &
exec ck-launch-session gnome-session
# adduser
普段使い用ユーザを追加
# visudo
今追加したユーザをsudoerにする

ノートPCのVirtualBox上にDebian環境を作る

Linux

やりたいこと

  • ホストOSはWindows，ゲストOSはDebian，仮想化にはVirtualBoxを使用
  • インターネットにはNATで接続
  • DebianにはGUI環境をインストールせず，常にPuTTYを通じて使用する
  • DebianのファイルをSambaを使ってWindowsと共有する

やったこと

  1. VMのネットワークの設定
    インターネットにはNATで接続したいので，アダプタ 1 にはNATを割り当てます．さらに，ポートフォワーディングの設定でホストポート2222からゲストポート22へのポートフォワードの設定を追加します (IPの欄は空)．また，ホスト-ゲスト間の通信のためにアダプタ 2 にホストオンリーアダプタを割り当てます．
  2. Debianのインストール
    普通にインストールします．途中にどのアダプタでインターネットに接続するかを聞かれるので，最初のアダプタを選びます．
  3. IPアドレスの設定など
    /etc/network/interfaces を以下のように編集します． 
    # The loopback network interface
auto lo
iface lo inet loopback

# The primary network interface (NAT)
auto eth0
allow-hotplug eth0
iface eth0 inet dhcp

# The secondary network interface (Host-only)
auto eth1
iface eth1 inet static
address 192.168.56.102
netmask 255.255.255.0
    次にネットワークを再起動します． 
    sudo /etc/init.d/networking restart
  4. Samba の設定
    まず apt で Samba をインストールします．インストール中にWORKGROUPを聞かれるので，WindowsのWORKGROUPと同じものを指定します． 
    sudo apt-get install samba
    /etc/samba/smb.conf を編集します．diff はこんなかんじ． 
    --- a/samba/smb.conf
+++ b/samba/smb.conf
@@ -114,7 +114,7 @@
 # This boolean parameter controls whether Samba attempts to sync the Unix
 # password with the SMB password when the encrypted SMB password in the
 # passdb is changed.
-   unix password sync = yes
+   unix password sync = no

 # For Unix password sync to work on a Debian GNU/Linux system, the following
 # parameters must be set (thanks to Ian Kahan < for
@@ -239,15 +239,15 @@

 # By default, the home directories are exported read-only. Change the
 # next parameter to 'no' if you want to be able to write to them.
-   read only = yes
+   read only = no

 # File creation mask is set to 0700 for security reasons. If you want to
 # create files with group=rw permissions, set next parameter to 0775.
-   create mask = 0700
+   create mask = 0644

 # Directory creation mask is set to 0700 for security reasons. If you want to
 # create dirs. with group=rw permissions, set next parameter to 0775.
-   directory mask = 0700
+   directory mask = 0755

 # By default, \\server\username shares can be connected to by anyone
 # with access to the samba server.
    Samba のアカウントを作ります． 
    sudo smbpasswd -a nojima
    最後に Samba を再起動します． 
    sudo /etc/init.d/samba restart
    Windows側のエクスプローラのアドレス欄に 
    \\192.168.56.102
    と打ち込んでアクセスできれば成功です．
  5. Windows の hosts ファイルの書き換え
    毎回VMのIPアドレスを打ち込むのは面倒なので，hostsに名前を登録しておきます． C:\Windows\System32\drivers\etc\hosts に以下の行を追加します．(debian-vmのところはVMの名前) 
    192.168.56.102    debian-vm
    書き換えに管理者権限が必要だったりするので，管理者権限でメモ帳などを実行し，そこから編集するとよいです．

ポートフォワードについて

PuTTYでVMにアクセスする際にはポートフォワードを用いてアクセスする方が便利です．(つまり localhost の 2222 番ポートにアクセスする) 直接VMにアクセスすると，ノートPCをスリープさせた時に接続が切れてしまいますが，何故かポートフォワードを使ってアクセスすると接続が切れません．どうして接続が切れないのかよくわかりませんが，とりあえず便利です．

アプリケーションのメモ

OSの再インストールに備えてリストアップ．

Windowsで快適なLaTeX環境を構築する

LaTeX OMake

Windowsで快適にLaTeXで論文を書くためのメモ．

LaTeXで論文を書いているときは，
　テキストエディタで.texを編集する → platexでコンパイル → Adobe Readerでプレビュー → 最初にもどる
という流れで論文を書いていくことになるのですが，いちいちコンパイルしたり，Adobe Readerで開いたりするのは面倒なので，.texを変更したら自動的に変更を検出してコンパイルし自動的にプレビューに反映する環境を構築しました．

使用したソフトは

  • w32tex．これがなくては始まらない．abtexinst を使えば何も考えなくてもインストールできます．
  • OMake．いわゆるビルドツール．コンパイルの自動化に使用します．
  • SumatraPDF．PDFビューワ．PDFを変更すると自動的にリロードしてくれます．

です．

以下では書いているTeXファイルを document.tex とし，BibTeXファイルを refs.bib としています．違う名前を使う場合はこれらの名前を置換してください．また，platexやomakeの存在するディレクトリにはパスが通っているものとします．

まず，document.tex や refs.bib が存在しているディレクトリで omake --install を実行して OMakefile と OMakeroot を生成します．Windows 7だといちいちコマンドプロンプトを開かなくても，エクスプローラーのアドレスバーに「omake --install」と打てばそのディレクトリでomakeを実行することができます．

次に，OMakefileの内容を全て消去して以下のように編集します．

LATEX = platex
TETEX2_ENABLED = false
LATEXFLAGS = -interaction=nonstopmode
BIBTEX = pbibtex
DVIPDFM = dvipdfmx
DVIPDFMFLAGS = -p a4

TEXDEPS[] = refs.bib

LaTeXDocument(document, document)

.DEFAULT: document.pdf document.dvi

次に，omake -P --verbose を実行します．このコマンドは，omake を監視モードで起動し，ファイルに変更があった場合は自動的にコンパイルするコマンドです．

次に，document.pdf を SumatraPDF で開いておきます．

後は，document.tex をテキストエディタで編集して保存する度に，omake が自動的にコンパイルを行い，SumatraPDF が自動的にプレビューに反映してくれます．手動でコンパイルするのと比べて，かなり楽にプレビューを見ることができるようになります．デュアルディスプレイだと，片方のディスプレイで PDF を常に表示しておくと，プレビューを見ながら TeX を編集できて，楽しいです．

ただし，TeXでエラーが出てしまうと，platexモードがデバッガモードに入ってしまって自動ビルドが止まってしまうことがあります．こういうときは，コマンドプロンプトの画面で Enter を押すとたいてい動いてくれます．それでもうまくいかないときは omake をいったん終了させてもう一度起動しましょう．ここらへんがもうちょっと何とかなればもっと楽なのですが，解決策がわからない…… -interaction=nonstopmode を LaTeX の引数に与えればエラー時にデバッグモードに入らないようです．

「サマーインターン2011問題 : Preferred Research」について考えてみる

今更ながら，「サマーインターン2011問題 : Preferred Research」について考えたので，ここにメモ．

問題の概要を箇条書きにすると

  • 長さ n の文字列 s が与えられる
  • s に含まれる文字の中で，出現回数が最も大きい文字を出力せよ
  • ただし，出現回数が最大の文字の出現回数は n/2 より大きい
  • 計算時間は O(n) でなければならない
  • 空間使用量は s を格納するバッファを除いて O(1) でなければならない
  • s を格納するバッファは書き換えてよい

解法1

よく考えると，s をソートしたときに n/2 番目に来る要素は，出現回数が最大の文字であることがわかります．「ソートしたときに k 番目に来る要素」というのは，実際にソートをしなくても O(n) で求めることができ，問題の条件を満たします．C++ の標準ライブラリには nth_element という関数が用意されており，これを使うと簡単に「ソートしたときに k 番目に来る要素」を計算できます．

解法2

次のアルゴリズムを考えます．

for (;;) {
  添字 i を [0, n) からランダムに選ぶ;
  文字 s[i] の出現回数をリニアにカウントする;
  if (s[i] の出現回数 > n/2) return s[i];
}

1回の反復で答えが求まる確率は少なくとも1/2あるので，平均計算時間は

(1 + 1/2 + 1/4 + ...) O(n) = O(n)

となり問題の条件を満たします．