便利なSTL Useful STL

C++

概要 Abstract

ACM-ICPCに向けて練習する中で便利だった, 又は便利そうだったSTLをまとめました. STLはC++の標準ライブラリで様々な機能が詰め込まれております. 今回まとめたのはその中でも特に便利だと思ったものです.

I sammarized useful STL for programming contest like ACM-ICPC. STL is C++ standard template library which contains valiable functions. In this article, the most useful things of them are summerized.

目次

Lambda, Container, Algorithm

ラムダ式は関数です. 次のように書きます.

[](引数の型 引数名){ 処理; }

Lambda is a function. You can write as follows.

[](Type arg){ doSomething; }

ラムダ式は関数内で定義することができます. 変数に代入することができます. 呼び出しは()を使用し, 引数があれば()に入れます.

You can write Lambda in any function. You can assign Lambda to argument. To call Lambda function, use () with arguments.

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

int main(void){
    auto greeting = [](string name){
        cout << "My name is " + name + "." << endl;
    };
    greeting("Jumpaku");
    // My name is Jumpaku.

    double average = [](double a, double b) {
        return (a + b) / 2.0;
    }(28.3, 10.89);
    cout << average << endl;
    // 19.595
}

コンテナとは要素の集まりです. list, vector, array, map, set, ...などがあります.

アルゴリズムはコンテナに対する様々な便利関数です. アルゴリズムの関数はイテレータを通してコンテナを操作します. アルゴリズムで使用する条件や処理, 比較などはラムダ式などを使って指定します.

Container is collection of elements like list, vector, array, map, set...

Algorithm is operations for containers. Algorithm functions operate container with iterator. Specifying conditions, operations, or comparators by Lambda, you can use algorithm functions.

入出力 Input and Output

cin, cout

cinを使うと入力が楽です. また簡単な出力はcoutが楽です.

With cin, you can get any input easily. cout is for simple output.

#include<iostream>
using namespace std;

int main(void){
    int n;
    double x;
    char c;
    cin >> n >> x >> c; // 3 1.66 A
    cout << n << " " << x << " " << c << endl; // 3 1.66 A 
}

printf

出力形式が複雑な場合はcoutよりprintfの方が使い易いかもしれません.

If output format is complex, printf is easier than cout.

#include<iostream>
using namespace std;

int main(void){
    printf("%-15s : %02d%02d", "4 digits time", 14, 9);
    // 4 digits time   : 1409
    printf("%-15s : %04x", "hexadecimal", 1089);
    // hexadecimal     : 0441
    printf("%-15s : %+.3lf %+.3lf", "decimal point", 10.89, -2.837870822);
    // decimal point   : +10.890  -2.837
}

コンテナ Container

vector, list

要素数が予め決まっているならvectorの方が良いです. vectorは[]で添字を使って要素にアクセスできます.

If the number of elements is decided, you should use vector.

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

int main(void){
    int n;
    cin >> n;
    vector<int> is(n);
    for(int i = 0; i < n; ++i){
        cin >> is[i]
    }
}

要素数が不明ならlistの方が良いです.

If the number of elements is unknown, you should use list.

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

int main(void){
    list<int> is;
    int tmp;
    while(cin >> tmp){
        is.push_back(tmp);
    }
}

for_each, sort, reverse

for_eachはコンテナの要素に同じ処理を施します.処理はlambdaなどで渡します.

sortはデフォルトで昇順でソートします.ソート順はlambdaなどで指定できます.

reverseはコンテナの要素の並びを逆にします.

for_each executes specified action for each element of container. You can specify the action with lambda.

sort sorts elements by specified order. You can specify the order with lambda. Default order is ascending order.

reverse reverses elements of the container.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void){
    vector<int> is = { 1, 0, 8, 9, 2, 8, 3 };

    for_each(is.begin(), is.end(), [](int const &i){
        cout << i << ",";
    });
    cout << endl;
    // 1,0,8,9,2,8,3,

    sort(is.begin(), is.end(), [](int const &a, int const &b){ return a > b; });
    for_each(is.begin(), is.end(), [](int const &i){
        cout << i << ",";
    });
    cout << endl;
    // 9,8,8,3,2,1,0,

    reverse(is.begin(), is.end());
    for_each(is.begin(), is.end(), [](int const &i){
        cout << i << ",";
    });
    cout << endl;
    // 0,1,2,3,8,8,9,
}

iota, transform, copy_if

iotaは指定された値からインクリメントしながら連続した値を生成し, コンテナに入れます.つまりrangeの生成です.

transformはコンテナの各要素を指定された法則で変換します. 変換法則はlambdaなどで指定します.

copy_ifは入力コンテナに含まれる要素の中で指定された条件を満たす要素のみを出力コンテナにコピーします. 条件はlambdaなどで指定します.コピー後は出力コンテナをリサイズしましょう.

iota generates range. From specified start value, incrementing repeatedly, iota generates values.

transform transforms values of input container by specified function and copies them to output container. Transformation function can be specified by lambda.

copy_if copies elements of input container which satisfy specified condition to output container. The condition can be specified by lambda. You should resize output container after copying.

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;

int main(void){
    vector<int> range(10);

    iota(range.begin(), range.end(), 0);
    for_each(range.begin(), range.end(), [](int const &i){
        cout << i << ",";
    });
    cout << endl; // 0,1,2,3,4,5,6,7,8,9,

    vector<int> squared(range.size());
    transform(range.begin(), range.end(), squared.begin(), [](int cost &i){
        return i * i;
    });
    for_each(squared.begin(), squared.end(), [](int const &i){
        cout << i << ",";
    });
    cout << endl; // 0,1,4,9,16,25,36,49,64,81,

    vector<int> evens(squared.size());
    auto copiedEnd = copy_if(squared.begin(), squared.end(), evens.begin(), [](int const &i){
        return i%2 == 0;
    });
    evens.resize(distance(evens.begin(), copiedEnd));
    for_each(evens.begin(), evens.end(), [](int const &i){
        cout << i << ",";
    });
    cout << endl; // 0,4,16,36,64,
}

find_if, max_element, min_element

find_ifはコンテナに含まれる要素の中で最初の条件を満たす要素のイテレータを返します.条件はlambdaなどで指定します.

max_elementはコンテナに含まれる要素の中で最後の最大の要素のイテレータを返します.

min_elementはコンテナに含まれる要素の中で最後の最小の要素のイテレータを返します.

find_if returns the iterator of the first element which satisfies specified condition. The condition can be specified by lambda.

max_element returns the iterator of the last maximum element of the container.

min_element returns the iterator of the last minimum element of the container.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void){
    vector<int> is = { 1, 0, 8, 9, 2, 8, 3 };

    auto firstEven = find_if(is.begin(), is.end(), [](int const &i) {
        return i % 2 == 0;
    });
    cout << *firstEven << endl; // 0

    auto max = max_element(is.begin(), is.end());
    cout << *max << endl; // 9

    auto min = min_element(is.begin(), is.end());
    cout << *min << endl; // 0 
}

all_of, any_of, none_of, count_if

all_ofはコンテナの要素の全てが指定された条件を満たす場合真を返します. 条件はlambdaなどで指定します.

any_ofはコンテナの要素のどれか1つ以上が指定された条件を満たす場合真を返します. 条件はlambdaなどで指定します.

none_ofはコンテナの要素のどれもが指定された条件を満たさない場合真を返します. 条件はlambdaなどで指定します.

cout_ifはコンテナに含まれる要素の中で指定された条件を満たす要素を数え上げます. 条件はlambdaなどで指定します.

all_of returns true if all elements of the container satisfy specified condition. The condition can be specified by lambda.

any_of returns true if any elements of the container satisfy specified condition. The condition can be specified by lambda.

none_of returns true if none elements of the container satisfy specified condition. The condition can be specified by lambda.

count_if counts the number of elements which satisfy specified condition. The condition can be specified by lambda.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void){
    vector<int> is = { 1, 0, 8, 9, 2, 8, 3 };
    auto isEven = [](int const &i) {
        return i%2 == 0;
    };
    bool any =  any_of(is.begin(), is.end(), isEven);
    cout << any << endl; // 1

    bool all = all_of(is.begin(), is.end(), isEven);
    cout << all << endl; // 0

    bool none = none_of(is.begin(), is.end(), isEven);
    cout << none << endl; // 0

    int count = count_if(is.begin(), is.end(), isEven);
    cout << count << endl; // 4
}

remove_if

remove_ifは指定された条件を満たす要素をコンテナの後ろに集め, 集めた要素の最初のイテレータを返します. コンテナから完全に取り除くにはeraseを使います. 条件はlambdaなどで指定します.

remove_if collects elements which satisfy specified condition, puts them to back of the container, and returns the iterator of first element of them. To erase them, you must use erase. The condition can be specified by lambda.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void){
    vector<int> odds = { 1, 0, 8, 9, 2, 8, 3 };
    for_each(odds.begin(), odds.end(), [](int const &odd) {
        cout << odd << endl;
    });
    // 1,0,8,9,2,8,3,

    auto removedEnd = remove_if(odds.begin(), odds.end(), [](int const &i) {
        return i%2 == 0;
    });
    odds.erase(removedEnd, odds.end());

    for_each(odds.begin(), odds.end(), [](int const &odd) {
        cout << odd << endl;
    });
    // 1,9,3,
}

文字列 String

string

stringのコンストラクタで文字列リテラルからstringを生成できます.

findでテキスト文字列に含まれるパターン文字列の検索ができます.findはパターン文字列が見つかった場合そのパターン文字列の先頭文字のテキスト文字列内での添字を返し, 見つからなかった場合string::noposを返します.

[ ]で添字を使った文字へのアクセスができます.

substrで部分文字列を取得できます.1つ目の引数が部分文字列の先頭の添字, 2つ目の引数が部分文字列の長さです.

+, +=で文字列の結合, 追加ができます.

c_strでchar配列の文字列を取得できます.

sizeで文字列の要素数を取得できます.

<, <=, >, >=, ==, !=などで辞書順の比較ができます.

With constructor of string, you can make string from string literal.

With find, you can find pattern in the text. find returns index of first element of pattern if pattern exists; otherwise find returns string::nopos.

With [], you can access to a character with index.

With c_str, you can get string of char array.

With size, you can get size of the string.

With <, <=, >, >=, ==, or !=, you can compare strings by lexical order.

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

int main(void){
    string s = "Jumpaku's blog";

    auto beginOfPaku = s.find("paku");
    cout << s[0] << s[1] << s[2] << s.substr(beginOfPaku, 4) << endl;
    // Jumpaku

    s += " is interesting.";
    printf("%s\nsize : %u\n", s.c_str(), s.size());
    // Jumpaku's blog is interesting.
    // size : 30

    string s1 = "aaa", s2 = "aaaa", s3 = "aba", s4 = "abb" , s5 = "abb";
    cout << (s1 < s2 && s2 < s3  && s3 < s4 && s4 == s5) << endl;
    // 1
}

to_string, stoi, stod

to_stringは数値を文字列に変換します.

stoi, stodは文字列をintやdoubleの数値に変換します.

to_string converts numerical value into string.

stoi or stod converts string into int or double value.

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

int main(void){
    string s1 = to_string(1089);
    string s2 = to_string(-283);
    cout << "1089 - 283 = " << (stoi(s1) + stoi(s2)) << endl;
    // 1372

    double d1 = stod("-123.456");
    double d2 = stod("987.654");
    cout << "d1 + d2 = " + to_string(d1 + d2) << endl;
    // 864.198000
}

stringstream

sstreamを使うとcinやcoutと同じような使い方で文字列と数値の変換ができます.

With stringstream, you can canvert between numerical value and string like cin or cout.

#include<iostream>
#include<string>
#include<sstream>
using namespace std;

int main(void){
    double a, b;
    stringstream("1089.283 283.1089") >> a >> b;
    cout << a + b << endl;
    // 1372.39

    stringstream ss2;
    string s1, s2, s3;

    ss2 << 123 << " " << 456 << " " << 789;
    ss2 >> s1 >> s2 >> s3;
    cout << s1 + s2 + s3 << endl;
    // 123456789
}

順列

next_permutation

要素が昇順に並んだコンテナに対して, falseが返るまで繰り返しnext_permutationを呼ぶと, 全ての順列を列挙することができます.

To enumerate all permutation, apply naxt_permutation to sorted container by ascending order until next_permutation return false.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(void){
    string s = "abc";
    do {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
    // abc
    // acb
    // bac
    // bca
    // cab
    // cba

    vector<int> is = { 1, 2, 3 };
    do {
        cout << is[0] << is[1] << is[2] << endl;
    } while (next_permutation(is.begin(), is.end()));
    // 123
    // 132
    // 213
    // 231
    // 312
    // 321
}