[C++]有用なライブラリと関数の整理


📌 リファレンス
アルゴリズムの問題を解決する際によく使用するライブラリと関数を更新し続けます.#include <algorithm>> find
template <class InpuptIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val);
反復文字
  • を返し、valに一致する最初の要素(最初から最後まで)を表します.
    一致する要素
  • が見つからない場合はlastを返します.
    🚨
  • stringライブラリのfind関数とは異なる
    // example
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    
    int main() {  
      vector<int> v = { 1,2,3,4,5 };
      auto iter = find(v.begin(), v.end(), 6);
      if (iter != v.end()) {
          cout << *iter << endl;
      }
      else {
          cout << "not found" << endl;
      }
      
      return 0;
    }
    > next_permutation & prev_permutation
    bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
    bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);
  • パラメータを使用してベクトルの反復器または配列のアドレス
  • を入力することができる.
  • firstは救いの順序の始まりであり、lastは救いの順序の終わりである
  • 次のシーケンスの結果をベクトルまたは配列に適用し、真の値
  • を返す.
    次のシーケンスがない場合はfalseを返します.
  • next permutation:データのソートが昇順であるため、次のシーケンスが前のシーケンスより小さい場合、
  • prev permutation:データのソートは降順であり、次のシーケンスが前のシーケンスより大きい場合、
  • #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main() {  
        vector<int> v;
        for (int i=1; i<=3; i++) {
            v.push_back(i);
        }
    
        // 오름차순으로 정렬된 vector에 대해 next_permutation 적용
        do {
            for (int i=0; i<v.size(); i++) {
                printf("%d ", v[i]);
            }
            printf("\n");
        } while(next_permutation(v.begin(), v.end()));
        /* 출력 결과
        1 2 3 
        1 3 2 
        2 1 3 
        2 3 1 
        3 1 2 
        3 2 1
        */
    
        // 내림차순으로 정렬된 vector에 대해 prev_permutation 적용
        sort(v.begin(), v.end(), greater<int>());
        do {
            for (int i=0; i<v.size(); i++) {
                printf("%d ", v[i]);
            }
            printf("\n");
        } while(prev_permutation(v.begin(), v.end()));
        /* 출력 결과
        3 2 1
        3 1 2
        2 3 1
        2 1 3
        1 3 2
        1 2 3
        */
    
        return 0;
    }
    > max_element & min_element
    template <class ForwardIterator>
    ForwardIterator max_element (ForwardIterator first, ForwardIterator last);
    template <class ForwardIterator, class Compare>
    ForwardIterator max_element (ForwardIterator first, ForwardIterator last, Compare comp);
  • 範囲[first,last]では
  • max element()最大値を返す反復器
  • min element()最小値を返す反復器
  • #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main() {  
        vector<int> v; // 1 2 3 4 5 6 7 8 9 10
        for (int i=0; i<10; i++) {
            v.push_back(i+1);
        }
    
        // 반환되는 iterator를 활용하여 최댓값, 최솟값의 인덱스 구하기
        int maxIndex = max_element(v.begin(), v.end()) - v.begin();
        int minIndex = min_element(v.begin(), v.end()) - v.begin();
        
        // 반환되는 iterator에 *연산자를 활용하여 최댓값, 최솟값 구하기
        int maxValue = *max_element(v.begin(), v.end());
        int minValue = *min_element(v.begin(), v.end());
    
        cout << "MAX index " << maxIndex << " value " << maxValue << endl;
        cout << "MIN index " << minIndex << " value " << minValue << endl;
        
        /* 출력 결과
        MAX index 9 value 10
        MIN index 0 value 1
        */
    
        return 0;
    }
    > lower_bound & upper_bound
    template <class ForwardIterator, class T>
    ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
  • 範囲[first,last]では
  • low boundの値はval値に等しい(ない場合、valより大きい値の中で最小の値).
    最初の位置を返す反復器
  • upper boundが返す反復器の初期値はval値
  • を超える
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main() {
        vector<int> v= { 1, 2, 2, 2, 3, 5, 7 };
    
        int firstIdx = lower_bound(v.begin(), v.end(), 2) - v.begin();
        int lastIdx = upper_bound(v.begin(), v.end(), 2) - v.begin();
    
        cout << "2 appears between idx [" << firstIdx << "," << lastIdx << ")" << endl;
        // 출력 결과: 2 appears between idx [1,4)
    
        return 0;
    }
    #include <string>> find
    size_t find(const string& str, size_T pos=0) const;
  • strは検索する文字列であり、posは検索する開始位置
  • である.
  • strが見つかった場合、その文字列で始まるインデックス
  • が返されます.
  • が見つからない場合はstring::npos returnと入力します.
    🚨
  • アルゴリズムライブラリのfind関数とは異なる
    // example
    #include <iostream>
    #include <string>
    using namespace std;
    
    int main() {  
        string word = "Hello World!";
        if (word.find("World") != string::npos) {
            cout << "Found, Index: " << word.find("World") << endl;
        }
        else {
            cout << "Not Found" << endl;
        }
    
        return 0;
    }