👋

CPP メモ

2025/04/23に公開

C++

42 Tokyo

tech

Bjarne Stroustrupの発音をマスターしよう

CPPの課題を始める前に、まずC++の開発者教祖Bjarne Stroustrup様の名前を正しく発音できるようにしましょう。
まず、こちらの音声を聞いて、リピートアフタミー、さんハイっ！
ビョーンスッポスッポ
正しく発音できるまで毎日10回唱えましょう。

発音のコツはこちらにあります。

The best suggestion I have heard yet was "start by saying it a few times in Norwegian, then stuff a potato down your throat and do it again :-)"
私が今まで聞いた中で最も良いアドバイスは、「まずノルウェー語で何度か言って、それから喉にジャガイモを詰め込んで、もう一度言ってみてください :-)」というものでした。

CPP09

ex02

自作intクラスの比較演算子をオーバーロードして比較回数をカウント

こんな感じで比較演算子をオーバーロードして、比較回数を数えられるようにしておくと理論値と比較しやすくなります。またアルゴリズムの実装で誤って==などの比較を使用していないことを証明できるようになります。

UInteger.hpp

#ifndef __U_INTEGER_HPP__
#define __U_INTEGER_HPP__

#include <iostream>

class UInteger {
 private:
  unsigned int value_;
　// クラスのstaticメンバに比較回数を持たせると、他のインスタンスと値を共有できます
  static unsigned long comparison_num_;

 public:
  explicit UInteger(const char* str);
  ~UInteger();
  UInteger(const UInteger& other);
  UInteger& operator=(const UInteger& other);

  // 比較演算子をオーバーロード
  bool operator<(const UInteger& other) const;
  bool operator>(const UInteger& other) const;
  bool operator<=(const UInteger& other) const;
  bool operator>=(const UInteger& other) const;
  bool operator==(const UInteger& other) const;
  bool operator!=(const UInteger& other) const;

  int value() const;

  static unsigned long getComparisonNum();
  static void initComparisonNum();
};

std::ostream& operator<<(std::ostream& os, UInteger& ui);

#endif  // __U_INTEGER_HPP__

UInteger.cpp

unsigned long UInteger::comparison_num_ = 0;

UInteger::UInteger(const char* str) {
  // コンストラクタで文字列から数値に変換して、
  // 不正な文字列の時は例外を投げるようにしておくと
  // c++っぽいバリデーションチェックの書き方ができます。
}

bool UInteger::operator<(const UInteger& other) const {
  comparison_num_++; // 比較回数をカウント
  return value_ < other.value_;
}
// 他の比較演算子も同様のため省略

// 比較回数をソート前に初期化
void UInteger::initComparisonNum() {
  comparison_num_ = 0;
}

比較回数の理論値

比較回数の理論値は下記の式^[1]で計算できます。
1〜100個の要素のランダムな順列で1000回ぐらい試行して、全て理論値以下になっているか確認してみて下さい。

F(n) = \sum_{k=1}^{n}\lg\lceil\dfrac{3}{4}k\rceil

static unsigned long theoreticalNumF(int n) {
  if (n <= 0) {
    return 0;
  }
  unsigned long fn = static_cast<unsigned long>(ceil(log2(3.0 / 4.0 * n)));
  return fn + theoreticalNumF(n - 1);
}

二分探索

std::lower_boundを使ってもいいのですが、一回ぐらいは自分で二分探索を書いてみるのも面白いと思います。しかし、二分探索はアイデア自体は単純ですが、昔から頭のいい人でもバグらせやすいことで有名です。
はじめて二分探索を書く人はめぐる式二分探索が簡単でオススメです。

脚注

Donald E. Knuth, The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版, KADOKAWA(2015)(ISBN/JAN: 9784048694315), p.177 ↩︎