STL/リスト (C++をもう一度)
[履歴] (2014/12/28 02:17:18)
最近の投稿
注目の記事

サンプルコード

#include <iostream>
#include <list>
using namespace std;

void Show(list<int>::iterator begin, list<int>::iterator end) {
    for( list<int>::iterator it = begin; it != end; ++it) {
        cout << *it << ' ' << flush;
    }
    cout << endl;
}

int main() {
    list<int> lst; // 双方向リスト。リストは配列と比較して:
    // - 要素の削除や追加のコストは低い
    // - 要素アクセスのコストは高い
    // - メモリもポインタの分だけ余分に必要
    cout << lst.size() << endl; //=> 0

    // 追加
    lst.push_front(1); // [1]
    lst.push_back(1); // [1,1]

    // 削除 (返り値なし)
    lst.pop_front(); // [1]
    lst.pop_back(); // []

    // すべて削除
    lst.clear();
    cout << lst.size() << endl; //=> 0
    cout << boolalpha << lst.empty() << endl; //=> true

    // リストを長くする (既定値の設定が可能)
    lst.resize(1, -1); // [-1]
    lst.resize(3, -2); // [-1,-2,-2]

    // リストを短くする
    lst.resize(2); // [-1,-2]

    // 要素へのアクセス
    Show(lst.begin(), lst.end()); //=> -1 -2
    cout << lst.front() << endl; //=> -1
    cout << lst.back() << endl; //=> -2

    // 指定位置に値を挿入
    list<int>::iterator pos = lst.begin();
    lst.insert(pos, -3);
    Show(lst.begin(), lst.end()); //=> -3 -1 -2

    // 指定位置の要素を削除
    cout << *pos << endl; //=> -1
    lst.erase(pos);
    Show(lst.begin(), lst.end()); //=> -3 -2

    // 指定範囲の要素を削除
    lst.push_back(0); //=> -3 -2 0
    lst.erase(++lst.begin(), lst.end());
    Show(lst.begin(), lst.end()); //=> -3

    // リストからリストへの要素の移動 (接合)
    list<int> other(5, 1); // 1 1 1 1 1

    // lst.splice(lst.begin(), other); // 指定位置にすべて移動
    // Show(lst.begin(), lst.end()); //=> 1 1 1 1 1 -3
    // Show(other.begin(), other.end()); //=> (空)

    // lst.splice(lst.begin(), other, other.begin()); // 指定位置に指定位置の要素を移動
    // Show(lst.begin(), lst.end()); //=> 1 -3
    // Show(other.begin(), other.end()); //=> 1 1 1 1

    lst.splice(lst.begin(), other, other.begin(), other.end()); // 指定位置に指定範囲の要素を移動
    Show(lst.begin(), lst.end()); //=> 1 1 1 1 1 -3
    Show(other.begin(), other.end()); //=> (空)

    // 並べ替え
    lst.push_front(-2); //=> -2 1 1 1 1 1 -3
    lst.sort(); // 既定は昇順
    // lst.sort(less<int>()); // 明示的に昇順
    // lst.sort(greater<int>()); // 降順
    Show(lst.begin(), lst.end()); //=> -3 -2 1 1 1 1 1

    // 重複要素を削除
    lst.unique();
    Show(lst.begin(), lst.end()); //=> -3 -2 1

    return 0;
}
関連ページ
    概要 配列のように複数の要素の入れ物として機能するクラスをコンテナとよびます。コンテナクラスには vector、list、queue/stack などがあります。それぞれのコンテナクラスはクラステンプレートとして提供されており、したがってヘッダファイルを include するだけで使用できます。ヘッダファイルにはコンテナクラスのクラステンプレートだけでなく、そのコンテナのイテレータクラスのクラス
    概要 限られた時間の中で問題を解くために必要となる、競技プログラミングにおける基本的な処理のチートシートです。競プロにおけるメジャー言語 C++ を利用します。その際 C++11 の機能は利用せず C++03 の機能の範囲内で記述します。 頻度高く定期的に開催されるコンテスト AtCoder Codeforces