lower_boundやupper_boundを使用してイテレーターを取得する際に、取得した値をそのまま使用することができないことに注意する。

distanceを使用して、整数型にすると扱いやすい。

vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

auto itr = lower_bound(data.begin(), data.end(), 5); // 5以上 戻り値はイテレーター
int d = distance(data.begin(), itr); // 要素5の場所を示す4を返す

itr = upper_bound(data.begin(), data.end(), 5); // 5より大きい
d = distance(data.begin(), itr); // 要素6の場所を示す5を返す

以下はDFSの簡易コードである。

void dfs(int node, vector<vector<int>> graph, vector<bool> seen){
    seen[node] = true;

    for(auto x : graph[node]) if(!seen[x]) check(x, graph, seen);
}

int main(){
    vector<vector<int>> graph(n); // 有向グラフの作成
    vector<bool> seen(n); // 探索済を管理する

    dfs(start, graph, seen);

    return 0;
}

しかし、上記のコードでは実行時間が増大する可能性がある。

以下のように修正することによって問題が解決する。

void dfs(int node, vector<vector<int>> graph, vector<bool> seen) // 修正前
void dfs(int node, vector<vector<int>> &graph, vector<bool> &seen) // 修正後

問題点は値渡しと参照渡しの違いである。

修正前のコードは値渡し、つまり関数を呼び出す度に数値をコピーしている。そのためオブジェクト構築のために時間が必要となり処理時間が増大する。

したがって値渡しではなく、参照渡しを使用し処理時間の増大が起きないように修正する。

#include <map>

//方法1
for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
    cout << itr->first << " " << itr->second << endl;
}

//方法2
for (const auto& [k, v] : data) {
    cout << k << " " << v << endl;
}

#include <set>

// 宣言
multiset<int> num;
multiset<int> num{3, 1, 4, 4, 3}; // {1, 3, 3, 4, 4}のように格納される

//追加
num.insert(2);

//ある値の要素を全て削除 戻り値は削除した要素数
num.erase(2);

//要素を全て出力1
for(auto itr = num.begin(): itr != num.end(); ++itr){
  cout << *itr << endl;
}

//要素を全て出力2
for (auto x : num) {
  cout << x << endl;
}

//ある値の要素数
num.count(2);

#include <algorithm>

vector<int> num{1, 2, 3};
do{
    for(auto x : num){
        cout << x << " ";
    }
    cout << endl;
}while( next_permutation(num.begin(), num.end()) );

//結果
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

next_permutationは次の順列を生成し、numに格納する。

最後から最初の順列を生成したときのみfalseを返し、それ以外はtrueを返す。したがって上記のコードの場合、numの最終状態は昇順にソートされた状態である。

上記のようなコードで全列挙をしたい場合、初期状態は昇順にソートされている必要があるが、あらかじめ要素数がわかっている場合はdo-while文ではなくfor文を使用すればいいため、必ずしも初期配列である必要はない。

#include <set>

// 宣言方法
set<int> num; //宣言のみ
set<int> num{3, 1, 3, 4}; // {1, 3, 4}のように格納される

//追加
num.insert(2);

//削除
num.erase(2); //戻り値は削除した要素の個数(0 or 1)

//要素を全て出力1 itrの型を指定するのは大変なので、autoを使用する。
for(auto itr = num.begin(); itr != num.end(); ++itr){
    cout << *itr << endl;
}

//要素を全て出力2
for (auto x : num) {
  cout << x << endl;
}

//探索(要素の有無) 二分探索なので探索時間はlog(N)
if(num.find(2) != num.end()){
    cout << *itr << endl;
}