東方算程譚

Oriental Code Talk ── επιστημηが与太をこく、弾幕とは無縁のシロモノ。

目次

Blog 利用状況

ニュース

著作とお薦めの品々は

著作とお薦めの品々は
東方熱帯林へ。

あわせて読みたい

わんくま

  1. 東京勉強会#2
    C++/CLI カクテル・レシピ
  2. 東京勉強会#3
    template vs. generics
  3. 大阪勉強会#6
    C++むかしばなし
  4. 東京勉強会#7
    C++むかしばなし
  5. 東京勉強会#8
    STL/CLRによるGeneric Programming
  6. TechEd 2007 @YOKOHAMA
    C++・C++/CLI・C# 適材適所
  7. 東京勉強会#14
    Making of BOF
  8. 東京勉強会#15
    状態遷移
  9. 名古屋勉強会#2
    WinUnit - お気楽お手軽UnitTest

CodeZine

  1. Cで実現する「ぷちオブジェクト指向」
  2. CUnitによるテスト駆動開発
  3. SQLiteで組み込みDB体験(2007年版)
  4. C++/CLIによるCライブラリの.NET化
  5. C# 1.1からC# 3.0まで~言語仕様の進化
  6. BoostでC++0xのライブラリ「TR1」を先取りしよう (1)
  7. BoostでC++0xのライブラリ「TR1」を先取りしよう (2)
  8. BoostでC++0xのライブラリ「TR1」を先取りしよう (3)
  9. BoostでC++0xのライブラリ「TR1」を先取りしよう (4)
  10. BoostでC++0xのライブラリ「TR1」を先取りしよう (5)
  11. C/C++に対応した、もうひとつのUnitTestFramework ─ WinUnit
  12. SQLiteで"おこづかいちょう"
  13. STL/CLRツアーガイド
  14. マージ・ソート : 巨大データのソート法
  15. ヒープソートのアルゴリズム
  16. C++0xの新機能「ラムダ式」を次期Visual Studioでいち早く試す
  17. .NETでマンデルブロ集合を描く
  18. .NETでマンデルブロ集合を描く(後日談)
  19. C++/CLI : とある文字列の相互変換(コンバージョン)
  20. インテルTBBによる選択ソートの高速化
  21. インテルTBB3.0 によるパイプライン処理
  22. Visual C++ 2010に追加されたSTLアルゴリズム
  23. Visual C++ 2010に追加されたSTLコンテナ「forward_list」
  24. shared_ptrによるObserverパターンの実装
  25. .NETでマンデルブロ集合を描く(番外編) ── OpenCLで超並列コンピューティング
  26. StateパターンでCSVを読む
  27. 状態遷移表からStateパターンを自動生成する
  28. 「ソートも、サーチも、あるんだよ」~標準C++ライブラリにみるアルゴリズムの面白さ
  29. インテルTBBの同期メカニズム
  30. なぜsetを使っちゃいけないの?

@IT

  1. Vista時代のVisual C++の流儀(前編)Vista到来。既存C/C++資産の.NET化を始めよう!
  2. Vista時代のVisual C++の流儀(中編)MFCから.NETへの実践的移行計画
  3. Vista時代のVisual C++の流儀(後編) STL/CLRによるDocument/Viewアーキテクチャ
  4. C++開発者のための単体テスト入門 第1回 C++開発者の皆さん。テスト、ちゃんとしていますか?
  5. C++開発者のための単体テスト入門 第2回 C++アプリケーションの効率的なテスト手法(CppUnit編)
  6. C++開発者のための単体テスト入門 第3回 C++アプリケーションの効率的なテスト手法(NUnit編)

AWARDS


Microsoft MVP
for Visual Developer - Visual C++


Wankuma MVP
for いぢわる C++


Nyantora MVP
for こくまろ中国茶

Xbox

Links

記事カテゴリ

書庫

日記カテゴリ

2012年5月13日 #

5/19 わんくま同盟東京勉強会#71 は「禁.NET」

来週土曜日、わんくま同盟東京勉強会っす。

.NETの一切出てこない勉強会やってもいぃんぢゃね?」
...言いだしっぺの法則発動、僕がディレクタやることに。

Lua と Java と C++ と Windows8 をネタに一日過ごします。
目玉は荒井さんのMetroなおハナシかなやっぱ。
WinRTとやらのおかげでXAMLなアプリがnativeで書けちゃうのね。

posted @ 1:19 | Feedback (0)

コンプガチャのヤバさ加減

N種のカードをガチャする。どのカードを引くかはどれも同確率。
N種のカードをコンプするには何回ガチャすることになるんだろ。
やってみた:

#include <iostream>
#include <random>
#include <set>
#include <map>
#include <string>

using namespace std;

int main() {
  const int N = 10; // カード数
  const int trials = 1000; // 試行回数

  mt19937 engine; // メルセンヌ・ツイスター
  uniform_int_distribution<int> dist(0,N-1); // 0..N-1 一様分布
  auto gacha = [&]() { return dist(engine); }; // 0..N-1 一様乱数
  set<int> items; // 入手したカード種
  map<int,int> hist; // 度数分布表

  int max_trials = 0;
  for ( int i = 0; i < trials; ++i ) {
    int draws = 0;
    items.clear();
    // コンプするまでガチャを繰り返し、
    // ガチャ数を度数分布表に累積する
    while ( items.size() != N ) {
      ++draws;
      items.insert(gacha());
    }
    ++hist[draws];
    if ( max_trials < draws ) max_trials = draws;
  }
  // 度数分布を出力する
  for ( int i = N; i <= max_trials; ++i ) {
    cout << i << ':' << string(hist[i],'#') << endl;    
  }  
}

実行結果はコチラ:
10:
11:
12:###
13:########
14:###############
15:############
16:##############
17:#############################
18:#######################################
19:#########################################
20:#########################################
21:##############################################
22:############################
23:######################################################
24:####################################
25:##############################################
26:##########################################
27:###########################################
28:##############################################
29:###########################################
30:################################
31:####################################
32:#####################################
33:##################
34:##########################
35:############################
36:####################
37:###################
38:###############
39:#############
40:####################
41:#################
42:##############
43:################
44:#############
45:#######
46:###########
47:########
...
N=10 のとき、23回あたりにピークがありますな。
一回100円としてコンプまでにおおむね2300円。
上の結果は途中で切ってるけど、7300円つぎ込んだバカがひとりいました。

posted @ 1:06 | Feedback (0)

2012年4月28日 #

Visual Studio 11 から本気出す! WPF with C++/CLI



レビューやらせていただきましたよ。
んで、せっかくだから「周回遅れにもほどがあんぞヲイ」なWPFに手を付けます。
いやね、Visual Studio 11でよぅやっとC++/CLIのインテリセンスが復活してくれたんで、
マンドクセーことやる気になったっちゅーのが本音。
てかさ、WPFアプリケーションてばC++の出番ナシなのが癪に障るんで、
ひな形生成だけをC#にやらせ、残りはぜーんぶC++/CLIで書いてみるココロミ。

おためしにこしらえたのは毎度毎度のカウンター。
「3.2.3 視覚的デザインツールの利用」にあったMVVMをほとんどそのままパクらせてもらいました。

<Window x:Class="DataBindingSample.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="データ バインディング サンプル" Width="193" SizeToContent="Height" Height="157">
    <StackPanel>
        <TextBox Text="{Binding Count}" FontSize="36" FontWeight="Bold" TextAlignment="Center" />
        <Button Content="+" Command="{Binding IncCommand}" />
        <Button Content="-" Command="{Binding DecCommand}" />
    </StackPanel>
</Window>

XAMLはこんな↑カンジね、表示とボタンをそれぞれ CountとIncCommand/DecCommandにバインドしてます。
以降C#からはしばらくオサラバ、C++/CLIでCLRクラスライブラリを用意して参照させます。
ViewModel がコレ↓

#ifndef MAINWINDOWVIEWMODEL_H__
#define MAINWINDOWVIEWMODEL_H__

namespace DataBindingSample {

  public ref class MainWindowViewModel : public System::ComponentModel::INotifyPropertyChanged {
  public:
    property int Count {
      int get();
      void set(int value);
    }

    virtual event System::ComponentModel::PropertyChangedEventHandler^ PropertyChanged;

    void attachCommand(System::Action<Object^>^ inc, System::Action<Object^>^ dec);
    void Update(int count);

    property System::Windows::Input::ICommand^ IncCommand 
      { System::Windows::Input::ICommand^ get(); }
    property System::Windows::Input::ICommand^ DecCommand 
      { System::Windows::Input::ICommand^ get(); }

  private:
    int _Count;
    System::Windows::Input::ICommand^ incCommand;
    System::Windows::Input::ICommand^ decCommand;
  };
 
}

#endif

attachCommandでView(のIncCommand/DecCommand)からModelに、
UpdateでModel(のカウント値変更)をViewに飛ばします。

カウンタ本体:Counter と ViewModelに接続するための CounterModel はそれぞれ:

#ifndef COUNTER_H__
#define COUNTER_H__

namespace DataBindingSample {

  public ref class Counter {
  public:
    void inc();
    void dec();
    int count();

  private:
    int count_;
  };

  public ref class CounterModel : Counter {
  public:

    // Model→ViewModel
    event System::Action<int>^ CountUpdatedHandler;

    // ViewModel→Model 
    property System::Action<Object^>^ Increment { System::Action<Object^>^ get(); }
    property System::Action<Object^>^ Decrement { System::Action<Object^>^ get(); }

  private:

    void Notify();

    void inc(Object^ dummy);
    void dec(Object^ dummy);

  };

}

#endif

CountUpdateHandlerとIncrement/Decrement がViewModelとの接続ポートになってます。

んでもって MainWindow, MainWindowViewModel, CounterModel をがしゃがしゃ繋ぐトコ
をC#側にねじ込みます。 MainWindowViewModel と CounterModel は App のstaticメンバ
にしちゃいました。

/* 
 * App.xaml.cs
 */
using System.Windows;

namespace DataBindingSample {

  public partial class App : Application {

    public static MainWindowViewModel ViewModel {
      get { 
        if ( viewmodel_ == null )
          viewmodel_ = new MainWindowViewModel();
        return viewmodel_;
      }
    }

    public static CounterModel Model {
      get {
        if ( model_ == null )
          model_ = new CounterModel();
        return model_;
      }
    }

    public static MainWindowViewModel viewmodel_;
    public static CounterModel model_;
  }

}

/*
 * MainWindow.xaml.cs
 */
using System.Windows;

namespace DataBindingSample {

  public partial class MainWindow : Window {
    public MainWindow() {
      InitializeComponent();
      this.DataContext = App.ViewModel;
      App.ViewModel.attachCommand(App.Model.Increment, App.Model.Decrement);
      App.Model.CountUpdatedHandler += App.ViewModel.Update;
    }
  }

}

C++/CLI側の実装(.cpp)は割愛。ソリューションまるごとうpするから読んでやって。

白状すればMVVMってハジメテなの。おもきし我流だし。ガスガス突っ込んでやってくだせ。

posted @ 23:51 | Feedback (1)

2012年4月6日 #

青少年のためのピーターと謝肉祭

本日の衝動買い:

プロコフィエフ 「ピーターと狼
サン・サーンス 「動物の謝肉祭
ブリテン 「青少年のための管弦楽入門
 小沢征爾/ボストン交響楽団

地獄のミサワ 世界のオザワが曲中のしゃべくりまで
やってくれちゃってるってんで買っちゃいました。

…いぃねぇ、小学校の音楽室で聴いたヤツよね♪

ボストンらっぱが元気でよろしいな。
ベルリンとかもちろん超一流で文句のつけようもないけれど、
ボストンやフィラ管の威勢のいいスカッとした響きは好きですよー

もいっちょ:



ロードショー封切りで観たしDVDも持ってるけど、
マザボ交換ついでにBlu-ray driveに取り替えたくせに
data用にしか使ってなかったんで一枚くらいは。

うわー、Blu-rayの情報量ハンパないわ。
こんなの観ちゃうとDVDはショボいねー。
音も良いすねー、
サー・ネビル・マリナーの曲がツヤツヤしてます。

posted @ 17:58 | Feedback (0)

2012年3月30日 #

いまさらながらCのおてつだい

僕のお仕事は社内相談事よろず承り係みたいなもんで、開発絡みのヘルプ・デスクと申しましょうか、ライブラリやツールの調査/評価とか、お望みとあらばサンプルコード書いてあげたりとかもやってます。

先日社内に山とあるプロジェクトの各リーダーにアンケート投げて開発環境調査やってるヒトとお話ししてたらば、社内ではCでの開発が(かなり減ってはいるものの)未だ現役バリバリなんだとか。

それじゃこんなオモチャはどうだろう、ってんで作ったのが「CUnit用ハリボテ生成機:cusg」っす。
コマンドラインから
> cusg foo=fok1+fok2+fng1+fng2 > main.c
とかやると、fok1,fok2,fng1,fng2 の4つのテスト(ナカミはからっぽ)が定義されたfoo_test.cができます。
これと標準出力から拾ったmain.cをコンパイルし、CUnit.libとリンクすればとりあえずCUnit-testができちゃうです。

posted @ 22:57 | Feedback (0)

2012年3月28日 #

Visual Studio 11 : 祝・インテリセンス復活

60GBのSSDにWindows 7 Ultimate 64 まるっとぶち込んで残り十数GB、しばらく使って何度かUpdateかけたらあえなくパンクしちまいましたよコノヤロー。

おかげで先の土日はせっせと再インスコ、OS入れてOffice入れてVisual Studio入れてVisual Studio入れてVirtualBox入れてVisual Studio入れてVisual Studio入れてたらお休み終わっちゃったヨ

そこいらへんに転がってた1TB-HDに引っ越して、余ったSSDにVisual Studio Solution群を納めました。うわーSSDにSolution置くとめっさ快適です。ビルドがやたらと早い。Solution丸ごとre-buildしてもあっちゅーまですわ(論理8coreはダテじゃねぇ)。

Visual Studio 11 Beta がなかなかに面白くて毎日くだらんコード書いてはコンパイラいぢめて遊んでます。いぢわるスタジオです。
ともかくも インテリセンス/CodeSnippetが使えるよになり喜ばしい限り。

<?xml version="1.0" encoding="utf-8"?>
<CodeSnippets
  xmlns="http://schemas.microsoft.com/VisualStudio/2005/CodeSnippet">

    <CodeSnippet Format ="1.0.0">
        <Header>
            <Title>C++ class decl.</Title>
            <Author>επιστημη</Author>
            <Description>C++ クラス宣言</Description>
            <Shortcut>classdecl</Shortcut>
        </Header>
        <Snippet>
            <Declarations>
                <Literal>
                    <ID>CLASS</ID>
                    <ToolTip>クラス名</ToolTip>
                    <Default>CLASS</Default>
                </Literal>
            </Declarations>
            <Code Language ="CPP">
                <![CDATA[class $CLASS$ {
public:
  $CLASS$(); // default ctor
  $CLASS$(const $CLASS$& other); // copy ctor
  virtual ~$CLASS$(); // dtor
  $CLASS$& operator=(const $CLASS$& other); // copy op.
private:
};
]]>
            </Code>
        </Snippet>
    </CodeSnippet>

    <CodeSnippet Format ="1.0.0">
            <Header>
                <Title>C++ class impl.</Title>
                <Author>επιστημη</Author>
                <Description>C++ クラス実装</Description>
                <Shortcut>classimpl</Shortcut>
            </Header>
            <Snippet>
                <Declarations>
                    <Literal>
                        <ID>CLASS</ID>
                        <ToolTip>クラス名</ToolTip>
                        <Default>CLASS</Default>
                    </Literal>
                </Declarations>
                <Code Language ="CPP">
                    <![CDATA[// default ctor
$CLASS$::$CLASS$() {
}

// copy ctor
$CLASS$::$CLASS$(const $CLASS$& other) {
  if ( this != &other ) {
  }
  return *this;
}

// dtor
$CLASS$::~$CLASS$() {
}

// copy op.
$CLASS$& $CLASS$::operator=(const $CLASS$& other) {
  return *this;
}
]]>
                </Code>
            </Snippet>

        </CodeSnippet>
</CodeSnippets>

こんなの書いてスニペット・マネージャにインポートしとくと幸せになれたり。

posted @ 22:20 | Feedback (1)

2012年3月27日 #

stateless lambda (そのさん)

stateless lambda は関数ポインタに暗黙変換できるっちゅーんだから、
delegateだって作れるはずよね...

#include <iostream>

using namespace System;
using namespace std;

public ref class Counter {
public:
  delegate void OnUpdate(Counter^ counter);
  Counter() : value_(0) {}
  void incr() { ++value_; handler(this); }
  property int count { int get() { return value_; }}
  event OnUpdate^ handler;
private:
  int value_;
};

void print_fun(Counter^ counter) {
  cout << counter->count << endl;
}

int main() {
  Counter^ counter = gcnew Counter();
  auto print_lambda = [](Counter^ counter) { cout << counter->count << endl; };
  counter->handler += gcnew Counter::OnUpdate(print_fun);    // OK
  counter->handler += gcnew Counter::OnUpdate(print_lambda); // error
  counter->incr();

  return 0;
}

...ダメでした orz
くやしいのでConnectにfeedbackしたです。 voteしてくれさい。

posted @ 22:41 | Feedback (0)

2012年3月16日 #

stateless lambda (そのに)

Visual Studio 11 Beta にて:

#include <iostream>
#include <locale>
#include <Windows.h>

using namespace std;

int main() {
  wcout.imbue(locale("japanese"));
  // EnumWindows に与える CALLBACK に stateless lambda を。
  EnumWindows([](HWND hWnd, LPARAM lParam)->BOOL {
                TCHAR buf[256];
                GetWindowText(hWnd, buf, 256);
                if ( buf[0] != L'\0' ) {
                  *reinterpret_cast<wostream*>(lParam) << buf << endl;
                }
                return TRUE;
              }, 
              reinterpret_cast<LPARAM>(&wcout));
}

あらおもしろい。stateless lambda を Win32-callback に使えるのね。
ふしぎねー、コンパイラくんてば __cdecl か __stdcall かを判別して
善きに計らってくれちゃうのね。

posted @ 21:51 | Feedback (2)

2012年3月9日 #

range based for

C++11の新機能 range based for
C#でいうところの foreach ( ほげほげ in ぱよぱよ) でありんす。
幸いなことに VC++11β でも使えます♪
# 残念なことにインテリセンスが赤線引いてくれやがりますけど

オモシロイネー、コレ。
for_each(c.begin(), c.end(), [](int n) { cout << n << endl;});
でももちろんかまわんけども
for ( auto n : c ) { cout << n << endl; }
って書けちゃうんだねー。
lambdaと違ってautoを許すのがナイス♪

コンテナとして許されるのは フツーの配列はもちろん、
array, vector, list ... コンテナはみんなOKだし、
こんなの↓も許す。
map<int,string> c;
for ( auto item : c ) { cout << item.first << ',' << item.second << endl; }

ちょいちょいとあすんでみたところ、begin()/end() を持ってて、
そいつらが ++, *, != できるもんを返せば
いいみたいね。

#include <iostream>

using namespace std;

template<typename T>
class iterap {
public:
  iterap(T t) : value_(t) {}
  iterap(const iterap& other) : value_(other.value_) {}
  iterap& operator=(const iterap& other) { value_ = other.value_; }
  T operator*() const { return value_; }
  iterap& operator++() { ++value_; return *this; }
  iterap  operator++(int) { return value_++; }
  friend bool operator==(const iterap& x, const iterap& y) { return x.value_ == y.value_; }
  friend bool operator!=(const iterap& x, const iterap& y) { return !(x == y); }
  friend bool operator< (const iterap& x, const iterap& y) { return x.value_ < y.value_; }
  friend bool operator>=(const iterap& x, const iterap& y) { return !(x < y);  }
  friend bool operator> (const iterap& x, const iterap& y) { return y < x;     }
  friend bool operator<=(const iterap& x, const iterap& y) { return !(y < x);  }
private:
  T value_;
};

template<typename T>
class iterange {
public:
  iterange(T first, T last) : first_(first), last_(last) {}
  iterap<T> begin() const { return iterap<T>(first_); }
  iterap<T> end() const { return iterap<T>(last_); }
private:
  T first_;
  T last_;
};


int main() {
  for ( auto n : iterange<int>(0,6) ) {
    cout << n << ' ';
  }
}

posted @ 19:47 | Feedback (1)

2012年3月4日 #

Visual Studio 11 の C++ UnitTest Framework (そのに)

Visual Studio 11 Express Beta ではどうなんだ、と。

残念ながらWin7にインスコ試みたところハネられました。Win8-onlyのようです。
Windows VirtualPC では Win8 が作れんかったので、OracleさんトコのVirtualBox
起こしてWin8 Consumer Preview ねじ込み、VS11 express beta をインスコ。
 


おお、これはスバラシイ。
ビギナ向け(?)なExpress版でUnitTestが使えることの意義は大きいよ。

posted @ 13:35 | Feedback (4)

2012年2月29日 #

stateless lambda

 

[]で始まり、lamda外のなにものもcaptureしていない

 stateless lambda function pointer に暗黙変換できる」

とあります。

さっそく試してみんよ。

#include <iostream>
#include <cstdlib>

using namespace std;

int main() {
  const int N = 10;
  int data[N] = { 9, 7, 5, 3, 1, 0, 2, 4, 6, 8 };
  // qsortの比較関数にlambdaをねじ込む
  qsort(data, N, sizeof(int),
        [](const void* x, const void* y)->int
          { return *static_cast<const int*>(x) - *static_cast<const int*>(y);}
       );
  for ( int i = 0; i < N; ++i ) cout << data[i] << ' ';
  cout << endl;
}
あー、おもしろいねコレ。C-functionのコールバックにlambdaを指定できちゃうです。
 

posted @ 21:34 | Feedback (4)

2012年2月26日 #

Visual Studio 11 の C++ UnitTest Framework

おやまぁ、Developer Preview 版 Visual Studio 11 が
C++-native な UnitTest Framework をサポートしてるぢゃあーりませんか。

雰囲気はWinUnitに近く、テスト・プロジェクトをDLLでこしらえ、
そいつを Visual Studio 備え付けの TestRunner で呼び出すよぉな。

まずはテスト・プロジェクトを用意:

しかるのちテストを書く。

#include "stdafx.h"
#include "CppUnitTest.h"
#include <Counter.h>

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace TestCounter {

  TEST_CLASS(TestCounter) {
  public:
                
    TEST_METHOD(test_initialize) {
      Counter c;
      Assert::AreEqual(0, c.get());
    }

    TEST_METHOD(test_incr) {
      Counter c;
      c.incr();
      Assert::AreEqual(1, c.get());
    }

  };

}

んでもってbuildし、UnitTest Explorer から実行すると:

おおぉ、やってくれっぢゃねぇか♪

posted @ 18:51 | Feedback (3)

2012年2月25日 #

CodeZineに書きますたー

ひさびさに一本、CodeZineに

なぜsetを使っちゃいけないの?」 てゆー。

はてブやらTwiterやらにぼちぼちと反響いただいております、
ありがたやありがたや。

「コ難しくするくらいなら素直にset使っとけばぁ?」ってコメント、
少なくないっすね。うん、僕もそう思う。今どきのCPU/メモリ
ならそんなに遅くならんし少々大喰らいでも大した問題には
ならんですから。

てか、こんなコマケーことに気を「使える」とこが
C++の持ち味なのかなー思うですよ。

posted @ 17:23 | Feedback (4)

2012年2月7日 #

たらこスパ

ちょー簡単。

スーパーの鮮魚売場で"たらこ"もしくは"めんたいこ"を入手。袋の割れた「バラ子」で充分。
それとバター。んでもってスパゲティ。いぢょ。

スパゲティ茹でる。その間にボウルにたらこ投入。指でしごいて袋(薄皮)から捻り出す。
バター投入してスタンバイ。茹であがったらボウルに放り込んで混ぜる。
パサつくようならバター(サラダ油も可)追加。できあがり。

うまいよー、「パスタにからめるだけのたらこスパソース」とか売ってるけど、あれよか数段ウマいす。

posted @ 21:50 | Feedback (2)

2012年1月21日 #

boost 1.48.0 flat_set はえー

ひっさしぶりに boost 触ってみた。
最新版 1.48.0 におもしろそげなコンテナ: flat族を見つけたのね。

標準の std::set(およびその一味)は連想コンテナの実装に二分木を使ってるんだが、
boost::container::flat_set(およびその一味)はベタなvectorを使ってる。
そのため要素の格納の際、左右の枝のためのポインタを要するstd::setより省メモリ

要素の挿入にはそこそこの時間がかかるけど、
lookup(検索)はバイナリ・サーチが使え、二分木のトラバースよか高速との触れ込み。
試してみんべ:

#include <iostream>
#include <set>
#include <boost/container/flat_set.hpp>
#include <boost/chrono.hpp>

using namespace std;
using namespace boost::container;
using namespace boost::chrono;

int main() {
  const int N = 1000000;
  std::set<int> s;
  flat_set<int> f;

  // [0..N) を set/flat_setに挿入
  for ( int i = 0; i < N; ++i ) {
    s.insert(i);
    f.insert(i);
  }
  system_clock::time_point start;
  duration<double> sec;

  // [0..N) を set から lookup
  start = system_clock::now();
  for ( int i = 0; i < N; ++i ) {
    s.find(i);
  }
  sec = system_clock::now() - start;
  std::cout << "set      " << sec.count() << " seconds\n";

  // [0..N) を flat_set から lookup
  start = system_clock::now();
  for ( int i = 0; i < N; ++i ) {
    f.find(i);
  }
  sec = system_clock::now() - start;
  std::cout << "flat_set " << sec.count() << " seconds\n";
}

実行結果:
set      0.069004 seconds
flat_set 0.0480028 seconds

ホンマや。確かに速い。

posted @ 1:53 | Feedback (3)