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
• メソッド
  • []
    • 代入、アクセス
    • アクセスするキーが存在しない場合、自動的に作成され、型のデフォルト値が代入される
    • 隠れたコストがある、底層は赤黒木で、探索効率は O (logN)
  • insert、find、erase
  • count
    • 特定のキーがいくつあるかを返す
    • ただし map には重複がないため、0 または 1 を返す
    • キーが存在するかどうかを判断するのに使える
• 底層実装は赤黒木【RBTree】
  • 順序付き構造で、map はデフォルトで昇順に並べられる
  • キーがカスタム構造体の場合、小なり演算子をオーバーロードする必要がある
• 拡張
  • 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 はハッシュ関数を定義する必要がある

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

出力

練習問題#

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：スタックを使ってキューを実装する#

• 思考
  • 二つのスタックでキューを実装する
  • 心の中にこのプロセスを持っている👇
  • 
• コード

class MyQueue {
public:
    // ここでスタックを宣言しないと、呼び出しが難しい
    stack<int> s1, s2;
    /** Initialize your data structure here. */
    MyQueue() {
        // 気にしないで
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // まずs1スタックの要素をすべてs2スタックに移す
        while (!s1.empty()) {
            // 先にpushしてからpop、順序を逆にしてはいけない
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // この時点でpopする値を取り出す
        s2.pop();          // スタックから出す
        // 戻す
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Get the front element. */
    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;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();  // s1を直接判断すればよい
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * 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 を pop すればよい
    • 参考スタックを使ってキューを実装する - 公式解答- 方法二

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

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

class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
        // 前のすべての要素を順に後ろに置く
        for (int i = 1; i < que.size(); i++) {
            que.push(que.front());
            que.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int t = que.front();
        que.pop();
        return t;
    }
    
    /** Get the top element. */
    int top() {
        return que.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

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

追加の知識点#

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

思考点#

Tips#

コース速記#