2.12.3. 配列・ベクター・リスト#
C/C++ において複数の値を保存・管理するための方法として、配列（array）、ベクター（vector）、リスト（list）などが用意されています。これらは見た目こそ似ていますが、設計思想と得意分野が大きく異なります。
配列は、C 言語由来の低レベルなデータ構造です。配列を作成する際には、その長さ（配列に含まれる要素数）をあらかじめ指定する必要があります。また、一度作成した配列は、その後で要素数を増やしたり減らしたりすることはできません。この制約は不便に見えますが、余計な管理情報を持たないためメモリ効率が良く、アクセス速度が非常に高速という利点があります。そのため、サイズが事前に決まっており、性能が重視される場面では今でも重要な選択肢です。
ベクター（std::vector）は C++ 標準ライブラリで提供される動的配列クラスです。内部的には配列を使っていますが、要素の追加や削除、サイズの拡張といった操作を安全かつ簡単に行えるように設計されています。要素数が実行時まで分からない場合や、後からデータを追加する必要がある場合には、ベクターが最もよく使われます。「とりあえず困ったら vector」という判断は、多くの場合で正解です。
リスト（std::list）は、配列やベクターとは異なり、各要素が前後の要素へのリンクを持つ構造で実装されています。このため、任意の位置への要素の挿入や削除を効率よく行うことができます。その代わり、インデックスを指定して該当位置の要素を取得することはできません。途中に頻繁に挿入・削除が発生する、という特殊な用途向けのデータ構造です。
2.12.3.1. 配列#
C/C++ で配列を作成する場合は、あらかじめサイズを指定する必要があります。例えば、10 個の整数を保存するための配列を宣言する場合は、int arr[10] のように記述します。
int arr[10];
このとき、arr[0] から arr[9] までの 10 個の要素を保存するための領域が、メモリ上のどこかに確保されます。なお、これは変数の代入と同様に、宣言しただけではどのような値が入るのかはわかりません。
宣言と同時に値を初期化する場合は、例えば、次のように記述ができます。
int arr1[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
int arr2[10] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
int arr3[10] = {1, 1, 2, 3, 5, 8};
また、このように int 型で配列を宣言した場合、各要素には整数しか保存できません。小数や文字列などを代入しようとすると、コンパイルエラーになります。
配列から要素を取り出すときは、0 から始まるインデックスを指定します。
int arr[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
printf("%d\n", arr[0]); // 1
printf("%d\n", arr[1]); // 1
printf("%d\n", arr[2]); // 2
printf("%d\n", arr[3]); // 3
for を用いて、配列の要素を順に取り出すこともできます。この際に、配列の要素数を把握しておく必要があります。一般的に、配列全体のバイト数を 0 番目の要素のバイト数で割ることで、要素数を求めます。
int arr[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
int arr_length = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < arr_length; i++) {
printf("%d\n", arr[i]);
}
2 次元配列を宣言する場合は、1 次元目と 2 次元目それぞれの要素数を指定する必要があります。
int arr[4][3];
arr[0][0] = 11;
arr[0][1] = 12;
arr[0][2] = 13;
arr[1][0] = 21;
arr[1][1] = 22;
arr[1][2] = 23;
2 次元配列の各要素が既知である場合は、次のように宣言できます。
int arr[4][3] = {{11, 12, 13},
{21, 22, 23},
{31, 32, 33},
{41, 42, 43}};
配列中の各要素を取り出すときは、1 次元配列と同様に添字を 0 から順に増やします。
int arr[4][3] = {{11, 12, 13},
{21, 22, 23},
{31, 32, 33},
{41, 42, 43}};
printf("%lu\n", sizeof(arr)); // 48
printf("%lu\n", sizeof(arr[0])); // 12
printf("%lu\n", sizeof(arr[0][0])); // 4
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
for (int j = 0; j < sizeof(arr[0]) / sizeof(arr[0][0]); j++) {
printf("%d\n", arr[i][j]);
}
}
C/C++ の配列は固定長であり、一度作成すると長さを変更できません。しかし、一度作成した配列に対して、そのの長さを後から変更したい場合は、配列用のメモリ領域を動的に管理します。次のコードでは、整数型の要素を 4 個保存する配列を作成し、その後 16 個保存できるように拡張する例です。malloc および realloc で確保した領域には不定値が入るため、memset 関数ですべての要素を 0 に初期化しています。また、一度確保したメモリ領域は、使用しなくなった時点で free 関数により解放する必要があります。
#include <cstdlib>
#include <cstdio>
#include <cstring>
int main() {
int n = 4;
int *arr;
arr = (int *) malloc(sizeof(int) * n);
if (arr == NULL) {
printf("Memory cannot be allocated.");
} else {
memset(arr, 0, sizeof(int) * n);
arr[0] = 1;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
}
int m = 16;
arr = (int *) realloc(arr, sizeof(int) * m);
if (arr == NULL) {
printf("Memory cannot be enlarged.");
} else {
memset(&(arr[n]), 0, sizeof(int) * (m - n));
arr[4] = 5;
arr[5] = 8;
}
for (int i = 0; i < m; i++) {
printf("%p %d\n", &(arr[i]), arr[i]);
}
free(arr);
return 0;
}
C++ には、配列をより安全かつ便利に扱える array クラスがあります。array クラスを使用すると、通常の配列と同様の操作に加え、size、front、back、fill などのメンバー関数を利用できます。ただし、array クラスも固定長であり、一度作成すると後から長さを変更できません。
#include <iostream>
#include <array>
int main() {
std::array<int, 10> arr{1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
if (!arr.empty()) {
std::cout << arr.size() << std::endl; // 10
}
for (int i = 0; i < arr.size(); i++) {
std::cout << arr[i] << std::endl;
}
std::cout << arr.front() << std::endl; // 1
std::cout << arr.back() << std::endl; // 55
return 0;
}
fill 関数を使用すると、配列中のすべての要素を同じ値で埋められます。次のコードは、長さ 10 の array を生成し、各要素を 256 で埋める例です。
#include <iostream>
#include <array>
int main() {
std::array<int, 10> arr;
arr.fill(256);
return 0;
}
2.12.3.2. ベクター#
ベクターは、配列を拡張したクラスで、あらかじめサイズを指定しなくても利用できる点が特徴です。そのため、添字を用いて要素にアクセスしたり、最後の要素に新しい値を追加したりすることができます。C++ の vector は、動的配列とも呼ばれます。vector クラスは、C/C++ の配列をサイズを意識せずに利用できるように拡張したものです。
次の例は、空のベクターを作成し、その後 push_back 関数を利用してベクターの末尾に要素を次々と追加し、最後にベクターの各要素を順番に出力する例です。
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
for (int x : v) {
std::cout << x << std::endl;
}
// 10
// 20
// 30
// 40
return 0;
}
vector クラスには push_back のほかに、clear、size、empty などのメンバー関数があります。clear はすべての要素を削除する関数、size は要素数を返す関数、empty はオブジェクトが空かどうかを判定する関数です。
#include <iostream>
#include <string>
#include <vector>
int main(void) {
std::vector<std::string> dnaSeq;
dnaSeq.push_back("CAGTT");
dnaSeq.push_back("GCC");
dnaSeq.push_back("CCTAGATATA");
std::cout << dnaSeq.size() << std::endl;
// 3
std::cout << dnaSeq.empty() << std::endl;
// 0
dnaSeq.clear();
std::cout << dnaSeq.size() << std::endl;
// 0
std::cout << dnaSeq.empty() << std::endl;
// 1
return 0;
}
2.12.3.3. リスト#
リスト（std::list） は、ベクターとは異なり、末尾だけでなく 先頭や任意の位置に要素を挿入・削除できる データ構造です。これは、リストが連結リストとして実装されており、各要素が前後の要素へのリンクを保持しているためです。
先頭および末尾への要素を追加するには、それぞれ push_front、push_back メンバー関数を利用します。次の例では、リストの先頭と末尾に要素を追加し、リスト中のすべての要素を順番に出力しています。
#include <iostream>
#include <string>
#include <list>
int main(void) {
std::list<std::string> dnaSeq;
dnaSeq.push_back("AAAAA");
dnaSeq.push_back("CCCCC");
dnaSeq.push_front("GGGGG");
for (const auto& s : dnaSeq) {
std::cout << s << std::endl;
}
// GGGGG
// AAAAA
// CCCCC
return 0;
}
次に、5 要素からなるリストを作成し、先頭から 3 番目の要素を削除してから、さらに先頭から 4 番目の位置に新しい要素を挿入する例を示します。
#include <iostream>
#include <string>
#include <list>
#include <iterator>
int main() {
std::list<std::string> dnaSeq = {
"CGCGC",
"TTTTT",
"GGGGG",
"AAAAA",
"CCCCC"
};
for (const auto& s : dnaSeq) {
std::cout << s << std::endl;
}
// delete 3rd element
dnaSeq.erase(std::next(dnaSeq.begin(), 2));
// insert element at 4th position
dnaSeq.insert(std::next(dnaSeq.begin(), 3), "ATATA");
for (const auto& s : dnaSeq) {
std::cout << s << std::endl;
}
return 0;
}
このプログラムでは、イテレーターを順に進めることで削除や挿入を行う位置を指定しています。list では添字による直接アクセスができないため、このようにイテレーターを用いて要素の位置を操作する点が重要です。