Cheat Sheet (C/C++ const)

以下は、c でも c++ でも同じ。
X(x) になってるところは全て警告orエラーになる。

void foo(void*x){}

#define C const
#define X(x) /* x */

int main()
{
  int   *   *    p000;
  int   *   * C  p001;
  int   * C *    p010;
  int   * C * C  p011;
  int C *   *    p100;
  int C *   * C  p101;
  int C * C *    p110;
  int C * C * C  p111;

    foo(p000[0]);     foo(p000);     foo(&p000);
    foo(p001[0]);     foo(p001);   X(foo(&p001));
    foo(p010[0]);   X(foo(p010));    foo(&p010);
    foo(p011[0]);   X(foo(p011));  X(foo(&p011));
  X(foo(p100[0]));    foo(p100);     foo(&p100);
  X(foo(p101[0]));    foo(p101);   X(foo(&p101));
  X(foo(p110[0]));  X(foo(p110));    foo(&p110);
  X(foo(p111[0]));  X(foo(p111));  X(foo(&p111));

  return 0;
}

valgrind

ある目的で, こんなテストプログラムを書いてみた.

#include <iostream>
#include <vector>

struct X
{
  std::vector<X*> children;
  X () { std::cout << "+[" << this << "]\n"; }
  ~X () {
    for( size_t i = 0; i < children.size(); ++i ){
      if( children[i] ){ delete children[i]; children[i] = 0; }
    }
    std::cout << "-[" << this << "]\n";
  }
};

int main () {
  X x;
  x.children.resize(2);
  x.children[0] = new X;
  x.children[1] = new X;
  x.children[0]->children.resize(2);
  x.children[0]->children[0] = new X;
  x.children[0]->children[1] = new X;
  return 0;
}

実行結果

$ ./a.out
+[0x7fff9877a320]
+[0x602030]
+[0x602050]
+[0x602090]
+[0x6020b0]
-[0x602090]
-[0x6020b0]
-[0x602030]
-[0x602050]
-[0x7fff9877a320]

とりあえず問題なく動くようだが, さて, 本当に大丈夫だろうか, と思い念のため valgrind を(人生で二度目に)使ってみた.

$ valgrind ./a.out
==25938== Memcheck, a memory error detector.
==25938== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
==25938== Using LibVEX rev 1658, a library for dynamic binary translation.
==25938== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
==25938== Using valgrind-3.2.1-Debian, a dynamic binary instrumentation framewor
k.
==25938== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
==25938== For more details, rerun with: -v
==25938==
==25938== Conditional jump or move depends on uninitialised value(s)
==25938==    at 0x40151F1: (within /lib/ld-2.7.so)
==25938==    by 0x4005052: (within /lib/ld-2.7.so)
==25938==    by 0x4007BA8: (within /lib/ld-2.7.so)
==25938==    by 0x400302E: (within /lib/ld-2.7.so)
==25938==    by 0x4013C14: (within /lib/ld-2.7.so)
==25938==    by 0x4001318: (within /lib/ld-2.7.so)
==25938==    by 0x4000A67: (within /lib/ld-2.7.so)
vex amd64->IR: unhandled instruction bytes: 0x66 0x66 0x66 0x66
==25938== valgrind: Unrecognised instruction at address 0x4015A71.
==25938== Your program just tried to execute an instruction that Valgrind
==25938== did not recognise.  There are two possible reasons for this.
==25938== 1. Your program has a bug and erroneously jumped to a non-code
==25938==    location.  If you are running Memcheck and you just saw a
==25938==    warning about a bad jump, it's probably your program's fault.
==25938== 2. The instruction is legitimate but Valgrind doesn't handle it,
==25938==    i.e. it's Valgrind's fault.  If you think this is the case or
==25938==    you are not sure, please let us know and we'll try to fix it.
==25938== Either way, Valgrind will now raise a SIGILL signal which will
==25938== probably kill your program.
==25938==
==25938== Process terminating with default action of signal 4 (SIGILL)
==25938==  Illegal opcode at address 0x4015A71
==25938==    at 0x4015A71: (within /lib/ld-2.7.so)
==25938==    by 0x4003C0E: (within /lib/ld-2.7.so)
==25938==    by 0x4013C14: (within /lib/ld-2.7.so)
==25938==    by 0x4001318: (within /lib/ld-2.7.so)
==25938==    by 0x4000A67: (within /lib/ld-2.7.so)
==25938==
==25938== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
==25938== malloc/free: in use at exit: 0 bytes in 0 blocks.
==25938== malloc/free: 0 allocs, 0 frees, 0 bytes allocated.
==25938== For counts of detected errors, rerun with: -v
==25938== All heap blocks were freed -- no leaks are possible.
zsh: illegal hardware instruction  valgrind ./a.out

不正な命令って? なんだかおかしい.
でもこれは実は心配なくて, valgrind が新しめの命令に対応していないだけらしい. aptitude install valgrind/testing したら大丈夫になった.

《参考》
http://bbs.archlinux.org/viewtopic.php?pid=315064

template?

下のような書き方で, 途中に出てくる template って何でしょうか?

template<T,S>
struct hoge {
  typedef typename foo<S>::bar Bar;
  typedef typename Bar::template xxx<T,S>::yyy zzz;
};

正解は, 以下のような文脈でテンプレートクラス(構造体)を参照するためのキーワード.

template<typename S>
struct foo
{
  struct bar
  {
    template<typename X,typename Y>
    struct xxx
    {
      struct yyy { };
    };
  };
};

template<typename T,typename S>
struct hoge
{
  typedef typename foo<S>::bar Bar;
  typedef typename Bar::template xxx<T,S>::yyy zzz;
};

int main(){
  hoge<int,int>  x;
}

template をつけずに

  typedef typename Bar::xxx<T,S>::yyy zzz;

と書いて良さそうに思うが, エラーが出る.

error: non-template ‘xxx’ used as template
note: use ‘typename foo<S>::bar::template xxx’ to indicate that it is a template

typename みたいなものか. コンパイラが struct hoge の宣言(あれ?定義?)を読んでいる段階では, まだ foo<S>::bar というクラスは実体化されていないので, xxx という名前がいったい何を指しているのか (型?変数?関数?) 不明であり, template かどうかも不明なので, template と書いてヒントを与えているわけか. なっとく.

this はつけるべきか

C++ (や Java その他の言語)において, メンバ変数や関数のアクセスに this->をつけるべきか否か, という疑問があり, 調べてみた.

this をつけるべきかどうかについてはコーディング規約や好みの問題で議論されている(た). が, 何か決定的な違いがあったような気がしてもやもやしていた.

次の点は, 個人やプロジェクトの嗜好ではなく技術的にはっきりと意識すべき違いをもたらす.

#include <iostream>
struct X { void hoge () { std::cout << "hoge" << std::endl; } };

template <typename T>
struct A { void foo () { T x; x.hoge(); } };

template <typename T>
struct B : public A<T> { void bar () { foo(); } }; /* ※1 */

int main () {
  B<X> b;
  b.bar();
  return 0;
}
x.cpp: In member function ‘void B<T>::bar()’:
x.cpp:8: error: there are no arguments to ‘foo’ that depend on a \
template parameter, so a declaration of ‘foo’ must be available
x.cpp:8: error: (if you use ‘-fpermissive’, G++ will accept your \
code, but allowing the use of an undeclared name is deprecated)

B::foo() は A::foo() を継承しているはずなのに, コンパイラは foo の定義が見つからないといっている.

これを解決する手段は:

  • foo() の呼び出しを書き換えて this->foo() にする
  • foo() の呼び出しを書き換えて A<X>::foo() にする
  • using A<X>::foo; 宣言 (using-declaration) を追加する.

また, foo がテンプレート引数の typename T に依存していれば, thisをつけなくても名前を見つけてくれるらしい. フ..フクザツな!

これは, テンプレート化された基底クラス内の名前へのアクセスするために知っておくべき方法らしい. 実は, 以前読んだ Effective C++ に書いてあった (やっぱり手元に置いてたまに見返さないといけないなぁ).

有名な本に載っているくらいだから, 有名な事実なんだろうけど, 検索でひっかかりにくかったので, こんなエントリを書いてみました, と.

あと, 仮想関数とか継承関係の問題がほかにもあったような気がするのだけど思い出せない. 気のせいかもしれない.

《参考》

追記

cppll_novice にて, どんぴしゃなスレッドが見つかりました...

ADL (argument dependent lookup) とか two-phase name lookup が関係するらしい, と. ふむふむ.

シェルの変数展開

sh, bash, csh 等のシェルで

$ echo ${hoge:-$foo}

とやると, 変数 hoge が空でなければ hoge の値が表示され, 変数 hoge が空であれば, $foo が出力される.

変数=${名前:-}

if [ $変数 ]; then
    変数 = ${名前}
else
    変数 =fi

と等価.

≪参考≫

[c++] 文字列のソーティング

qsort と STL の sort では STL の方が速いよ、という事を以下の記事で読んで知ってました。たしかに整数の配列(正確には vector か)に対しては STL が速いのですが、文字列のソーティングに関しては事情が異なるようです。

C の qsort と STL の sort の速度比較 - bkブログ


最近になって文字列のソーティングをする必要に迫られ、最初は考えずにえいやっと std::sort を使っていたのですが、気になってベンチマークをとって見ると qsort の方が100倍速いという結果になりました。ついでに multikey-quicksort と比べてみると、qsort と同じか少し速いようです*1

ソート方法 g++4.3.1
qsort 1.10秒
stl-sort-func 115.91秒
stl-sort-functor 115.80秒
mulikey-quicksort 0.80秒

ベンチマークには 1MB のテキストファイルを使いました。具体的には、手元にあった XML ファイルを head -c 1m したものです。
参照の局所性だとかテキストデータの性質とか考慮すべき点はたくさんありますが、これだけの差は容易にひっくり返らないのでは、と思います。

うーーん。どっか間違えているのかな。

#include <cassert>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include "mmap_file.hpp"

typedef char         Char;
typedef const Char*  String;

void swap(String& a, String& b) {
    if( &a == &b ) { return; }
    const String  temp = a;
    a = b;
    b = temp;
}

int qsort_cmp(const void* p1, const void* p2) {
    const String&  s1 = *(const String *)p1;
    const String&  s2 = *(const String *)p2;
    return strcmp(s1, s2);
}

bool stl_sort_func_cmp(const String& s1, const String& s2) {
    return strcmp(s1, s2) < 0;
}

struct stl_sort_functor_cmp {
    bool operator()(const String& s1, const String& s2) const { return strcmp(s\
1, s2) < 0; }
};

void do_qsort(String* v, const int v_num) {
    qsort(&v[0], v_num, sizeof(&v[0]), qsort_cmp);
}

void do_stl_sort_func(String* v, const int v_num) {
    std::sort(&v[0], &v[v_num], stl_sort_func_cmp);
}

void do_stl_sort_functor(String* v, const int v_num) {
    std::sort(&v[0], &v[v_num], stl_sort_functor_cmp());
}

void multikey_quicksort(String* begin_, String* end_, int offset) {
    if( begin_ >= end_ ) {
        // do nothing
    }
    else if( end_ - begin_ < 8 ) {
        qsort(&begin_[0], end_ - begin_, sizeof(&begin_[0]), qsort_cmp);
    }
    else {
        assert( begin_ < end_ );

        const String&  pivot = *(begin_ + (end_ - begin_) / 2);
        const char     pivot_char = pivot[offset];

        String*  p1 = begin_;
        String*  p2 = end_ - 1;

        while( p1 < p2 ) {
            if( (*p1)[offset] <  pivot_char ) { ++p1; }
            else if( (*p2)[offset] >= pivot_char ) { --p2; }
            else { swap(*p1, *p2); ++p1; }
        }

        p2 = p1;
        for( String*  p3 = p1; p3 != end_; ++p3 ) {
            if( (*p3)[offset] == pivot_char ) { swap(*p2, *p3); ++p2; }
        }

        if( pivot_char ) {
            multikey_quicksort(begin_, p1, offset  );
            multikey_quicksort(p1,     p2, offset+1);
        }
        multikey_quicksort(p2,     end_, offset  );
    }
}

void do_multikey_quicksort(String* v, const int v_num) {
    multikey_quicksort(&v[0], &v[v_num], 0);
}

typedef void (*SortFunc)(String* v, const int v_num);

void benchmark(const char* name, SortFunc func,
               const String text, const int text_size) {
    assert( text[text_size] == '\0' );

    const int  v_num = text_size + 1;
    String*  v = new String[v_num];
    for( int i = 0; i < v_num; ++i ) {
        v[i] = &text[i];
    }

    const double  start_time = clock();
    func(&v[0], v_num);
    const double  elapsed = clock() - start_time;
    printf("%-20s:\t%.2f\t[%d %d %d]\n", name, elapsed / CLOCKS_PER_SEC,
           v[v_num/4] - text, v[v_num/2] - text, v[v_num-1] - text);
}

int main(int argc, const char** argv) {
    assert( argc == 2 );
    const char*  filename = argv[1];

    const MmapFile  mmap(filename);
    const String  text = mmap.data();
    assert( text );
    const int  text_size = mmap.size();
    assert( text[text_size] == '\0' );

    benchmark("qsort",             do_qsort,              text, text_size);
    benchmark("stl-sort-func",     do_stl_sort_func,      text, text_size);
    benchmark("stl-sort-functor",  do_stl_sort_functor,   text, text_size);
    benchmark("mulikey-quicksort", do_multikey_quicksort, text, text_size);
    return 0;
}

*1:というか、「ついで」と書いておいてなんですが、この mulkey-quicksort の実用上の性能を知りたいというのが本来の動機だったので、「ついで」でも何でもなくこれが本命だということをいま思い出しました。これも yak shaving なのでしょうか。