シーケンスコンテナ

STLコンテナ型その1

シーケンスコンテナはSTLコンテナの一種です。
以下のコンテナクラスがシーケンスコンテナに分類されます。

シーケンスコンテナは要素の並び順をプログラマが任意に制御できます。
これらはさらに「配列タイプ」と「リストタイプ」に分類できます。

配列タイプ

arrayクラス、vectorクラス、dequeクラスは配列タイプです。
これらのクラスはメモリ上の要素の並びが配列のように連続しているのが特徴です。

arrayクラスのみ、要素の追加や削除はできず要素数は固定です。
以下の説明中での要素の追加や削除についてはarrayクラスは除きます。

ランダムアクセスは高速です。
要素の挿入/削除は低速です。
要素の検索は低速です。

ただし、vectorクラスは末尾への追加/削除は高速です。
dequeクラスは先頭と末尾への追加/削除は高速です。

vectorクラスに要素を挿入すると、挿入位置から後方にあるすべての要素が後ろにずらされます。
末尾に挿入(追加)した場合は後ろにずらす処理がないので高速ですが、先頭への挿入は全ての要素をずらすことになるため、先頭に近い位置への挿入ほど低速になります。

dequeクラスはvectorクラスとほぼ同じものとして使用できます。
先頭要素への要素追加/削除がvectorクラスよりも高速ですが、その代わりに内部構造が複雑化しており、その他の速度はvectorクラスにわずかに劣ります。

arrayクラスとvectorクラスは先頭要素から末尾要素までメモリ上に連続して配置されることが保証されており、先頭要素からのポインタ演算で各要素にアクセスできます。
dequeクラスはこのような並び方である保証はなく、要素アクセスにはイテレータを使用する必要があります。

リストタイプ

listクラス、forward_listクラスはリストタイプです。

ランダムアクセスはできません。
要素の挿入/削除は高速です。
要素の検索は低速です。

ランダムアクセスができないというのは、イテレータへのit[3]や(it + 3)などの演算で要素アクセスができないということです。
リストタイプは各要素のメモリ上の配置位置に決まりはなく、各要素が自分自身の前後の要素のアドレスを格納することでリスト全体を構成しています。
そのため各要素へのアクセスは先頭/末尾から順に要素をたどっていくしかありません。
その代わりに要素の挿入/削除はアドレス情報の書き換えだけで済むため高速に処理できます。

forward_listクラスはイテレータに--演算が出来ません。
つまり前方向に進む事しかできず、後方向(並び順で言えば手前)に戻ることはできません。
後方要素の情報を持たないため、その分listクラスよりもメモリ効率が良いです。

速度比較

各シーケンスコンテナの速度と簡単な特徴のまとめです。

◎=高速、△=低速、-=使用不可

共通のメンバ関数

シーケンスコンテナで共通するメンバ関数の対応一覧です。
一覧にない、コンテナクラス固有のメンバ関数は後述します。

arrayクラスやvectorクラスと共通の関数はそれぞれのページを参照してください。
イテレータについてはイテレータの項を参照してください。
以下は、上記のページでは説明していない関数について説明します。

std::vector<int> vec;

//全て同じデータ型
std::vector<int>::iterator it1;
auto it2 = vec.begin();
decltype(vec)::iterator it3;

push_front、emplace_front関数

push_front関数、emplace_front関数は要素の先頭に新しい要素を追加します。
戻り値はありません。

#include <iostream>
#include <list>

int main()
{
    std::list<int> lst{ 1, 2, 3 };
    
    lst.push_front(0);
    lst.emplace_front(-1);

    for (auto e : lst) {
        std::cout << e << " ";
    }
    //-1 0 1 2 3
}

push_front関数とemplace_front関数の違いは、引数から直接オブジェクトを生成できる点です。

#include <iostream>
#include <string>
#include <list>

class TestClass
{
    int n;
    std::string s;

public:
    TestClass(int n, std::string s)
        : n(n), s(s) {}
};

int main()
{
    std::list<TestClass> lst;

    //これでも可能だが
    lst.emplace_front(TestClass(1, "abc"));

    //こういう書き方もできる
    lst.emplace_front(1, "abc");

	//これはできない
    //lst.push_front(1, "abc");
}

emplace系の関数は、実引数に目的のクラス(今回はTestClass)のインスタンスを指定する以外にも、クラスのコンストラクタに渡す値を直接指定することでもインスタンスを生成でき、コンテナクラスに追加できます。

emplace_front関数はpush_front関数よりも高速に動作する可能性があります。
push_front関数は「オブジェクトを生成して、それをコピーしたもの」が追加されますが、emplace_front関数は「オブジェクトを生成したもの」が直接追加されます。

push_back、emplace_back関数

push_back関数、emplace_back関数は要素の末尾に新しい要素を追加します。
追加位置が末尾である以外はpush_front関数、emplace_front関数と同じです。

pop_front、pop_back関数

pop_front関数は先頭要素を削除します。
pop_back関数は末尾要素を削除します。

引数や戻り値はありません。

listクラス、forward_listクラスのメンバ関数

listクラスとforward_listクラスには上記以外にもメンバ関数が存在します。
(vectorクラス固有のメンバ関数はvectorクラスの項で説明しています)

insert_after、emplace_after、erase_after関数(forward_list)

forward_listクラスでは、insert関数はinsert_after関数、emplace関数はemplace_after関数、erase関数はerase_after関数として提供されています。
vectorクラスなどのinsert関数は指定の位置への要素の挿入を行いますが、forward_listクラスのinsert_after関数は指定の位置の後ろに要素の挿入を行います。
emplace_after関数、erase_after関数も同様に指定の要素の後ろに対する操作となります。
forward_listは手前の要素に対する情報を持たないためこのような動作になります。

std::vector<int> vec{ 1, 2, 3, 4, 5 };
std::forward_list<int> flst{ 1, 2, 3, 4, 5 };

std::vector<int>::iterator itV = vec.begin();
std::forward_list<int>::iterator itF = flst.begin();

vec.insert(++itV, 9);			//1番目に挿入
flst.insert_after(++itF, 9);	//1番目の後ろに挿入

itV = vec.begin();
itF = flst.begin();

while (itV != vec.end())
{
	std::cout << *itV++ << " ";
}

std::cout << std::endl;

while (itF != flst.end())
{
	std::cout << *itF++ << " ";
}

1 9 2 3 4 5
1 2 9 3 4 5

merge関数

merge関数は、ふたつのコンテナを結合します。

#include <iostream>
#include <list>

int main()
{
    std::list<int> lst1 = { 1, 4, 7 };
    std::list<int> lst2 = { 3, 6, 9 };

    //マージ
	//lst2は空になる
    lst1.merge(lst2);

	//C++11以降はstd::moveを使用したほうが高速
	//lst1.merge(std::move(lst2));

    for (int x : lst1) {
        std::cout << x << " ";
    }
    //1 3 4 6 7 9

    std::cin.get();
}

引数に指定されたコンテナの中身はすべて移動し、中身は空になります。
この関数の戻り値はありません。

merge関数を実行するには、両方のコンテナがあらかじめ昇順で並べられている必要があります。
昇順に並んでいないコンテナに対してmerge関数を実行した場合の並び順は保証されません。

要素の並べ替えを行わずに、単純に結合する場合はinsert関数やsplice関数を使用します。

std::list<int> lst1 = { 1, 4, 7 };
std::list<int> lst2 = { 3, 6, 9 };

//lst1の末尾にlst2の先頭から末尾までをコピーして追加
//lst2の中身は残る
lst1.insert(lst1.end(), lst2.begin(), lst2.end());
//1 4 7 3 6 9

//lst1の末尾にlst2を移動して追加
//lst2は空になる
lst1.splice(lst1.end(), lst2);
//1 4 7 3 6 9 3 6 9

splice関数、splice_after関数

splice関数(listクラス)、splice_after関数(forward_listクラス)は、任意の位置に他のコンテナの要素を移動します。

{
	std::list<int> a = { 1, 2, 3 };
	std::list<int> b = { 7, 8, 9 };

	//aの0番目(先頭)にbを移動
	//移動なのでbは空になる
	a.splice(a.begin(), b);        
	//7 8 9 1 2 3

	//C++11以降はstd::moveを使用したほうが効率が良い
	//lst1.splice(lst1.begin(), std::move(lst2));
}
{
	std::list<int> a = { 1, 2, 3 };
	std::list<int> b = { 7, 8, 9 };

	//aの2番目直前にbの1番目の要素を移動
	a.splice(
		std::next(a.begin(), 2),
		std::move(b),
		std::next(b.begin())
		);
	//1 2 8 3

	b;
	//7 9
}
{
	std::list<int> a = { 1, 2, 3 };
	std::list<int> b = { 7, 8, 9 };

	//aの2番目直前にbの0番目から2番目の直前までの要素を移動
	a.splice(
		std::next(a.begin(), 2),
		std::move(b),
		b.begin(),
		std::next(b.begin(), 2)
	);
	//1 2 7 8 3

	b;
	//9
}

この関数の戻り値はありません。

なお、splice_after関数は指定の要素の後ろへの移動となります。

remove関数

remove関数は、コンテナから引数に一致する要素を削除します。

std::list lst = { 1, 2, 3, 1, 4, 5, 1 };

//「1」を削除
lst.remove(1);
//2 3 4 5

C++17まではこの関数の戻り値はありません。
C++20からは削除された要素数を返します。

remove_if関数

remove_if関数は、コンテナから引数に指定した条件に一致する要素を削除します。

「条件」には引数ひとつ、boo型を戻り値とする関数を指定します。
関数をわざわざ定義するのは面倒なので、C++11からはラムダ式を指定する方法がよく用いられます。

#include <list>

//引数が3未満なら真を返す関数
bool pred(int x)
{
    return x < 3;
}

int main()
{
	std::list<int> lst = { 1, 2, 3, 1, 4, 5, 1 };

	//関数predの条件で要素を削除
	lst.remove_if(pred);
	//3 4 5

	lst = { 1, 2, 3, 1, 4, 5, 1 };
	//ラムダ式で同様の記述を行う場合
	lst.remove_if([](int x) { return x < 3; });
	//3 4 5
}

C++17まではこの関数の戻り値はありません。
C++20からは削除された要素数を返します。

sort関数

sort関数は、コンテナの要素を昇順に並べ替えます。

std::list<int> lst = { 1, 4, 2, 9 };

//昇順に並べ替える
lst.sort();
//1 2 4 9

この関数の戻り値はありません。

降順に並べ替え

sort関数はデフォルトでstd::less<データ型>()という関数オブジェクトが並べ替えに使用されます。
これは昇順での並べ替えを行います。

降順での並べ替えはstd::greater<データ型>()を引数に指定することで行えます。

std::list<int> lst = { 1, 4, 2, 9 };
lst.sort(std::greater<int>());
//9 4 2 1

std::greaterは<functional>ヘッダファイルに定義があるので、使用できない場合はこれをインクルードしてください。

並べ替えの比較関数

list(forward_list)で自作のクラスや構造体を管理している場合、そのままでは並べ替えを行うことはできません。
これはオブジェクトの大小を比較する手段がないからです。

sort関数の引数に比較のための関数(ラムダ式でも可)を指定することで、独自のルールで並べ替えを行うことができます。

#include <list>

class TestClass
{
    int x;
    int y;

public:
    TestClass(int x = 0, int y = 0)
        : x(x), y(y) {}

    //インスタンス同士の順序の比較関数
    //これは昇順で並べ替えている
    static bool comp(const TestClass& a, const TestClass& b) {
        if (a.x < b.x) {
            return true;
        }
        else  if (a.x > b.x) {
            return false;
        }
        return (a.y < b.y);
    }
};

int main()
{
	std::list<TestClass> lst = {
		TestClass(1, 2),
		TestClass(3, 5),
		TestClass(2, 2),
		TestClass(3, 4),
	};
	
    //TestClass::comp関数のルールで並び替える
	lst.sort(TestClass::comp);
	//(x = 1, y = 2)
	//(x = 2, y = 2)
	//(x = 3, y = 4)
	//(x = 3, y = 5)
}

比較関数は以下の定義で行います。

bool cmp(const T& a, const T& b);

戻り値はbool型で、関数名や引数名は自由です。
aがbよりも小さい場合はtrueを返すようにすると昇順で並べ替えられます。
これを反対にすると降順となります。
上記コードは、メンバ変数xの値で並べ替えを行い、xの値が同じ場合はメンバ変数yの値で並べ替えを行っています。

<、>演算子のオーバーロード

独自の並べ替えルールは<または>演算子のオーバーロードでも定義することができます。

#include <list>

class TestClass
{
	int x;
	int y;

public:
	TestClass(int x = 0, int y = 0)
		: x(x), y(y) {}

	//「<」演算子のオーバーロード
	bool operator<(const TestClass& r) const
	{
		if (this->x < r.x) {
			return true;
		}
		else  if (this->x > r.x) {
			return false;
		}
		return (this->y < r.y);
	}

	//「>」演算子のオーバーロード
	bool operator>(const TestClass& r) const
	{
		if (this->x > r.x) {
			return true;
		}
		else  if (this->x < r.x) {
			return false;
		}
		return (this->y > r.y);
	}
};

int main()
{
	std::list<TestClass> lst = {
		TestClass(1, 2),
		TestClass(3, 5),
		TestClass(2, 2),
		TestClass(3, 4),
	};

	//昇順に並べ替える
	//オーバーロードした<演算子が比較に使用される
	lst.sort(); //std::less
	//(x = 1, y = 2)
	//(x = 2, y = 2)
	//(x = 3, y = 4)
	//(x = 3, y = 5)

	//降順に並べ替える
	//オーバーロードした>演算子が比較に使用される
	lst.sort(std::greater<TestClass>());
	//(x = 3, y = 5)
	//(x = 3, y = 4)
	//(x = 2, y = 2)
	//(x = 1, y = 2)
}

std::lessは<演算子、std::greaterは>演算子を使用します。

演算子オーバーロードはconst関数にする必要があります。

reverse関数

reverse関数は、コンテナの要素を前後逆に並べ替えます。

std::list<int> lst = { 1, 4, 2, 9 };

//前後を逆に並べ替える
lst.reverse();
//9 2 4 1

この関数の戻り値はありません。

unique関数

unique関数は、コンテナの重複する要素を削除します。

std::list<int> lst = { 1, 4, 5, 2, 4, 0, 5 };

lst.sort();
lst.unique();
//0 1 2 4 5

unique関数を実行するコンテナは、あらかじめ昇順または降順で並べられている必要があります。
そうでない場合、どのような結果になるかはコンパイラ依存です。

この関数の戻り値はありません。
C++20からは削除された要素数が返されます。

一致の比較関数

unique関数は、1番目の要素と0番目の要素を比較、2番目の要素と1番目の要素を比較…という処理を終端まで行い、一致した要素を削除します。
あらかじめ並び替えられていないと正しい結果が得られないのはこのためです。

自作のクラスや構造体の場合は==演算子をオーバーロードすることでunique関数を使用することができます。
その他、比較関数を独自に定義することもできます。
(ラムダ式でも可)

#include <list>

class TestClass
{
    int x;
    int y;

public:
    TestClass(int x = 0, int y = 0)
        : x(x), y(y) {}

	//sort関数用
    bool operator<(const TestClass& r)
    {
        if (this->x < r.x) {
            return true;
        }
        else  if (this->x > r.x) {
            return false;
        }

        return (this->y < r.y);
    }

    //==演算子のオーバーロード
    bool operator==(const TestClass& r) {
        return (this->x == r.x && this->y == r.y);
    }
    //インスタンス同士の一致の比較関数
    static bool equals(const TestClass& a, const TestClass& b) {
        return (a.x == b.x && a.y == b.y);
    }
};

int main()
{
    std::list<TestClass> lst = {
        TestClass(1, 2),
        TestClass(3, 5),
        TestClass(1, 2),
        TestClass(3, 4),
    };

    lst.sort();

	//比較関数を使用する
	lst.unique(TestClass::equals);
    //(x = 1, y = 2)
    //(x = 3, y = 4)
    //(x = 3, y = 5)

	//==演算子のオーバーロードを使用する
    lst.unique();
}