CPP アルゴリズム問題のための共通コンテナ技術

[[413003]]

アルゴリズムの問題を解決するときに CPP でよく使用されるコンテナテクニックを整理しました。新しい言語に出会ったとき、私はまず従属機能をどのように実装するかを考えます。アルゴリズムに関するメモはGitHub[1]で入手できます。

固定長配列

配列

可変長配列

ベクター

ハッシュテーブル

整列辞書

優先キュー

優先キューの再ロード

ソート

ソート戻りインデックス

固定長配列

必要とする：

申告と回収

配列

整数dx[4] = {0, 1, 0, -1};
 int a[N]; 
 
 0 から 10 まで

可変長配列

必要とする：

値: 先頭、末尾、インデックスを取得します
追加
両端を折る

ベクター

vector< int > ans(n); // 初期長さn、デフォルト値は0 
 
 // 値: 先頭、末尾、インデックスを取得します
答え.front();
回答.戻る();
答え[i] += 1; 
 
 // 追加
// std::vector はなぜ push_front をサポートしないのでしょうか? - ミロ・イップの答え - Zhihu
 // https://www.zhihu.com/question/51555037/answer/126373709
 ans.push_back(5); // O(1) 
 
 // 末尾を削除
ans.pop_back();

ハッシュテーブル

必要とする：

キー値がすでに存在します
整列辞書

マップ< int , int > S;
 // キー値は既に存在します
（S.カウント（5））の場合
    // S[5]が定義されている
それ以外 
    // S[5]は定義されていない

整列辞書

地図は赤黒木に基づいて順序付けられている
unordered_mapはマッピングに基づいて順序付けされておらず、より効率的である可能性があります。

優先キュー

必要とする：

弾丸を見るための空の定規
ストレージオブジェクトのオーバーロード
比較関数のオーバーロード

// デフォルトはビッグルートヒープです
priority_queue< int > ヒープ; 
 
 //小さなルートヒープに変更
priority_queue< int 、 vetor< int >、 greater< int > min_heap; 
 
 // 格納されている箇条書きを表示するための空の定規
ヒープを空にする();
ヒープサイズ();
ヒープトップ();
ヒープ.push(5);
ヒープをポップする

優先キューの再ロード

// 比較関数をオーバーロードする
構造体cmp{
    テンプレート<typename T, typename U>
    ブール演算子()(T const&左、U const &右) {
        if (左.秒<右.秒)戻り値 真実;
戻る 間違い;
    }
 }; 
 
 int main() {
    順序付けされていないマップ< int , int > mp;
    mp[3] = 4;
    mp[2] = 44;
    mp[12] = 432;
    // ストレージオブジェクトペア< int , int >をオーバーロードする
    priority_queue<pair< int , int >, vector<pair< int , int >>, cmp> pq(mp.begin ( ), mp.end ( )); //pqの初期化を完了する
} 
 
 // 著作権声明: この記事は CSDN ブロガー「leagalhigh」によるオリジナル記事であり、CC 4.0 BY -SA 著作権契約に準拠しています。転載の際は、元のソース リンクとこの声明を添付してください。
 // 元のリンク: https://blog.csdn.net/u014257954/article/details/78623215

ソート

必要とする：

ソートルールのオーバーロード
ソート戻りインデックス

ベクトル< int > ans;
 sort( ans.begin (), ans.end ( )); // デフォルトは小さい順から大きい順
 
ベクトル<ペア< int , int >> res;
 sort( res.begin ()), res.begin ( )); // デフォルトでは最初の要素を比較します

ソート戻りインデックス

ベクトル< int > データ = {5, 16, 4, 7};
ベクトル< int >インデックス( data.size (), 0);
 for ( int i = 0 ; i !=インデックス.サイズ() ; i++) {
インデックス[i] = i;
 }
ソート(インデックス.begin (),インデックス.end ( ),
    [&](const int & a, const int & b) {
戻り値(データ[a] < データ[b]);
    }
 );
 for ( int i = 0 ; i !=インデックス.サイズ() ; i++) {
    cout <<インデックス[i] << endl;
 }
 // 著作権声明: この記事は CSDN ブロガー「liangbaqiang」によるオリジナル記事であり、CC 4.0 BY -SA 著作権契約に準拠しています。転載の際は、元のソース リンクとこの声明を添付してください。
 // 元のリンク: https://blog.csdn.net/qq_36523492/article/details/114122256