Bo2SS

「コンテナ」とはなぜ引用符を付けるのか～下に進んでください

コース内容#

テンプレート <タイプ> 名；// カスタムタイプも可能、例えば struct

キューとスタック#

queue#

• 

• queue que;

• 名。方法 ()

  • que.push (5); // エンキュー
  • que.pop (); // デキュー
  • que.front (); // キューの先頭要素
  • que.size (); // 要素の数
  • que.empty (); // 空かどうか

stack#

• stack sta;
• 名。方法 ()
  • sta.push(5);
  • sta.pop();
  • sta.top(); // スタックのトップ要素、queue とは唯一異なる
  • sta.size();
  • sta.empty();

本質#

• それらの底層はdequeで実装されている
  • double-ended queue、両端キュー
  • 参考deque-cppreference
• それらは deque のラッパーで、実際にはアダプターである
  • deque こそが本物のコンテナである

ベクターと優先キュー#

vector#

【挿：C 言語では可変長配列を定義できない、❌このように定義してはいけない：int n; scanf ("% d", &n); int num [n]】

• vector v;
• 名。方法 ()
  • v.push_back (5); // 尾に要素を追加O(1)
  • v.size (); // 要素の数
  • v.insert (1, 6); // 要素を挿入O(N)、push_back を使った方が効率的
• vector<vector > v2; // 動的二次元配列
  • C++11 標準以前は "> >" の間にスペースが必要、さもなければ右シフト操作と誤解されやすい
  • 
• 初期化、参考vector のいくつかの初期化と代入方法-CSDN
• cin から vector に値を入れるには、まず vector のサイズを初期化する必要がある

priority_queue#

• priority_queue que;
  • int の後にソートするオブジェクトを追加できる
  • 参考C++ priority_queue (STL priority_queue) の使い方詳細解説-C 言語中文网
• 名。方法 ()
  • que.push(5);
  • que.pop();
  • que.top(); // ヒープのトップ要素、デフォルトは大きい数が上に
  • que.size();
  • que.empty();
• カスタム構造型の優先キューは小なり演算子をオーバーロードする必要がある
  • bool operator <(const struct 名 & 変数) {}
  • 注：小なり演算子をオーバーロードすると、このコンテナ内で実装される場合
    • a) <、大から小に並べる、対応するのは最大ヒープ
    • b) >、小から大に並べる、対応するのは最小ヒープ
    • 少しややこしい、詳細はコードデモを参照 - priority_queue
  • 注：すべてのソートが必要なコンテナ構造は、小なり演算子をオーバーロードする

本質#

• vector の底層は配列で実装されている
• priority_queue の底層はヒープで実装されている

文字列 string#

クラス

• string str;
• 名。方法 ()
  • str.size () //str.length () と同じ
  • str.find (s2, pos = 0); //str の中で s2 を探す、デフォルトは先頭 (pos = 0) から探し、見つけたらインデックスを返す
    • 底層のメソッド実装はコンパイラに依存する
    • 見つかったかどうかを判断する（no position）

if (str,find(s2) != string::npos) {
  // static const size_t npos = -1;
  // 見つかった
} else {
  // 見つからなかった
}

• • str.insert (x, s2); // インデックス x に s2 を挿入
  • str.substr (2); // インデックス 2 から最後までを切り取る
  • str.substr (2, len); // 注意：第二引数は長さ
  • str.replace (index, len, s2); // 同様に第二引数は長さに注意
• 多くの演算子をオーバーロードしている
  • +
    • string a = string("123") + string("a");
    • += は慎重に使用
      • a += string ("123") + string ("456"); // "+=" の優先度は "," よりも高い
      • ❓ どれだけの一時変数が定義され、値が何回コピーされたかを想像してみてください
  • ==、>=、<=、>、<
    • 辞書順で判断
  • =
    • str = "123a"
    • 直接代入できる、C 言語のように strcpy を使用する必要はない

キーと値のペア map#

マッピング

• map<string, int> m; // "123" → 456
• メソッド
  • []
    • 代入、アクセス
    • アクセスする key が存在しない場合、自動的に作成され、型のデフォルト値が代入される
    • 隠れたコストがある、底層は赤黒木で、探索効率は O (logN)
  • insert、find、erase
  • count
    • 特定の key がいくつあるかを返す
    • しかし map には重複がないため、0 または 1 を返す
    • key が存在するかどうかを判断するために使用できる
• 底層実装は赤黒木【RBTree】
  • 順序付き構造、map はデフォルトで昇順に並ぶ
  • key がカスタム構造体に対応する場合、小なり演算子をオーバーロードする必要がある
• 拡張
  • multimap
    • 複数の重複したキーを持つことができる
  • unordered_map ❗c++11 で登場
    • 無秩序
    • 底層実装はハッシュテーブルで、探索、挿入効率は O (1)
    • カスタム構造体には手動でハッシュ関数を実装する必要がある
      • 参考C++ STL 無秩序コンテナのカスタムハッシュ関数と比較ルール-C 言語中文网

セット set#

• 重複を排除したり、ソートしたりするために使用できる
• 底層は map と同じ、赤黒木で、必要に応じて「<」をオーバーロードする必要がある
• 拡張
  • multiset
  • unordered_set ❗c++11

ペア pair#

• ペア
• pair<int, int>
  • pair.first 前の要素
  • pair.second 後の要素
• make_pairを使用して一時的なペアを迅速に作成できる

コードデモ#

queue#

• 

• 二種類のデータ型のキュー

• que.empty () と que.size () はどちらも O (1) で、底層にデータ領域が保存されている

• デフォルトの生成コンストラクタ

出力

stack#

• 

• queue との違い：名前、ヘッダーファイル、top () メソッド

出力

vector#

• 

• 配列よりも高機能で、leetcode でよく使用される

• 3 種類の挿入方法

出力

priority_queue#

• 

• カスタム構造型のキューは小なり演算子をオーバーロードすることを忘れないでください

• ❗オーバーロードしているのは小なり演算子ですが、出力は大から小になります！

出力

• 

• 第二部では、大から小に並べる実装を行いましたが、オーバーロードしているのは小なり演算子であり、実装も小なり演算子です

map#

• 

• カスタム構造体に対しては、map は小なり演算子をオーバーロードし、unordered_map はハッシュ関数を定義する必要があります

• 存在しない key にアクセスすると、自動的に作成され、型のデフォルト値が代入されます

出力

練習問題#

HZOJ-383：週末の舞踏会#

サンプル入力

3 5 6

サンプル出力

1 1
2 2
3 3
1 4
2 5
3 1

• 思考
  • キュー
  • デキュー、キューの尾に置く
• コード
  • 
  • キューの基本操作

HZOJ-378：文字列の括弧マッチング 2#

サンプル入力

a(cc[])bbb()@

サンプル出力

YES

• 思考
  • 文字スタック
  • マッチ：YES、例えば ([] )
  • マッチしない：NO
    • 括弧がずれている、例えば ([) ]
    • 右括弧に出会ったとき、スタックが空である、例えば ())
    • 文字列が終了したとき、スタックがまだ空でない、例えば (( {} )
  • 注意：3 つの変数を使って単純にカウントを記録することはできません、なぜなら括弧には順序の問題があるからです、例えば ([)]
• コード
  • 
  • 3 つの不一致の状況に注意
  • マッチするときは左括弧をスタックから取り出す

HZOJ-376：機械翻訳#

サンプル入力

3 7
1 2 1 5 4 4 1

サンプル出力

5

• 思考
  • キュー
  • マーク配列を使用して単語を記録する
    • mark[x] = 1、0
    • データが小さい（文章の長さは 1000 を超えない）、map や set を使用する必要はない
• コード
  • 
  • 単語を保存するキューと単語をマークする配列が重要
  • メモリが満杯の状況に注意

HZOJ-379：倉庫のログ#

サンプル入力

13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2

サンプル出力

2
4
4
1
0

• 思考
  • 0、1、2：入庫、出庫、照会
  • 先入れ後出し：貨物スタックが必要
  • 照会機能（最大値を出力）：最大値を記録するスタックも必要 **【重要】**
  • 注意：各貨物は異なるため、問題が簡略化されている
• コード
  • 
  • 2 つのスタックが必要！
    • この問題では、貨物スタックは必要ないが、理解を助けるために役立つ
    • この問題では、出庫する貨物が何であるかを気にする必要はなく、最大スタックは毎回入庫時に最大値を記録し、繰り返し記録される

HZOJ-382：数を報告する#

サンプル入力

7 3

サンプル出力

4

• 思考
  • ヨセフス環の問題
  • 【本質】キュー：安全な人はキューの尾に、危険な人は弾き出される
  • 終了条件：キューのサイズが 1 のとき
• コード
  • 
  • push の i は番号
  • pop は戻り値がないのか？
    • ここで言及されているコンテナでは、pop、push はどちらも戻り値がない
    • 詳細はpop-cppreference

HZOJ-384：7 を叩く#

サンプル入力

4 3 6

サンプル出力

3

• 思考
  • 上の問題と同じ、注意が必要
  • 違いは
    • 入力：x 番目の人が t から報告を始める
    • 判断条件：7 または 7 の倍数を含む
    • 報告はリセットせず、常に + 1
• コード

HZOJ-385：港#

サンプル入力

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

サンプル出力

3
3
3
4

• 思考
  • 入力：到着時間、人数、各人の国籍
  • キュー +【マーク配列 /map】+ 国の数の変数
    • キューに船や人を保存することができる
      • 船の中の人は固定されていないため、人を保存する方が便利
    • まず時間に基づいて人を減らし、その後人を追加する
    • 国の数：新しい人が来た場合は + 1、最後の人が去った場合は - 1
• コード
  • 
  • 使用するキュー、マーク配列、国の数をカウントする変数が重要
  • スライディングウィンドウのような？少し似ているが、一般的にスライディングウィンドウでは、データはすでに固定されている
  • データ入力を直接コピーし、出力形式が少し奇妙？おそらく改行文字の問題
  • 33 行目で構造体を迅速に定義する：(struct 名){..., ...}
    • 括弧 () を付けなくても問題ありませんが、括弧を付けるとより明確になるかもしれません

HZOJ-569：溶液シミュレーター#

サンプル入力

100 100
2
P 100 0
Z

サンプル出力

200 50.00000
100 100.00000

• 思考
  • 操作を取り消す：スタックを使用！各操作後の質量と濃度を保存する [または] 塩の質量と総質量
  • 化学の知識を振り返る
    • 溶液の構成：塩 + 水
    • 濃度：塩 / (塩 + 水)
    • 質量：塩 + 水
• コード
  • 
  • 塩の質量と総質量を保存することで計算を理解しやすくする
    • どちらも double 型で保存し、出力時に注意して変換する
  • 操作を取り消す：先に減らしてからポップする

LC-232：スタックを使用してキューを実装する#

• 思考
  • 2 つのスタックでキューを実装する
  • 心の中にこのようなプロセスを持つ👇
  • 
• コード

class MyQueue {
public:
    // ここでスタックを宣言しないと、呼び出しが難しい
    stack<int> s1, s2;
    /** ここでデータ構造を初期化します。 */
    MyQueue() {
        // 気にしないでください
    }
    
    /** 要素xをキューの背面にプッシュします。 */
    void push(int x) {
        s1.push(x);
    }
    
    /** キューの前面から要素を削除し、その要素を返します。 */
    int pop() {
        // まずs1スタックの要素をすべてs2スタックに移す
        while (!s1.empty()) {
            // 先にプッシュしてからポップする、順序を逆にしてはいけない
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // この時点でポップする値を取得
        s2.pop();          // ポップする
        // 戻す
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** 前の要素を取得します。 */
    int peek() {
        // s2に移す
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // 一時変数tに値を保存し、戻してから返す
        // 戻す
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** キューが空かどうかを返します。 */
    bool empty() {
        return s1.empty();  // s1を直接判断するだけ
    }
};

/**
 * あなたのMyQueueオブジェクトはこのようにインスタンス化され、呼び出されます：
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

• • 各操作が完了した後、値は常に s1 に保存される
  • スタックの宣言位置：クラスのグローバルに置かないと、他の関数からアクセスできない
    • 初期化関数 MyQueue () に置くと this で呼び出せるか？
    • ❌無理、this は全体のクラスを指し、後でクラスを学ぶときに注意する
  • 【進化】各操作の平均時間計算量を O (1) にすることができるか？言い換えれば、n 個の操作の総時間計算量は O (n) で、たとえその中の 1 つの操作が長い時間を要することがあっても。
    • 鍵は：pop が要素を s1 から s2 に移すとき、戻さないこと
    • こうすることで s2 の順序はキューの出力順序になる
    • pop が s2 が空のときだけ s1 の要素を移し、それ以外は直接 s2 をポップする
    • 参考スタックを使用してキューを実装する - 公式解答- 方法二

LC-225：キューを使用してスタックを実装する#

• 思考
  • 実際には 1 つのキューだけで十分
    • 要素を移動する際、キューの尾に置くだけでよい
      • ①プッシュ時に順序を調整することもできる
      • ②ポップ時に操作することもできる
    • queue.size () で移動の境界を制御する
• コード

class MyStack {
public:
    queue<int> que;
    /** ここでデータ構造を初期化します。 */
    MyStack() {
    }
    
    /** 要素xをスタックにプッシュします。 */
    void push(int x) {
        que.push(x);
        // 前のすべての要素を順次後ろに置く
        for (int i = 1; i < que.size(); i++) {
            que.push(que.front());
            que.pop();
        }
    }
    
    /** スタックのトップの要素を削除し、その要素を返します。 */
    int pop() {
        int t = que.front();
        que.pop();
        return t;
    }
    
    /** トップの要素を取得します。 */
    int top() {
        return que.front();
    }
    
    /** スタックが空かどうかを返します。 */
    bool empty() {
        return que.empty();
    }
};
/**
 * あなたのMyStackオブジェクトはこのようにインスタンス化され、呼び出されます：
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

• • 複雑な操作を push に与え、他の操作はスタックのように使用する

追加の知識点#

• 構造体を迅速に定義する：(struct 名){..., ...}

思考点#

ヒント#

コース速記#