要素を追加する | Programming Place Plus　新C++編

このページの概要

このページでは、std::vector や std::string に対して、あとから新たな要素を追加する方法を取り上げます。要素を追加するコードそのものは非常に簡単ですが、具体的にはどのようなことが起きているのかきちんと理解しておかなければ、バグを生んだり、実行効率を大きく低下させたりする可能性があり、意外と大きなテーマになる話題です。

以下は目次です。要点だけをさっと確認したい方は、「まとめ」をご覧ください。

• 要素を追加する
• 要素数（サイズ、長さ）
  • empty関数
• メモリの再割り当て
  • 容量を取得する
• 要素を末尾に追加する
  • push_back関数
  • append関数、+演算子、+=演算子
• 要素を任意の位置に追加する
  • std::vector の場合
  • std::string の場合
  • 複数の要素を挿入する
  • 逆イテレータを使う場合
• まとめ
• 練習問題
• 参考リンク
• 更新履歴

要素を追加する

std::vector（や std::string）は要素を後から追加したり、要素を削除したりする機能をもっています。要素の追加と削除を自由にできることは非常に便利であり、現在の目標である蔵書リストのような、データの登録と削除が必要なプログラムを作るうえで重要な機能です。

しかし、要素の追加と削除は意外と難しい面もあります。たとえば、{0, 1, 2} という 3つの要素をもった std::vector があるとして、1 と 2 のあいだに 10 という要素を追加したとします。その結果、std::vector の内容は {0, 1, 10, 2} となりますが、ここでいくつか気になることがあります。

1. std::vector の要素数を 3 だと思って書いていたコードは、要素数の判断を誤るのではないか？
2. 追加前と追加後で、v[2]（v.at(2)）がアクセスする要素は異なるものになるのではないか？
3. 追加前、2 という要素を指していたイテレータは、追加後にも同じ要素を指しているのか？

プログラムで書くとこういうことです。

#include <iostream>
#include <vector>

int main()
{
    constexpr auto element_count = 3;  // 要素数
    std::vector<int> v {0, 1, 2};

    auto it = std::begin(v) + 2;  // v[2] を指すイテレータ

    // v[2] の値を出力
    std::cout << v.at(2) << "\n";
    std::cout << *it << "\n";

    //
    // ここで、v に要素を追加したとする。
    //

    // v[2] の値を出力（追加前と同じ要素をアクセスできる？）
    std::cout << v.at(2) << "\n";
    std::cout << *it << "\n";

    for (int i = 0; i < element_count; ++i) {  // element_count が 3 のままだが・・・？
        std::cout << v.at(i) << "\n";
    }
}

いずれの懸念点についても、「気にしなくても大丈夫」とはいきません。

要素数（サイズ、長さ）

まず、要素数の話から始めます。

要素数（あるいはサイズ）とは、配列に実際に存在している要素の個数のことです。std::vector<int> v(5); なら 5 ですし、std::vector<int> v {0, 1, 2}; なら 3 です。std::string の場合は 長さ (length) と呼ぶこともありますが、「文字という要素が入った配列」に過ぎないので、要素数といっても問題ありません。

要素数が変化しないことが分かっている場合、要素数を constexpr変数で管理できますが、要素の追加や削除が起こると不整合を起こしてしまいます。

// よくない。v の要素数が変わると、element_count の値が正しくなくなる
constexpr auto element_count = 3;
std::vector<int> v {0, 1, 2};

// こちらの使い方ではマジックナンバーを避ける意味はあるが、
// 要素の追加・削除を行うなら要注意。最初の要素数という意味でしかない。
std::vector<int> v (element_count);

そこで、要素数が必要なときには、size関数を使って、std::vector や std::string の変数に問い合わせるようにします。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};
    std::cout << "size = " << v.size() << "\n";

    for (int i = 0; i < v.size(); ++i) {
        std::cout << v[i] << "\n";
    }
}

実行結果：

size = 3
0
1
2

もちろん、このプログラムのような for文であれば、範囲for文を使ったほうが簡単ですし、添字が登場しない方が安全でもあります。

このプログラムをコンパイルすると、「signed と unsigned の数値を比較している」という趣旨の警告が出るかもしれません。問題の箇所は i < v.size() のところで、i が int型であるのに対して、v.size() で得られる整数は、実は int ではない別の型であるためです。型が一致しない比較に対して警告を発しているというわけです。警告を安易に無視してはいけませんが、事実上問題はないので、ここでは無視しておきます。この問題の解決は、いずれ別のページで行います。

【上級】【C++17】非メンバ関数の std::size関数が追加されました（<iterator> にあります）¹。こちらを使うと、クラスではない通常の配列からでも要素数を取得できます。

std::string の場合は、「長さ」という表現が自然に思えるので、length関数でも、size関数と同じ結果を得られるようになっています。

#include <iostream>
#include <string>

int main()
{
    std::string s {"Hello"};
    std::cout << s.size() << "\n";
    std::cout << s.length() << "\n";
}

実行結果：

5
5

「イテレータ」のページで、auto s = "Hello"; のように auto を使った場合、std::string には型推論されないという話をしました。std::string ではないため、s.size() とか s.length() はコンパイルエラーになります。

【上級】【C++20】size関数や length関数は constexpr関数になり、定数式の文脈の中でも要素数を取得できるようになりました。^{2 3}

#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<int> v {};
    std::vector<int> v2 {0, 1, 2};
    std::string s {""};
    std::string s2 {"Hello"};

    std::cout << std::boolalpha
              << v.empty() << "\n"
              << v2.empty() << "\n"
              << s.empty() << "\n"
              << s2.empty() << "\n"
              ;
}

true
false
true
false

メモリの再割り当て

変数の値はメモリ（メインメモリ）に記憶されています。int型の値を記憶しておくためには、int型の値が収まる大きさのメモリを確保 (allocation) しておかなければなりません。メモリの確保は、プログラムの実行中、変数を宣言している箇所を通過するときに自動的に行われています。また、使わなくなったメモリは、ほかの用途で使えるように、確保状態が解除されます。

こういった事情は std::vector や std::string でも同様ですが、これらは配列であるため、すべての要素の値を記憶できるだけのメモリを確保しなければなりません。また、配列は、要素が連続的に並ぶ構造であることから、メモリ上でも連続的になっていなければなりません。ここで、std::vector や std::string が確保しているメモリが、要素何個分であるかをあらわす数を、容量 (capacity) と呼びます。

要素数と容量はイコールではなく、多くの場合、要素数よりも容量のほうが大きいです。これから説明するように、「要素数＝容量」というシンプルな関係性では、非効率になるからです。

std::vector や std::string に要素を追加しようとしたときに、容量が不足する場合（つまり、追加前の要素数と容量が同じ場合）、自動的に新たなメモリが確保されます。このとき、元々確保してあったメモリの後ろに付け足すようなかたちで確保できれば、要素の連続性が維持できますが、その場所はすでにほかの変数などに取られているかもしれず、可能である保証がありません。そのため、既存の要素と、追加する要素のすべてを記憶できるだけの広いメモリをあらためて確保しなおすことがあります。この場合の動作はこうです。

1. 既存の要素と追加された要素のすべてを記憶できる広いメモリを新たに確保する
2. 既存の要素の内容を、１番で確保したメモリへコピーする
3. 既存の要素を記憶していたメモリを解放する

この一連の動作を、メモリの再割り当て (reallocation) といいます。

３番の「メモリを解放 (deallocation) する」というのは、確保されていたメモリを、もう使わないとして、確保前の状態に戻すことです。

２番のところで要素がコピーされ、３番で元のメモリが解放されるということは、既存の要素はメモリ上の別のところへ移動するということです。ある要素を指し示していたイテレータは、その要素を指し示さなくなることに注意しなければいけません。移動先まで追いかけてはくれません。これは、past-the-end イテレータ（「イテレータ」のページを参照）についても同様です。

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

auto it = std::begin(v);      // 先頭の要素を指し示すイテレータ

// 要素を追加する。
// メモリの再割り当てが起こる可能性があり、
// 既存の要素 {0,1,2} は、メモリ上でまったく別の場所に移動されるかもしれない。

std::cout << *it << "\n";     // it が何を指しているかわからないので危険

このように、すでにあるイテレータが、要素の移動によって使えなくなることを、「イテレータが無効になる」と表現します。無効になったイテレータをデリファレンスすることは未定義動作です。

【上級】イテレータだけを取り上げましたが、要素を指していた参照やポインタについても同様に無効になります。

メモリの再割り当てには多くの処理時間がかかります。そこで、std::vector や std::string は、できるだけメモリの再割り当てが起こらないように、実際の要素数よりも多めのメモリを確保するという動作を取ることがあります。これは初期化のときも同様です。そのため前述したように、要素数と容量はイコールではなく、多くの場合、容量のほうが大きいです。

【上級】ピーク時に必要になる要素数が分かっているのであれば、reserve関数^{5 6}を使うことで、メモリを強制的に確保させることができ、要素追加時にメモリの再割り当てが発生することを避けられます。処理速度が重要であるのなら検討すべきです。

#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<int> v1 {};
    std::cout << "size: " << v1.size() << "   capacity: " << v1.capacity() << "\n";

    std::vector<int> v2(1000);
    std::cout << "size: " << v2.size() << "   capacity: " << v2.capacity() << "\n";


    std::string s1 {};
    std::cout << "length: " << s1.length() << "   capacity: " << s1.capacity() << "\n";

    std::string s2 {"Hello"};
    std::cout << "length: " << s2.length() << "   capacity: " << s2.capacity() << "\n";
}

size: 0   capacity: 0
size: 1000   capacity: 1000
length: 0   capacity: 15
length: 5   capacity: 15

要素を末尾に追加する

では、実際に要素の追加を試してみます。

まずは、配列の末尾に追加する方法から取り上げます。特別、追加する場所を選ぶ理由がなければ、末尾に追加すると効率的であり、便利でもあります。なぜなら、前述したとおり、配列の要素はメモリ上で連続的に並んでいなければならず、要素を割り込ませるためには、その位置よりも後ろにあるすべての要素を、後続にずらしていく処理が必要になるためです。この処理には時間がかかるため効率が悪いですし、要素がずらされることによって、イテレータが無効になったり、添字がずれたりして、危険あるいは不便でもあります。

要素を末尾に追加した場合、メモリの再割り当てが起きたかどうかにかかわらず、要素の添字には変化がありません。つまり、追加前に v.at(i) でアクセスできた要素には、追加後も v.at(i) でアクセスできます。イテレータについては、メモリの再割り当てが起きると無効になります。

#include <iostream>
#include <vector>

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

    std::cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    std::cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";

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

size = 3, capacity = 3
size = 6, capacity = 6
0
1
2
3
4
5

#include <iostream>
#include <string>

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

    std::cout << "length = " << s.length() << ", capacity = " << s.capacity() << "\n";
    s.append(", World.");
    std::cout << "length = " << s.length() << ", capacity = " << s.capacity() << "\n";

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

length = 5, capacity = 15
length = 13, capacity = 15
Hello, World.

#include <iostream>
#include <string>

int main()
{
    std::string s {"Hello"};
    std::string s2 {};

    s2 = s + ", World";
    std::cout << s2 << "\n";

    s2 += '.';
    std::cout << s2 << "\n";
}

Hello, World
Hello, World.

要素を任意の位置に追加する

今度は、要素を好きなところに追加（挿入）する方法を取り上げます。好きなところなので末尾も含まれますが、末尾だと分かっているのなら、push_back関数や append関数などを使えばいいです。

前述したとおり、配列においては、末尾以外の場所に要素を追加するという行為は、基本的に非効率です。また、挿入によってずらされた要素については、添字がずれるほか、それらの要素を指し示していたイテレータは無効になります。

std::vector や std::string で、任意の位置に要素を追加するには insert関数を使います。ただし、使い方は異なっているため、それぞれ説明します。

#include <iostream>
#include <vector>

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

    auto it = std::cbegin(v);  // 0 を指すイテレータ
    ++it;                      // 1 を指すようになる
    v.insert(it, 999);         // 1 の手前に 999 を挿入

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

0
999
1
2

#include <iostream>
#include <string>

int main()
{
    std::string s {"abcde"};

    s.insert(0, "xxx");             // s.insert(std::cebgin(s), "xxx"); はエラー
    s.insert(std::cbegin(s), 'z');  // s.insert(0, 'z'); はエラー

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

zxxxabcde

#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<int> v {0, 1, 2};
    v.insert(std::cbegin(v), {10, 20, 30});
    for (auto e : v) {
        std::cout << e << "\n";
    }

    std::string s {"abcde"};
    s.insert(std::cbegin(s), {'x', 'y', 'z'});
    std::cout << s << "\n";
}

10
20
30
0
1
2
xyzabcde

#include <iostream>
#include <iterator>
#include <vector>

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

    auto it = std::crbegin(v);  // 2 を指す逆イテレータ
    ++it;                       // 1 を指すようになる
    v.insert(it.base(), 999);   // base() は 2 を指すイテレータを作るため、2 の手前に 999 を挿入

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

0
1
999
2

まとめ

• std::vector や std::string の要素数を size関数で取得できる。std::string では length関数でも同じ値が得られる
  • 要素がないかどうかは、empty関数でも調べられる
• std::vector や std::string は、要素の値を記憶するためにメモリを自動的に確保しており、それが何要素分あるかを容量と呼ぶ
  • 容量は capacity関数で取得できる
• std::vector や std::string は、要素を追加しようしたとき、容量が不足するようならば、メモリの再割り当てをおこなう
  • このとき、新しいメモリ領域の確保、既存の要素のコピー、古いメモリ領域の解放が起こり、イテレータが無効になる
• push_back関数を使って、std::vector や std::string の末尾に１つの要素を追加できる
• append関数か、+ や += の演算子を使って、std::string の末尾に文字や文字列を追加できる
• insert関数を使って、std::vector や std::string の任意の位置に要素を追加できる
• 逆イテレータは、base関数を使って、イテレータに変換できる

新C++編の【本編】の各ページには、末尾に練習問題があります。ページ内で学んだ知識を確認する簡単な問題から、これまでに学んだ知識を組み合わせなければならない問題、あるいは更なる自力での調査や模索が必要になるような高難易度な問題をいくつか掲載しています。