コンテナからの要素削除

ひさしぶりに書くとこんな事も忘れてしまっていた.下記のコードでセグメンテーションフォールトが出た. でも,そもそもremove_ifをこんな時には使うようだ.

std::list<int> lis {0,1,2,3,4,5,6,7,8,9};
for (auto itr=lis.begin(); itr!=lis.end(); ++itr) {
  if (*itr == 2)
    lis.erase(itr);
}

どこで出るかと言うと,eraseした後のforループの更新(++itr). lis.erase(itr)でitr(何かしらのアドレスitr)が指す先が消される.と,そのポインタitrもなくなって++itrが出来なくなる? ならばということで,

std::list<int> lis {0,1,2,3,4,5,6,7,8,9};
for (auto itr=lis.begin(); itr!=lis.end(); ) {
  if (*itr == 2)
    lis.erase(itr++); // auto t = itr; itr = itr+1; lis.erase(t)と同じことになる.
  else
    ++itr;
}

もうforっぽくないので,whileで似たように書ける.

std::list<int>::iterator itr = v.begin();
for (itr != v.end()) {
    if (*itr == 2) {
        itr = lis.erase(itr); // eraseの返り値は次のポインタ
    } else ++itr;
}

ポリモルフィズム

目的

  • オブジェクトによって振る舞いを変える.

方法

  • 子クラスのポインタを親クラスのポインタに代入するのがミソ.(子クラスは親クラスのポインタに代入可能.逆はだめ.)
  • それを使う側は親クラスのポインタを引数なりにして受け取って,親クラスのメソッドを呼ぶ.
  • その時に,親クラスでvirtual宣言しておけば,親クラスのポインタであっても,実態が子クラスのポインタである場合は子クラスのメソッドを実行する.
  • これで,分岐したい処理の分だけ子クラスで分岐できる.
  • virtual付けたときと付けないときの違いは下記を参照.virtual付けていないと親クラスのメソッドが実行される.
class Parent {
protected:
  int x_;
public:
  int get_x() const {return x_;}
  void set_x(int x) {x_ = x;}
  void non_virtual_func() {cout << "I'm parent.\n";}
  virtual void virtual_func() {cout << "I'm parent.\n";}
  Parent(int x): x_(x) {}
};

class Child : public Parent {
public:
  void non_virtual_func() {cout << "I'm child.\n";}
  virtual void virtual_func() {cout << "I'm child.\n";}
public:
  Child(int x) : Parent(x) {}
};

int main()
{
  //std::make_unique<Parent> p = std::make_unique<Child>(1);
  Parent* p = new Child(1);
  cout << "non virtual function call: ";
  p->non_virtual_func();
  cout << "virtual function call: ";
  p->virtual_func();

  return 0;
}

テンプレートのメモ

基本

型推論

  • 関数テンプレートの場合は型推論されるので,実体化の際に明示的に型を書かなくても良い.
  • クラステンプレートの場合には推論されないので注意.

特殊化

  • テンプレート関数,テンプレートクラスがある時に特定の型でだけ別の動きをしたい場合には,その型専用のテンプレートを作れば特殊化される.
  • あるテンプレートを具象化すること(普通にテンプレートの実態?を作ること)も特殊化と言う場合があって混乱するので注意.
#include <iostream>
#include <string>

using namespace std;

template <typename X>
X add(X a, X b){ return a+b;}

// 特殊化
template<>
double add(double a, double b) {return a+b;}

int main()
{
  cout << add<int>(1, 2) << "\n";
  cout << add(1, 2) << "\n";                // 型が推論される
  cout << add<float>(1.0, 2.0) << "\n";
  cout << add(1.0, 2.0) << "\n";            // 同様
  cout << add<string>("Oda", "Nobunaga") << "\n";
  //cout << add("Oda", "Nobunaga") << "\n"; // これはエラー.char*になって'+'が無いと怒られる.
  return 0;
}

値引数,値パラメタ

  • テンプレートの宣言,定義に型ではなくて値を書く例を見る.例えば下記.hoge1, hoge2はそれぞれNが1,2で実態が作られる.
  • 実体化するインスタンス毎に設定値を変えたい場合に使うのかな?とも思うけどテンプレートでやらなくても普通にコンストラクタでやれば?と思う.どういう時に使うんだろう?コンパイル時に設定値も分けて実態を作りたい時かな?
template<int N>
class Hoge {
private:
  int m_ = N;
public:
  int get_m() const {return m_;}  
};

int main()
{
  Hoge<1> hoge1;
  Hoge<2> hoge2;

  cout << hoge1.get_m() << "\n";
  cout << hoge2.get_m() << "\n";
  return 0;
}

引数を柔軟に取るためのテンプレート

  • 何という名前のテクニックなのか知らないけどたまに見る.
  • ある関数やメンバ関数に与える引数を,その引数が適切に定義されていれば型の正式な名前に依らずに受け取りたい時とかに使える.
  • 例えば,色々な人(Human)の定義が作り得るとして,それらの人全般を受け取るような関数を作る時.下記例は,Human型はsay_helloというメンバ関数さえあれば,どんな型のものであろうと渡すことが出来る.実際に,NobunagaもIeyasuもHumanとは関係ないけど,say_helloがあるのでHumanの満たすべき性質は満たせている.
template<typename Human>
void call_say_hello(Human human) {human.say_hello();}

class Nobunaga {
public:
  void say_hello() {cout << "I'm Nobunaga.\n";}
};

class Ieyasu {
public:
  void say_hello() {cout << "I'm Ieyasu.\n";}
};

int main()
{
  Nobunaga nobunaga;
  Ieyasu   ieyasu;
  call_say_hello(nobunaga);
  call_say_hello(ieyasu);
  return 0;
}

二分探索 バイナリサーチ

  • 簡単でかつ効果が高いのでよく使うサーチ.
  • 意外と境界条件でバグりがち.味噌は,右側を配列の外において置く.
#include<iostream>
#include<vector>
using namespace std;
int main() 
{
  int d, n;
  cin >> d;
  cin >> n;
  vector<int> v(n);
  for (int i=0; i<n; ++i) cin>>v[i];

  int l=0, r=v.size(), m=(l+r)>>1;
  while (l<r) {
    if (d == v[m]) {
      cout << "find: " << m << "\n";
      return 1;
    }
    else if (d < v[m]) 
      r=m;
    else
      l=m+1;
    m=(l+r)>>1;
  }
  cout << "not found\n";
  return 0;
}

線形探索と番兵アルゴリズム

  • 番兵アルゴリズムはただの書き方の問題だと思ってたけど,高速化のテクニックだった,という話.
  • forでvectorの要素を回す時に,毎回比較演算が行われるけど,それが勿体無いという場合に,絶対に止まるよに番兵を置いておいて無限ループで回すというのが番兵テクニックみたいだ.
  • アルゴリズム本体が軽い時,かなり性能がシビアに要求される時には必要なのかな?

forで書く場合(比較は2回)

for (int i=0; i<n; ++i) {         // ここで1回
  if (vec[j] == key) return true; // ここで1回(計2回)
}
return false;

番兵で書く場合(比較は1回)

vector<int> vec(n+1);       // +1個分確保
vec[n] = key;               // 末尾に番兵を置く
int j = 0;
while (1) {                 // 無限ループが絶対に止まることが保証される
  if (vec[j] == key) break; // ここの比較だけで良い
  ++j;
}
if (j==n) return false;// 末尾まで行っていたら失敗
else return true;

プロコンと標準入出力

プロコンをかじってみたら,標準入出力で躓いた...ということで,使い方を整理しておく.

scanf

  • 空白文字または改行文字を区切りとして,フォーマットに従って変換して変数に取り込む.2つ以上フォーマット指定子を指定すれば一度にその分だけ読み進む.注意として,最後の空白や改行自体は変換後にバッファに残っている.よって,連続して読み込む場合に前回の改行や空白文字が残ることになるので,2回目以降使う場合はfflush(stdin)する.
  • 整数はd, 浮動小数点数はlf, 文字はc, 文字列はsで受け取る.但し,sは空白は含まないので注意.
  • 戻り値は,成功のときは変換した変数の数,ミスの場合はEOF.
// 0 * 入力で終了.
#include <stdio.h>
int main()
{
  int a, b;
  scanf("%d %d", &a, &b);
  while (a != 0) {
    printf("a:%d, b:%d\n", a, b);
    fflush(stdin);
    scanf("%d %d", &a, &b);
  }
}

fgets/sscanf

  • バッファサイズが指定できないことや,フォーマットを無視した入力の取扱が面倒なので,普通はscanfは使わずにfgetとsscanfを組合せて使う.これも合わせて覚えておく.
  • sscanfの戻り値は,フォーマットに従って入力された変数の数.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
main()
{
    FILE    *fp;
    char    buf[256]; // バッファサイズを指定する
    double  d1, d2;

    if( (fp = fopen( "hoge.dat", "r" )) == NULL ) {
        printf( "ERROR: file can't be opened." );
        exit(1);
    }
    while( fgets( buf, sizeof(buf), fp ) ) {
        if( strncmp(buf,"//",2) == 0 || strcmp(buf,"\n") == 0 ) // skip comment line
            continue;
        if( sscanf( buf, "%lf %lf", &d1, &d2 ) != 2 ) {
            printf( "WARNING: format does not match.\n" );
            break;
        }
        printf( "d1=%.1f, d2=%.1f\n", d1, d2);
    }
    fclose( fp );
}

cin

  • 空白区切りで文字列をパースしていく,改行文字は取り込まれないなどscanfとほぼおなじ動きをする.
  • 関数じゃなくて(オーバーロードされた)演算子
#include <iostream>
int main() {
  int a, b;
  cin >> a >> b; // "1 2" のようなラインを読み取る書き方
}

n個の数列を入力する例

// n
// 1 2 3 4 5
int n;
cin >> n;
vector<int> v(n); // (当然)コンストラクタは変数でも良い
for(int i = 0; i < v.size(); ++i) cin >> v[i];

文字列として連続して受け取る

  • cin >> がEOFを読み込んだ時にfalseとなることを利用する.
string str;
while (cin >> str) { // EOF(Ctrl-D)入力時に抜ける
 ...
}
//同じことの別の書き方
while (1) {
  cin >> str;
  if (cin.eof()) break;
  ...
}

C++ファイル分割

またまた久しぶりにC++を書こうとすると,ヘッダファイル,ファイル分割を忘れてしまっていたので,整理.

全般

  • 共通にするものをヘッダに書く(当たり前だけど).
  • 宣言と定義の違いを持つこと.宣言は名前だけ.定義は実態を生成する文.
  • 定義は(普通)は一つ.ということで関数の定義や,変数の定義は書かない.
  • 逆に変数の宣言(extern)はヘッダに書く.共通したいから.
  • グローバル変数は実態を(何処か1つの)ソースファイルに書いて,そのヘッダにexternで宣言する.他のソースをはそのヘッダをインクルードする.
  • static変数は(普通は)ヘッダに書かない.ヘッダに書くってことはそのヘッダをインクルードしたソース(Cのインクルードは基本的にコピー)全てに,ソース固有のstatic変数が生成される.
  • ヘッダの中で不要にヘッダファイルをインクルードしない.相互依存が発生してしまうし,そのヘッダをインクルードしているソース全部が再コンパイルされてしまう.ラベルが欲しいだけなら前方宣言を利用する.

前方宣言

  • クラス定義をしていると,他のクラスを変数として持ちたいことが(当然だけど)ある.その場合にそのクラスのヘッダファイルをインクルードしないといけなくなって,すぐにヘッダの依存関係が混雑してしまう.
  • そんな時に利用するのが,その変数をポインタとして持つ方法.ポインタであればメソッドやメンバ変数などの情報(というかコンパイル時のメモリ割当)が不要(ポインタ64ビットか32ビットあれば良い)だから,ラベルさえあれば良い.
// シンプルVer.
class Hoge; // <- 前方宣言

class Foo {
private
  Hoge *hoge; // <- ポインタで持つ
};

// 名前空間の下にいるVer.
namespace BAR {
  class Hoge;
}

class Foo {
private
  BAR::Hoge *hoge;
};

extern C {...}

  • Cの関数をC++でも使えるようにするための宣言.
  • 関数名はコンパイル時にリネームされる.しかし,その方法がCとC++で異なるため,普通にコンパイルするとリンクエラー(そんな名前の関数無いよ)になる.
  • それを避けるために,extern C {...}で囲っておく.特に,g++とかだと_cplusplusマクロが定義されているから,それでifdefする.
#ifdef _cpuluspulus
extern C {
#endif
... // Cの宣言文

#ifdef _cpuluspulus
}
#endif