HomebrewでMacにGCC 4.6を入れる

最近MacBook Airを買いました。なかなか快適です。ただ、期待していたのと違いデフォルトではGCCが入っていない。Xcodeというものを入れるとGCCも入るらしいことを知って、Xcodeを入れましたが入ったのはGCC 4.2.1。これではとても辛いので、Homebrewを使ってGCC 4.6.0を入れてみました。*1

Homebrew本家のリポジトリにはGCCが無いようなので、homebrew-altというリポジトリから入れると良いらしいです。*2以下のコマンドを打てばいいはずなのですが、

$ brew install https://github.com/adamv/homebrew-alt/raw/master/duplicates/gcc.rb --enable-all-languages

私の環境 (Mac OS X 10.7 Lion) ではmake bootstrapに失敗しました。これはビルドにclangが使われたためのようです。GCCでビルドするには、

$ HOMEBREW_USE_GCC=1 brew install https://github.com/adamv/homebrew-alt/raw/master/duplicates/gcc.rb --enable-all-languages

とすれば良いようです。私の環境ではビルドに成功しました。

これでMac上でC++11ライフが送れます。

$ g++-4.6 -std=c++0x hello.cc

*1:本当は4.6.1がいいので、そのうちHomebrewで4.6.1を入れる方法を考えます。

*2:homebrew-alt で gcc-4.6 をインストール

GCCでBoostをC++11用にビルドする

BoostにはC++11対応がなされており、ヘッダーオンリーライブラリなら

g++ -std=c++0x source.cc

とするだけで使うことができます。*1しかし、ビルドが必要なライブラリの場合には落とし穴があります。ライブラリを、bjamを使って通常の手順で生成した場合、-std=c++0x無しでコンパイルされてしまいます。これではリンクエラーになってしまいます。*2

この問題に関する日本語情報が見つからなかったので解決法を書いておきます。*3

解決法は非常に簡単です。user-config.jamというファイルを書いてホームディレクトリに置き、Boostをビルドするだけです。user-config.jamは次の形式に従って書いてください：

using gcc : バージョン : g++のコマンド名 : <cxxflags>-std=c++0x ;

例えばGCCのバージョンが4.6.1で、g++がg++-4.6.1という名前なら

using gcc : 4.6.1 : g++-4.6.1 : <cxxflags>-std=c++0x ;

となります。バージョンを省略して

using gcc : : g++-4.6.1 : <cxxflags>-std=c++0x ;

のようにすることもできます。jamファイルのトークンはスペース区切りであるため、上のjamファイルのスペースは省略できないことに注意してください。

あとはBoostのルートに移り、

./bootstrap.sh && ./bjam --layout=versioned

と打つだけでC++11対応のライブラリファイルが生成されます。

*1:当然Boostをダウンロードして設定を行う必要はありますが。

*2:追記：多くの場合問題は生じないようですが、-std=c++0xをつけてビルドするのが無難でしょう

*3:英語情報

C++03とC++11の互換性についての補足

id:melponさんがC++03とC++11の互換性について書かれました。ぜひ読むべきだと思います。

当該記事のコメント欄で指摘されてますが、n3291*1のC.1に書かれている部分が抜けているので補足します。C.1にはC言語からの変更について書かれており、C++03では変更されてないがC++11で変更されたものも含まれています。C.1に書かれているもののうち、C++03で既にC言語から変更されているものについては書きません。知りたい場合は規格か適当な書籍に当たってください。
変更部分は2つあります。文字列リテラルに関することと、autoキーワードの意味の変更です。これらの変更によって互換性の問題が発生したとしても、修正するのは容易です。修正方法も書きました。

文字列リテラル

Cでは、文字列リテラルはconstではありませんでした。

char* s = "abc"; // valid in C

C++03の文字列リテラルはconstになりましたが、constでないポインタで文字列リテラルを指したり、constでないポインタを引数に取る関数に文字列リテラルを渡したりできました（deprecatedですが）。C++11ではこれらが禁止されました。

char* s = "abc"; // deprecated in C++03
                 // invalid in C++11

void f(char*);
f("abc"); // deprecated in C++03
          // invalid in C++11

修正方法は、constを付けることです。

char const* s = "abc";

void f(char const*);
f("abc");

関数を修正できない場合は、char*にキャストするか、文字列をコピーすることによって解決できます。

void f(char*);

// キャストによる解決
f(const_cast<char*>("abc"));

// コピーによる解決
char s[] = "abc";
f(s);

当然ですが、キャストによる解決の場合、関数の中で文字列を書き換えてはいけません。

autoの意味の変更

C言語およびC++03では、自動変数を定義するときにautoというキーワードを付けることができました。単に自動変数であることを明示的に示すだけで、省略しても全く問題ありません。

auto int n = 0; // int n = 0;

C++11では、autoは別の意味を持ちます。初期化子から変数の型を推論するときに使うようになりました。

auto n = 0; // int n = 0;
auto const x = 3.14; // double const x = 3.14;

この変更に伴い、型を明示的に書くときにautoを付けることはできなくなりました。

auto int n = 0; // invalid in C++11

解決法は、単にautoを削除するだけです。

*1:C++11の最新ドラフト。ダウンロードできなくなったが、ほぼ同等のn3242で多くの場合代用できる。

C++で40バイトのHello Worldを書いた

Hello Worldはプログラミング言語の入門書でおなじみのプログラムで、入力を受け付けず、"Hello, world!"を出力するプログラムです。Hello Worldを、C++で40バイトのものを書きました。

main(){__builtin_puts("Hello, world!");}

これだけではよくわからないと思いますので、順を追って説明します。
C++で普通にHello Worldを書くと次のようになります。

#include <iostream>

int main()
{
    std::cout << "Hello, world!\n";
}

長いですね。削除できる空白や改行を除いても60バイトもあります。まずiostreamのかわりにCのstdioを使って書きなおします。

#include <cstdio>

int main()
{
    puts("Hello, world!");
}

51バイト。main関数の戻り値の型を消しましょう。

#include <cstdio>

main()
{
    puts("Hello, world!");
}

47バイト。実はC++では戻り値の型を省略できないことになっているのですが、g++では警告が出るもののコンパイルが通りました。さてincludeが邪魔ですね。削除しましょう。

main()
{
    puts("Hello, world!");
}

これで30バイト！と言いたいところですがg++には通りませんでした。C++の規格からすると当然なのですが。そこでputs関数の代わりに、ヘッダをインクルードする必要がないビルトイン関数の__builtin_putsを使います。

main()
{
    __builtin_puts("Hello, world!");
}

空白や改行を削除して

main(){__builtin_puts("Hello, world!");}

40バイトのHello Worldの完成です。
2011年8月22日現在、Anarchy Golfというサイトでこのコードが1位になっています。

PFIサマーインターン2011問題

PFIという検索エンジンのベンチャー企業でインターンシップの募集があったようです。その選考過程で次のような問題*1が出たそうです。

長さnの文字列中で出現回数が最大の文字をO(n)時間で答えるプログラムを書いてください。但し、出現回数が最大の文字の出現回数はn/2より大きいとします。

条件として、文字列を格納しているバッファは書き換え可能で文字列以外に利用できるバッファサイズはc log n bits（cは任意の定数）であり、文字種類数は可変（最大n）であるとします。

この問題が解けたので、解答を書いておきます。

#include <cassert>
#include <algorithm>
#include <string>

char PFI(std::string& s)
{
    assert(!s.empty());

    typedef std::string::iterator iterator;

    iterator const begin = s.begin();
    iterator const mid = begin + s.size()/2;

    std::nth_element(begin, mid, s.end());

    return *mid;
}

これが何をしているかというと、文字列の中央値を求めています。見つけたい文字が文字列の半分以上を占めているので、それでいいわけです。中央値を求めるのを実際に行っているのがstd::nth_elementで、ある範囲のうちm番目に小さいものをm番目に置く操作を行います。std::nth_elementは平均的には対象とする範囲の要素数に比例した時間しかかからないことが、C++の規格で定められています。また、std::nth_elementの典型的な実装はメモリの条件も満たしています。

*1:サマーインターン2011問題 : Preferred Research

Expression Template と auto 追補

このエントリは Expression Template と auto の補足です。

先日は問題の提示だけして解決法を書きませんでした。本エントリでは解決法と、Expression Templateで実装されたライブラリを使うときの注意と、前回のサンプルコードについて述べます。

解決法

問題は

Vector<double> v1(3), v2(3);
auto v3 = v1 + v2;

とするとv3の型がPlus, Vector >に推論され、これはv1とv2の値ではなく参照を持つので危険だということでした。autoで加法演算子の結果を受けられないようにすれば問題は解決します。

そのために、Plus<...>のコピーコンストラクタをprivateにすれば、autoで受けられなくなります。

template <typename Vec1, typename Vec2>
class Plus {
  // ...
private:
  Plus(Plus const&);
  // ...
};

コピーコンストラクタをprivateにすると、Plus<...>に推論されたv3のコピーコンストラクタが不可視になります。また、コピーコンストラクタを宣言するとムーブコンストラクタが暗黙に生成されないので、v3を構築することができなくなります。

コピーコンストラクタをprivateにしたために、operator+がPlus<...>を返すことができなくなりますが、operator+をPlus<...>のfriendにすれば返せるようになります。

template <typename Vec1, typename Vec2>
class Plus {
  // ...
  template <typename U1, typename U2>
  Plus<U1, U2> operator+(U1 const&, U2 const&);
  // ...
};

Expression Templateで実装されたライブラリを使うときの注意

まず使用するライブラリがExpression Templateで実装されているかを確認しましょう。std::valarrayがExpression Templateで実装されているかもしれないということはあまり知られていないと思います。C++の規格では（C++03でもC++0xでも）std::valarrayをExpression Templateで実装してもしなくても構わないことになっています。

そしてExpression Templateで実装されている可能性があることが分かったら、autoで演算結果を受けないように注意しましょう。既存のExpression Templateは上のような対応はしていないことが多いので気をつけるしかありません。

サンプルコード

前回のサンプルコードはインクルードするヘッダを書かない、すべてをグローバル名前空間に置く、などの問題がありましたので修正したものを以下に貼ります。

#include <cassert>
#include <algorithm>
#include <boost/config.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/scoped_array.hpp>
 
namespace pepshiso {
namespace impl {
template <typename T>
class Vector {
public:
  typedef T value_type;

  explicit Vector(std::size_t n)
    : buf_(new T[n]), size_(n)
  {}
  Vector(Vector const& v)
    : buf_(new T[v.size_]), size_(v.size_)
  {
    std::copy(v.buf_, v.buf_ + v.size_, buf_);
  }
#ifndef BOOST_NO_RVALUE_REFERENCES
  Vector(Vector&& v)
    : size_(0)
  {
    swap(v);
  }
#endif
  Vector& operator=(Vector const& v) {
    Vector tmp(v);
    swap(tmp);
    return *this;
  }
#ifndef BOOST_NO_RVALUE_REFERENCES
  Vector& operator=(Vector&& v) {
    swap(v);
    return *this;
  }
#endif

  void swap(Vector& v) {
    using std::swap;
    swap(buf_, v.buf_);
    swap(size_, v.size_);
  }
 
  T& operator[](std::size_t n) {
    return const_cast<T&>(const_cast<Vector const&>(*this)[n]);
  }
  T const& operator[](std::size_t n) const {
    assert(n < size_);
    return buf_[n];
  }
 
  std::size_t size() const { return size_; }
 
private:
  boost::scoped_array<T> buf_;
  std::size_t size_;
};

template <typename T>
void swap(Vector<T>& u, Vector<T>& v)
{
  u.swap(v);
}
 
template <typename Vec1, typename Vec2>
class Plus {
public:
  typedef typename Vec1::value_type value_type;
  BOOST_MPL_ASSERT((boost::is_same<value_type, typename Vec2::value_type>));

  template <typename U1, typename U2>
  friend
  Plus<U1, U2> operator+(U1 const&, U2 const&);

  std::size_t size() const {
    std::size_t const size = lhs_.size();
    assert(size == rhs_.size());
    return size;
  }
 
  value_type operator[](std::size_t n) const {
    assert(n < size());
    return lhs_[n] + rhs_[n];
  }
 
  operator Vector<value_type>() const {
    Vector<value_type> result(size());
    for (std::size_t i = 0, sz = size(); i < sz; ++i)
      result[i] = lhs_[i] + rhs_[i];
    return result;
  }

private:
  Plus(Vec1 const& u, Vec2 const& v)
    : lhs_(u), rhs_(v)
  {}
  Plus(Plus const& other)
    : lhs_(other.lhs_), rhs_(other.rhs_)
  {}
 
  Vec1 const& lhs_;
  Vec2 const& rhs_;
};

template <typename Vec1, typename Vec2>
Plus<Vec1, Vec2> operator+(Vec1 const& u, Vec2 const& v)
{
  return Plus<Vec1, Vec2>(u, v);
}
} // namespace impl
 
using impl::Vector;
 
} // namespace pepshiso
 

int main()
{
  using namespace pepshiso;
  Vector<double> v1(3), v2(3);
  v1[0] = 1, v1[1] = 2, v1[2] = 3;
  v2[0] = 10, v2[1] = 20, v2[2] = 30;

  // ok
  Vector<double> v3 = v1 + v2;

  // bad
  // auto v4 = v1 + v2;
}

Expression Template と auto

これはC++ Advent Calendar jp 2010への参加記事です。

C++の次世代規格であるC++0xには、新しくautoという機能が加わります。autoは次のように使います。

  auto p = std::make_pair(1, 2.0);

上のコードでは、std::make_pair(1, 2.0)の型が推論され、pの型はstd::pairとなります。
以下のような

std::pair<int, double> p = std::make_pair(1, 2.0);

冗長な型の記述をなくせる非常に便利な機能です。constをつけたり、参照にしたりすることもできます。詳しくはこちらを御覧ください。

このようにautoはとても便利な機能なので、C++0xが普及したら多用されることでしょう。しかし、何も考えずにautoを使うと、ごく稀に分かりにくいバグを入れてしまう場合があります。Expression Templateを使ったライブラリを使用する場合です。

Expression Template

Expression Templateとは、式をテンプレートの階層として表現することにより、様々な機能を実現する手法です。Boost.uBLASのような線形代数ライブラリ、Boost.LambdaやBoost.Spiritなどに用いられています。

次のような、簡単なベクトルを表すクラステンプレートを考えます。

template <typename T>
class Vector {
public:
  typedef T value_type;

  explicit Vector(std::size_t n)
    : buf_(new T[n]), size_(n)
  {}
  Vector(Vector const& v)
    : buf_(new T[v.size_]), size_(v.size_)
  {
    std::copy(v.buf_, v.buf_ + v.size_, buf_);
  }
  Vector& operator=(Vector const& v) {
    Vector tmp(v);
    swap(tmp);
    return *this;
  }
  
  void swap(Vector& v) {
    using std::swap;
    swap(buf_, v.buf_);
    swap(size_, v.size_);
  }

  T& operator[](std::size_t n) {
    return const_cast<T&>(const_cast<Vector const&>(*this)[n]);
  }
  T const& operator[](std::size_t n) const {
    assert(n < size_);
    return buf_[n];
  }

  std::size_t size() const { return size_; }

private:
  boost::scoped_array<T> buf_;
  std::size_t size_;
};

このベクトルに対する加法演算子

template <typename T>
Vector<T> operator+(Vector<T> const& u, Vector<T> const& v)
{
  std::size_t size = u.size();
  assert(size == v.size());
  Vector<T> result(size);
  for (std::size_t i = 0; i < size; ++i)
    result[i] = u[i] + v[i];
  return result;
}

を考えます。Vectorの変数v1, v2, v3の和の値を取る新しい変数uを作るには、当然

Vector<double> u = v1 + v2 + v3;

と書きます。ここでは、v1 + v2が実行されて一時オブジェクトを返し、その一時オブジェクトとv3との和によってuが初期化されます。v1 + v2によって無駄な一時オブジェクトが生成されています。Expression Templateを使うと、シンプルな記述を保ちながら一時オブジェクトの生成を避けることができます。

上の加法演算子の代わりに、次のようなPlusクラステンプレート

template <typename Vec1, typename Vec2>
class Plus {
public:
  typedef typename Vec1::value_type value_type;
  BOOST_MPL_ASSERT((boost::is_same<value_type, typename Vec2::value_type>));

  Plus(Vec1 const& u, Vec2 const& v)
    : lhs_(u), rhs_(v)
  {}

  std::size_t size() const {
    std::size_t const size = lhs_.size();
    assert(size == rhs_.size());
    return size;
  }

  value_type operator[](std::size_t n) {
    assert(n < size());
    return lhs_[n] + rhs_[n];
  }

  operator Vector<value_type>() const {
    Vector<value_type> result(size());
    for (std::size_t i = 0, sz = size(); i < sz; ++i)
      result[i] = lhs_[i] + rhs_[i];
    return result;
  }

private:
  Vec1 const& lhs_;
  Vec2 const& rhs_;
};

および加法演算子

template <typename Vec1, typename Vec2>
Plus<Vec1, Vec2> operator+(Vec1 const& u, Vec2 const& v)
{
  return Plus<Vec1, Vec2>(u, v);
}

を定義します。この2つの定義によって、以下の文

Vector<double> u = v1 + v2 + v3;

においてv1 + v2ではVector型の一時オブジェクトは生成されません。実際の計算はオブジェクトuのコンストラクタに渡されるまで遅延されます。ここで、v1 + v2 + v3の型はPlus<...>であることに注意してください。Plus<...>から、Plus<...>の型変換演算子によってVectorが生成されます。この変換はuの型がVectorであると書かれているから起きるのです。

autoを使う

型をVectorと明示的に決めずに、autoを使ったらどうなるでしょうか。

auto u = v1 + v2 + v3;

このとき、uの型はVectorではなくPlus<...>です。これはv1, v2, v3への参照を持っており、たとえばv1の値を変更を変更したらuを評価したときの値も変わります。また、

auto u = Vector<double>(3) + Vector<double>(3);

などとすると、動作未定義への道が開かれます。

補足を書きました。