先頭へ戻る

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

Programming Place Plus トップページ新C++編

先頭へ戻る

このページの概要

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

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



要素を追加する

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

しかし、要素の追加と削除は意外と難しい面もあります。たとえば、{0, 1, 2} という 3つの要素をもった std::vector があるとして、12 のあいだに 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> にあります)1。こちらを使うと、クラスではない通常の配列からでも要素数を取得できます。

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

empty関数

要素がない(空である)かどうかを調べたい場合、v.size() == 0 としてもいいですが、empty関数を使う方法もあります。

empty(v) のように使い、v が空であれば true、空でなければ false になります。

#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

【上級】【C++17】非メンバ関数の std::empty関数が追加されました(<iterator> にあります)4。これはクラスでない通常の配列にも使えます(必ず false です)。

メモリの再割り当て

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

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

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

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

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

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

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

2番のところで要素がコピーされ、3番で元のメモリが解放されるということは、既存の要素はメモリ上の別のところへ移動するということです。ある要素を指し示していたイテレータは、その要素を指し示さなくなることに注意しなければいけません。移動先まで追いかけてはくれません。これは、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を使うことで、メモリを強制的に確保させることができ、要素追加時にメモリの再割り当てが発生することを避けられます。処理速度が重要であるのなら検討すべきです。

容量を取得する

現在の容量は、capacity関数を使って取得できます。

#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

std::vector や std::string の容量がどのように変化するかは、仕様では決められておらず、標準ライブラリの実装次第ということになっています。上の実行結果は Visual Studio 2015 で試したものです。

要素を末尾に追加する

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

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

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

push_back関数

配列の末尾に要素を追加する方法として、push_back関数があります。v.push_back(10); のように記述し、すでに存在する要素の末尾に、() の内側に記述した値を持った新たな要素を追加します。

push_back関数は std::vector、std::string ともに使用できますが、1度に追加できる要素は1つだけです。std::string では数文字の文字列を追加したいケースが多いでしょうから、あとで紹介する append関数のほうが便利かもしれません。あるいは、これまたあとで紹介しますが、insert関数を使っても、複数の要素をまとめて追加できます。

#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

append関数、+演算子、+=演算子

std::string の場合は、数文字の文字列をまとめて追加できると便利です。そこで、append関数を使います。

append関数の使い方のパターンは多種多様なので、全般的なことはリファレンスサイト(cpprefjpcppreference.com)で確認してください。

#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関数を使います。ただし、使い方は異なっているため、それぞれ説明します。

std::vector の場合

insert関数には、「追加する位置」と「追加する要素の値」という2つの情報を指定します。位置はイテレータを使って表現し、イテレータが指し示している要素の手前側に挿入します。

insert関数の使い方のパターンは多種多様なので、全般的なことはリファレンスサイト(cpprefjpcppreference.com)で確認してください。

#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

変数it は、std::cbegin関数(std::begin関数でも可)の結果で初期化したあと、++ で1つ先に進めているので、v[1] の要素を指し示しています。この位置を挿入位置として指定しているので、0 と 1 のあいだに 999 が挿入されます。なお、1行で v.insert(std::begin(v) + 1, 999); と書くこともできます。

std::string の場合

std::string では、文字でも文字列でも挿入できます。しかしどういうわけか、挿入位置を指定する方法が、文字列を追加する場合には添字、文字を追加する場合にはイテレータでなければなりません。

insert関数の使い方のパターンは多種多様なので、全般的なことはリファレンスサイト(cpprefjpcppreference.com)で確認してください。

#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

複数の要素を挿入する

insert関数では、追加する要素を { } を使って書き並べることで、複数の要素をまとめて追加できます。

#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

逆イテレータを使う場合

insert関数に指定する位置情報は、通常のイテレータ(か constイテレータ)でなければならず、逆イテレータは使えません。

逆イテレータを使いたい場合は、base関数を使って、イテレータに変換します。base関数は、逆イテレータをイテレータに変換しますが、指し示す要素が1つ末尾側へずれることに注意してください。

#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


まとめ


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


参考リンク


練習問題

問題の難易度について。

★は、すべての方が取り組める入門レベルの問題です。
★★は、自力でプログラミングができるようなるために、入門者の方であっても取り組んでほしい問題です。
★★★は、本格的にプログラマーを目指す人のための問題です。

問題1 (確認★)

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

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

解答・解説

問題2 (確認★)

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

#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";
    }
}

解答・解説

問題3 (基本★★)

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

解答・解説

問題4 (基本★★)

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

解答・解説

問題5 (調査★★★)

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

解答・解説

問題6 (調査★★★)

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

解答・解説


解答・解説ページの先頭



更新履歴




はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー