要素を追加する　解答ページ | Programming Place Plus　新C++編

問題１　（確認★）

次の中から、std::vector において、ありえないことをすべて選んでください。

1. 要素数が 0 のときに、容量も 0 であること
2. 要素数が 100 のときに、容量が 1000 であること
3. 要素数が 1000 のときに、容量が 100 であること
4. 要素を追加したときに、容量が増えること
5. 要素を追加したときに、容量が増えないこと

１番はありえます。要素数が 0 なら、要素の値を記憶するためのメモリを確保する必要もありませんから、容量が 0 であることがありえます。

２番はありえます。実際の要素数よりも、容量のほうが大きいことは、むしろよくあることです（本編解説）。

３番はありえません。容量は、実際に存在している要素の値を記憶するために、何個分のメモリが確保済みであるかということなので、要素数が容量より大きいことはありえません。

４番はありえます。要素を追加しようとしたときに、容量が不足する場合には、新たなメモリが確保され、容量が増加します。

５番はありえます。要素を追加しようとしたとき、容量が十分にあれば、メモリを確保する必要はないため、容量は変化せず、要素数だけが増えることになります。

問題２　（確認★）

次のプログラムの問題点を指摘してください。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};

    auto itEnd = std::cend(v);

    v.push_back(3);
    v.push_back(4);

    for (auto it = std::cbegin(v); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
}

要素を追加する前に取得しておいたイテレータを、要素の追加後に使ってしまっていることが問題です。

要素を追加しようとしたときに、容量が不足していて、メモリの再割り当てが起きた場合、既存の要素がメモリ上で別のところへ移動させられます。結果、イテレータが指し示す先には要素がなくなっていることになります。この現象は、「イテレータが無効になる」と表現されます。無効になったイテレータは使ってはいけません（本編解説）。

要素の追加後には、イテレータはあらためて取得しなおすようにします。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};

    auto itEnd = std::cend(v);

    v.push_back(3);
    v.push_back(4);

    for (auto it = std::cbegin(v); it != std::cend(v); ++it) {
        std::cout << *it << "\n";
    }
}

実行結果：

0
1
2
3
4

問題３　（基本★★）

標準入力から整数の入力を受け取り、std::vector に格納していくプログラムを作成してください。入力は何度も繰り返し受け付け、整数とみなせない入力がなされた時点で終了するものとします。

たとえば次のようになります。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {};

    while (true) {
        std::cout << "Please enter the integer.\n";
        int value {};
        std::cin >> value;
        if (std::cin.fail()) {
            break;
        }

        v.push_back(value);
    }

    for (auto e : v) {
        std::cout << e << "\n";
    }
}

実行結果：

Please enter the integer.
7  <-- 入力された内容
Please enter the integer.
10  <-- 入力された内容
Please enter the integer.
5  <-- 入力された内容
Please enter the integer.
8  <-- 入力された内容
Please enter the integer.
exit  <-- 入力された内容
7
10
5
8

要素はいくらでも追加できる仕様なので、あらかじめ一定量の要素をもった状態で初期化するのではなく、空の状態にしておいて、push_back関数で追加していくようにしています。

問題４　（基本★★）

“Hello, World.” という文字列が入っている std::string に文字列を挿入して、“Hello, C++ World.” にするプログラムを作成してください。

要素をあいだに挿入するには、insert関数を使います（本編解説）。

文字列を追加する場合は、挿入位置を添字で指定する必要があります。指定した位置の手前に挿入されます（本編解説）。

今回、文字列の内容が分かっているので、決め打ちで指定してしまえます。

#include <iostream>
#include <string>

int main()
{
    std::string s {"Hello, World."};

    s.insert(7, "C++ ");
    std::cout << s << "\n";
}

実行結果：

Hello, C++ World.

ほかの方法として、挿入すべき位置をきちんと探してから、その場所に挿入する方法も考えられます。たとえば、'W' の位置を探して、その手前に挿入するには次のようにします。

#include <iostream>
#include <string>

int main()
{
    std::string s {"Hello, World."};

    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == 'W') {
            s.insert(i, "C++ ");
            break;
        }
    }

    std::cout << s << "\n";
}

実行結果：

Hello, C++ World.

文字列の挿入を終えたら、break文でループを抜けています。これをしないと、“C++” が挿入されることによって 'W' の位置が後ろにずらされるため、何度も繰り返し 'W' を見つけてしまい、挿入も何度も行われるため、for文を抜けられません。

問題５　（調査★★★）

std::vector に要素を追加し続けたとき（100万個程度）、容量がどのように変化するか調べてみてください。

たとえば、次のように、容量が変化したタイミングを捕まえて、そのときの要素数と容量を出力するようにしてみます。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {};

    // 初期状態の要素数と容量を出力する
    auto capacity = v.capacity();
    std::cout << "size = " << v.size() << ", capacity = " << capacity << "\n";

    for (int i = 0; i < 1000000; ++i) {
        v.push_back(i);

        // 容量に変化が起きたタイミングで、要素数と容量を出力する
        auto new_capacity = v.capacity();
        if (capacity != new_capacity) {
            std::cout << "size = " << v.size() << ", capacity = " << new_capacity << "\n";
            capacity = new_capacity;
        }
    }
}

実行結果：

size = 0, capacity = 0
size = 1, capacity = 1
size = 2, capacity = 2
size = 3, capacity = 3
size = 4, capacity = 4
size = 5, capacity = 6
size = 7, capacity = 9
size = 10, capacity = 13
size = 14, capacity = 19
size = 20, capacity = 28
size = 29, capacity = 42
size = 43, capacity = 63
size = 64, capacity = 94
size = 95, capacity = 141
size = 142, capacity = 211
size = 212, capacity = 316
size = 317, capacity = 474
size = 475, capacity = 711
size = 712, capacity = 1066
size = 1067, capacity = 1599
size = 1600, capacity = 2398
size = 2399, capacity = 3597
size = 3598, capacity = 5395
size = 5396, capacity = 8092
size = 8093, capacity = 12138
size = 12139, capacity = 18207
size = 18208, capacity = 27310
size = 27311, capacity = 40965
size = 40966, capacity = 61447
size = 61448, capacity = 92170
size = 92171, capacity = 138255
size = 138256, capacity = 207382
size = 207383, capacity = 311073
size = 311074, capacity = 466609
size = 466610, capacity = 699913
size = 699914, capacity = 1049869

この実行結果は、Visual Studio 2015 で試したものです。使っている環境によって、結果は異なります。

容量が変化したタイミングで、メモリの再割り当てが起きているわけですが、100万回の push_back に対して、35回程度に済むようになっていることがわかります。こうして極力、時間がかかるメモリの再割り当てを避けるように工夫されています。

ちなみに Visual Studio 2015 の場合、容量が不足したときに、容量を 1.5倍にしているようです（0 から 1 になるところは例外として）。

問題６　（調査★★★）

reserve関数を使うと、メモリを事前に確保させることができます。問題５と同様のことをして、挙動の変化を確認してください。

std::vector の変数を宣言した直後、v.reserve(1000000); を実行して、最初から 100万個分の容量を確保させてみます。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {};
    v.reserve(1000000);

    // 初期状態の要素数と容量を出力する
    auto capacity = v.capacity();
    std::cout << "size = " << v.size() << ", capacity = " << capacity << "\n";

    for (int i = 0; i < 1000000; ++i) {
        v.push_back(i);

        // 容量に変化が起きたタイミングで、要素数と容量を出力する
        auto new_capacity = v.capacity();
        if (capacity != new_capacity) {
            std::cout << "size = " << v.size() << ", capacity = " << new_capacity << "\n";
            capacity = new_capacity;
        }
    }
}

実行結果：

size = 0, capacity = 1000000

初期状態の要素数と容量しか出力されなくなりました。つまり、それ以降、何度 push_back関数を使っても、容量に変化は起きていないということです。したがって、メモリの再割り当てが起こることもなく、劇的に効率が良くなることが分かります。イテレータが無効にならず、添字がずれないことも利点になります。