EurekaMoments

ロボットや自動車の自律移動に関する知識や技術、プログラミング、ソフトウェア開発について勉強したことをメモするブログ

ソフトウェアエンジニアの技術面接で実際に出たC++質問集

目的

自分のように自律移動システムを開発するエンジニアの採用プロセスでは、
C++の知識がどれだけあるかを問われる技術面接が必ずあると思います。

今まで何度か実際に面接を受けたことがありますが、いざ聞かれて答えようと
すると(しかも英語で)、自分がC++の事を全然理解出来ていないということを
思い知らされました。

今後また同じ質問をされたときはちゃんと答えられるように、これまでに
問われた質問の内容と、その模範解答をまとめておこうと思います。

目次

質問集

C++とPythonの違い

両者を比較して、一番違いを感じるのは型宣言の有無だと思います。
自分は仕事柄、C/C++, Python, Javaを使い分けているので、この違いに
分かっていても戸惑うことがあります。

Pythonでは型宣言が必要ありません。それに対してC++では、bool, short,
intなどを型宣言を行う必要があり、これによって

  • この変数とあの変数は同じか?
  • 取れる値の範囲は?
  • サイズは1バイト? 2バイト? 4バイト?

などを気にしながら設計、実装する必要があります。

このように型宣言をするのは、計算するためのメモリ領域を明記するためであり、
そうしないとコンパイラが、どこのどの変数を使って演算するのかが分からない
からです。

また、自分の場合はいろんな事情があってあまり高い性能のCPUが使えないため、
計算は基本的に全て整数型で行う、計算時に扱うデータがとり得る値の範囲を
最低限満たす型を選ぶようにし、必要以上にメモリを使わないようにすることを
意識して実装する必要があります。

クラス/構造体/共用体の違い

クラスと構造体は、どちらも独自の型を定義するためのコンストラクトです。
どちらもデータメンバとメンバ関数を持つことができ、これをにより型の動作や
状態を表現することができます。

両者の違いを挙げるとすれば、クラスではデフォルトのアクセシビリティがprivate,
構造体ではpublicであるという点です。

また、3つ目のクラス型として共用体(union)というものもあります。
デフォルトのアクセシビリティがpublicという点では構造体と同じ
ですが、同時に使用できるメンバは一つまでです。
共用体は一つのメモリ領域に複数の変数を割り当てるようになっており、
そこで割り当てた全ての変数のアドレスは同じになるためです。

共用体のサイズはコンパイル時に決定され、メンバの中で一番大きい
型のサイズになります。例えば、このように異なるサイズのメンバを
持つ共用体がある場合、

union UNION {
    char a;
    int b;
    double c;
}

確保される共用体のサイズは、double型であるcの8バイトになります。
しかし、他のメンバであるaやbへのアクセスは、ビット数が制限され、
その型に合わされます。そのため、aにアクセスした場合は8バイトの
うちの下位8ビットまでしか参照できないということになります。

一つのメモリ領域を複数の型で共有することで、それらの型を使い分け
つつ、領域の無駄を抑えられるというメリットがありますが、間違った
型で解釈するとおかしなことになるので注意も必要です。

ポインタ渡しと参照渡しの違い

C++では、関数の呼び出しの際の引数の渡し方が下記の3つに分かれます。
* 参照渡し (Pass by Reference)

値渡し (Pass by Value)

まず値渡しは、int, float, bool, charなどといった組み込み型を使う際に
よく用いられます。値渡しをすると簡単に言えばその値がコピーされ、
その引数を変更したとしても関数の呼び出し側の変数は変更されません。

ただし、引数として渡すデータのサイズが大きなもであると、その
オブジェクトを作成するまでの処理時間が長くなってしまうため、
サイズの大きなデータを渡す際には、値渡しは推奨されません。

ポインタ渡し (Pass by Pointer)

ポインタ渡しは、変数のメモリ上のアドレスを渡すやり方です。
渡されたアドレスを間接参照することで、関数の呼び出し元の
変数を書き換えることができます。

その際は、引数にNULLが渡されてプログラムが正常に動作しなくなる
ことを防ぐために、必ずnullチェックによる例外処理を入れた方が良いです。

参照渡し (Pass by Reference)

参照渡しはC++で追加されたやり方であり、より安全で制約の厳しい
ポインタであると言えます。また、ポインタ渡しと同様に、呼び出し元の
変数を書き換えることができます。

ポインタとの違いとしては、NULLのような無効値を表す記法が存在しない
ことが挙げられます。そのため、呼び出される関数側ではその参照が有効な
ものであることを前提に実装でき、呼び出す側では無効な参照を渡さない
ことを前提に実装することが要求されるようになります。

constの使い方

関数内の処理が実行される前に、与えられた入力引数の値が書き換えられて
しまうと、当然ながら間違った値が出力されてしまいます。こういった
間違った変更を防ぐ手段としてconst修飾子が使われます。
C++では、安全のために積極的にconstを用いるべきです。

メモリの扱い方

C++では、下記のような命令でメモリの確保と解放を行うことができます。

  • new: メモリを確保する命令
  • delete: newで確保した領域を解放する命令
  • delete[]: new で確保した配列を解放する命令

メモリを確保できない場合は、例外処理としてstd::bad_allocを投げます。
std::nothrowを指定すると、例外ではなくnullptrを返します。

ちなみにC言語では、下記のような関数でメモリの確保と解放を行います。

  • malloc: 指定されたサイズのメモリを確保する関数
  • calloc: 指定されたサイズのメモリブロックを確保し、その領域を0クリアする関数
  • realloc: 確保済みのメモリを拡張する関数
  • free: 上記3つの関数で確保したメモリを解放する関数

このとき、上記の関数でメモリを確保できない場合はNULLが返されます。

reallocの注意点

reallocは動作が下記のように複雑なので、使う際には注意しないといけません。

新しいアドレス = realloc(既存アドレス, 確保するメモリサイズ)

  1. 既存アドレスがNULLか判定する
    NULLなら、mallocと同じ動作になります。

  2. 確保したいメモリ量が既存メモリより同じ/小さい/大きいか判定する
    同じなら何もしないで返します。
    小さいなら、アドレスのサイズ情報を書き換えて既存のポインタを返します。

  3. 既存の領域の後ろに拡張できるかを確認する
    拡張可能なら、アドレスのサイズ情報を書き換えて既存のポインタを返します。
    拡張不可能かつメモリ不足なら、NULLを返し、既存のアドレスには何もしません。
    拡張不可能なら、別領域にメモリを確保し、既存のアドレスの内容を
    新しいアドレスにコピーした後、既存のアドレスを解放して
    新しいアドレスを返します。

そのため、以下のようなコードを書いてしまうとメモリリークが起きてしまいます。

    char* p = malloc(100);

    // mallocで確保している既存領域より大きいメモリを確保しようとしている
    // メモリ不足のため、reallocはNULLを返す
    // ここでNULLがpに入ると、mallocで確保した領域を解放できなくなってしまう
    p = realloc(p, 200);

C++における4大メモリ

C++では下記の4種類のメモリを扱います。

  • プログラム用メモリ
  • 静的変数用メモリ
  • スタック用メモリ
  • ヒープ用メモリ

C++で開発したプログラムを起動すると、下記のプロセスが生成されます。

  1. プログラムを起動
  2. OSがプログラムが必要とするメモリを獲得
  3. 内部ストレージから獲得したメモリへプログラムを読み込む
  4. プログラムに含まれているスタートアップ・ルーチンが呼ばれる
  5. 静的変数用メモリとスタック用メモリが初期化される
  6. main()関数が呼ばれる
  7. プログラムからの要求によりヒープ用メモリが獲得/解放される
  8. main()関数から戻ると必要な後始末を行う
  9. main()関数からの戻り値をOSへ渡してプログラムを終了する

プログラム用メモリ

機能を実現するためのプログラムそのものを格納するメモリであり、
ROM(Read Only Memory)となっています。

静的変数用メモリ

static記憶領域とも呼びます。このメモリを使うことで、プログラム
実行中有効な変数やプログラム全体や一部で共有する変数を実現できます。

ローカル変数にstaticを付けると、そのローカル変数の寿命が
「プログラムの開始から終了まで」に伸びます。
対してグルーバル変数の場合は、staticを付けても寿命は変わりません。
その代わり、アクセスできるのがそのソースコードからのみとなります。

上記のような変数はコンパイル時にメモリ割り当てが確定し、
実行中はそのメモリ割り当てが変化しません。そのことから
「静的変数」と呼ばれます。
そして、これらはプログラムの起動時に実メモリである
staticな記憶領域に割り当てられます。

スタック用メモリ

ある関数が呼び出されたとして、その関数が終了したら呼び出し元へ戻ります。
こういった処理は、どこかに呼び出し元を記録しておき、戻るときはその戻り先を
取り出すことで実現されます。この戻り先を記録するメモリが「スタック」です。

関数の戻り先を関数を呼び出す度に山の上へ次々と積んでいき、関数から
戻るときに山の上から取り出すようになっています。

ヒープ用メモリ

メモリを獲得するためにはnew演算子を使います。型を指定することで
その型を記録できるメモリを割り当て、その先頭アドレスを返します。
そして使い終わったあとは、deleteを使って解放します。

int* a = new int;

// aを使った処理

delete a;

C++のnewはメモリを獲得するだけでなく、そのメモリ上に
「オブジェクト」と呼ばれるデータ構造の構築処理を行う
ことができます。これはコンストラクタと呼ばれます。
またdeleteはメモリを解放する前にその「オブジェクト」の
解体処理をすることができます。これはデストラクタと
呼ばれます。

newで獲得されるメモリは、元々はある場所にストックされており、
解放されたときにはその場所へ再び戻されます。その場所が
「ヒープ」です。

ヒープはスタックと同様に山積みの意味ですが、スタックと
比べて大量で乱雑なニュアンスを含みます。
スタックは下から順に獲得し上から順に解放するため、隙間なく
使われます。それに対してヒープは、解放される領域がヒープの
最下位部分とは限らないため、ヒープ領域には隙間ができます。

スタックとヒープの違い

スタックもヒープもプログラム実行中に領域のサイズが変わります。
どちらも動的メモリですが、使い方が全く違います。

スタックは下から順に使っていき、解放するときは上からと決まっています。
ヒープはプログラムから要求される度にメモリを使用中とマークします。
そして、解放される度にマークを外し、使用可能領域として記録します。
このときの解放順序はプログラムの自由です。

再帰関数とスタックオーバーフロー

再帰関数とは、関数内で自分自身を呼び出す関数のことです。
例えばこのように階乗を計算する関数を実装できます。
再帰関数内の処理は、自身を呼び出さないケースと、自身を
呼び出さないケースの2つに分かれます。

int factorial(int n) {
  if (n < 2) {
    return 1; // 自身を呼び出さないケース
  }
  return n * factorial(n - 1); // 自身を呼び出すケース
};

例えばfactorial(3)を呼び出すと、そのケースがスタックに
入ります。その後facotorial(3)を処理すると戻り値は
factorial(2)で計算結果がまだ取得できないので、
factorial(2)がスタックに積まれます。その後も同様に
facotorial(1)が戻り値に含まれるので、factorial(1)が
スタックに積まれます。

そして一番上に積まれたfactorial(1)から順番に解決されて
いくので、最後にfactorial(3)が解決されてスタックは空になります。

これに関連して、再帰関数について回るのがスタックオーバーフローです。
スタックオーバーフローとは、スタック領域に処理が積み上がり過ぎて、
メモリが足りなくなり、プログラムが異常終了してしまうことです。
再帰関数は深ければ深くなるほどスタックが積み上がり、最終的に
スタックオーバーフローを引き起こすので注意が必要です。

フィボナッチ数列のように漸化式で表せる処理や、
木構造のデータの各要素に何らかの変更を加える処理は、
再帰関数が有効です。

このときに注意しなければいけないのが計算量です。
再帰関数はシンプルに処理を書けますが、通常のループに
比べて計算量が増加しがちです。
上記で例にあげたフィボナッチ数列を再帰関数で実装
すると、一つの数値を出力するのに内部で自身を2回
呼ばないといけないので、計算量はO(2n)になります。
つまり、入力が増えると指数関数的に計算量が増加
してしまうことになります。

メモリリークとは

確保したメモリを不要になっても解法せずにいることをメモリリークと
いいます。その結果、必要なメモリを確保できなくなるという問題が
起こります。
C/C++では自前でメモリを管理する必要があるため、こういった
問題が多く起きます。これに対してJavaやC#などは言語レベルで
この問題を解消しているため、メモリリークが起きることはありません。

テンプレートとは

例えば、下記のような関数が定義されたとします。

void swap(double& a, double& b)
{
    double tmp = a;
    a = b;
    b = a;
}

こういった関数は宣言時に予め決められた型以外のデータ型を
扱うことはできません。そこで、下記のような型パラメータを
持たせることで、任意のデータ型を扱えるようになります。

template <class T>
void swap(T& a, T& b)
{
    T tmp = a;
    a = b;
    b = tmp;
}

int main()
{
    int m = 2, n = 3;
    swap(m, n); // swap(int&a, int& b)として処理される
}

このようなパラメータTを持つ関数やクラスを、テンプレートと呼びます。
このパラメータは複数持たせることも可能で、

template <class T, class U>

のように書くことができます。

値パラメータ

テンプレートには、型パラメータ以外にも、値パラメータを持たせる
ことができます。
例えば下記のようなコードを書くことで、任意のデータ型の要素を
持つ配列を初期化することができます。

template <class T, int N>
void init(T (&arr)[N])
{
    for (int i = 0; i < N; ++i)
        arr[i] = T();
}

int main()
{
    int arr[256];
    init(arr);   // init(int (&arr)[256])として処理される
}

クラステンプレート

下記のようなコードを書くことで、クラスが持つメンバ変数や関数の
データ型を任意に決めることができます。これをクラステンプレート
といいます。

template <class T>
class Stack
{
private:
    T* stack;
    int index;
public:
    Stack(int size) : index(0) { stack = new T[size]; }
    ~Stack() { delete [] stack; }
    void push(T item) { stack[index++] = item; }
    T pop() { return stack[--index]; }
};

int main()
{
    Stack<int> stack(256);
    stack.push(123);
    stack.pop();
}

このクラステンプレートについては、型の指定を
省略することはできないので注意しましょう。

仮想関数とは

継承と仮想関数を使うことで、既存クラスの振る舞いを変更した
新しいクラスを定義することができます。

例えば、下記のような時計クラスがあるとします。
このクラスはTick()関数を呼び出す度に時刻を進め、
60回目でピーピーと音を鳴らすというものです。

class Clock
{
protected:
    SIntN time; 

public:
    Clock() 
    {
        time = 0;   
    }

    SIntN GetTime()
    {
        return time;
    }

    Void Tick()
    {
        ++time;
        if (time == 60) 
            Action();
    }

    virtual Void Action()
    {
        // 音を鳴らす処理
    }
};

コードを見るとわかるように、音を鳴らす処理はAction()関数により実現されます。
この関数にはvirtualというキーワードが付いており、これが仮想関数です。

オーバーライド

仮想関数には、派生クラスの中で再定義できるという利点があります。
例えばこのように、Clockクラスを継承したLaughClockクラスを定義したとすると、
元のAction()関数の中の処理を再定義することができます。

class LaughClock : public Clock
{
public:
    virtual Void Action()
    {
        // 時計がケタケタ笑う処理
    }
};

このように、基底クラスの仮想関数を派生クラスの方で再定義することを
オーバーライドと呼びます。

呼び出し

仮想関数は通常のメンバ関数と同じように呼び出します。
ただし、オブジェクトの実際のクラスが何であるかにより、
呼び出される関数も異なるので注意が必要しないといけません。

Clock clock;
clock.Action(); // Clock::Action()が呼び出される

LaughClock laubhClock;
lauchClock.Action(); // LaubhClock::Action()が呼び出される

// 見かけのクラスはClockだが、実際のクラスはLaughClock
// そのため、LaughClock::Action()が呼び出される
Clock* clock2 = new LaughClock();
clock2->Action();

純粋仮想関数

純粋仮想関数は、実装がなく、プロトタイプが宣言されているだけの関数です。
純粋仮想関数があるクラスは、そのままインスタンス化できず、そのクラスを
継承し、純粋仮想関数をオーバーライドして実装する必要があります。
このようなクラスを抽象クラスと呼びます。

宣言方法はこちらのように、プロトタイプ宣言に = 0をつけるようにします。

#include <iostream>
using namespace std;
 
class A {
    public:
        virtual void hoge() = 0; // 純粋仮想関数
};

2つのベクトルの内積の求め方

ベクトルの内積とは、こちらの記事にて解説されているように、
2つのベクトルの成す角を求める際に利用されるものです。
rikeilabo.com

自動運転における活用例としては、こちらの論文にて述べられて
いるように、LiDARで物体をスキャンして得られた3次元点群
から、エッジ部分や平面部分を抽出するというものがあります。

各点における法線ベクトルの成す角やその分散を特徴量として、
エッジ部分や、平面とは異なる不均一な形状であるものほど、
その特徴量の値が大きくなるということを利用しています。

そしてこの内積をC++で計算するにはこちらの関数を使います。
cpprefjp.github.io

2次元配列のメモリを動的に確保する方法

まず思いつく方法はnewを使うことだと思います。
newを使って配列の動的メモリを確保できるのは1次元配列まで
なので2次元配列の場合は、まず行方向の一次元配列として確保し、
その後各行の列方向の一元配列として確保するようにします。

ここで注意しないといけないのは、newで確保したメモリは必ず
最後にdeleteで解放する必要があることです。この時も、
まずは各行における列方向の1次元ベクトルのメモリをdeleteし、
最後に行方向のベクトルのdeleteするようにします。

deleteを忘れるとメモリリークを起こしてしまうので、
あまりこの方法はおススメされません。

2つ目の方法は、STDライブラリのvectorを使って確保することです。
例えば、vector<vector> arrayのように宣言し、その後
resize()関数で確保するサイズを決定します。この方法の場合、
deleteによるメモリ解放の処理はデストラクタ内で自動で行って
くれるので、メモリリークの危険性を減らすことができます。

最後に3つ目の方法として、以下の記事のように2次元配列を
1次元配列として表現するというものがあります。例えば、
高さをH, 幅をWとする2次元配列を確保する場合、それを
1次元配列で表現したものはarray[W*H]となります。

qiita.com

この場合、一つ目の方法よりもシンプルなコードでnewによる
メモリ確保ができるようになります。ただし、最後にdeleteに
よるメモリの解放が必要になることも同様なので、忘れて
はいけません。

emplace_back/emplaceとは

まず、emplace_back関数とは、要素型のクラスが取り得る
コンストラクタ引数の値を元に、要素を直接コンテナ内で
構築して追加する関数です。

ここで言う「要素型のクラスが取り得るコンストラクタ引数の
値」とは、std::vector<std::string>コンテナクラスの要素型で
あるstd::stringのコンストラクタが取り得るchar*などのことを
指します。

emplace系の特徴

emplace系の関数は、要素をコンテナ内部で生成します。
そのため、例えばemplace_back関数が受け取るのは、
要素自体ではなく、その要素型のコンストラクタが引数
として取り得る値となります。

これにより、オブジェクトや一時オブジェクトの余計な
生成やコピー、ムーブ、破棄といった処理を省けるように
なります。

push_backとの違い