Developer

競技プログラミング風 標準C++ライブラリ入門【第11回】
2020.12.03
Lv3

競技プログラミング風 標準C++ライブラリ入門【第11回】

競技プログラミング風 標準C++ライブラリ入門【第11回】

今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。

問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック!

目次

Nの倍数を0に置換(難易度:★★☆☆☆)

問題

引数で渡された vector<int>& lst の各要素が第2引数Nの倍数の場合は0に置換する関数 void replaceNxTo0(vector<int>& lst, int N) を実装しなさい

例えば、lst: {3, 1, 4, 1, 5, 9, 2, 6}, N: 2 の場合、lst は {3, 1, 0, 1, 5, 9, 0, 0} となる。

ただし、N>0 とし、Nが0以下の場合は、何も処理を行わないものとする。

#include <iostream>       //  標準入出力ライブラリ
#include <algorithm>
#include <vector>
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
void replaceNxTo0(vector<int>& lst, int N) {
    //  ToDo: 標準関数を使い、ここを書き換えて、Nの倍数のlst要素を0に置換する
}
int main() {
    vector<int> lst1 = {3, 1, 4, 1, 5, 9, 2, 6};
    replaceNxTo0(lst1, 2);
    DO_TEST( lst1 == vector<int>({3, 1, 0, 1, 5, 9, 0, 0}) );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・条件付き置換を行うには std::replace_if(first, last, pred, val) を使うんだぞ。
・first, last は置換を行う範囲だ。
・pred は条件を表す関数オブジェクト(通常はラムダ式)だぞ。
・キャプチャの説明
・val は置換する値だ。

解答例
void replaceNxTo0(vector<int>& lst, int N) {
    if( N <= 0 ) return;    //  N が範囲外の場合
    // 要素が N の倍数であれば、0 に置換
    replace_if(lst.begin(), lst.end(), [N](int a) { return a % N == 0; }, 0);
}
解説

条件付き置換を行うには std::replace_if(first, last, pred, val) を使う。
first, last は置換を行う範囲だ。本問題ではコンテナの内容を置換するので、begin(), end() を使用する。
3番目の引数は条件を表す関数オブジェクトだ。本問題の場合は、N の倍数かどうかなので、 回答例の様にラムダ式を使えば簡単に記述できるぞ。
最後の引数は置換する値だ。本問題では0に置換なので0を指定するだけだ。

スマートポインタ(難易度:★★☆☆☆)

問題

テストコードの「ここから」「ここまで」の部分を修正して、lst を resize() で縮小するとオブジェクトが自動的に破棄されるようにしなさい。

テストコードで定義している CTest クラスは、コンストラクタがコールされるとカウンタをインクリメントし、 デストラクタがコールされるとカウンタをデクリメントするようになっている。

#include <iostream>       //  標準入出力ライブラリ
#include <vector>
//#include <memory>
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if (b) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
int g_objCount = 0;     //  オブジェクト数
struct CTest {
    CTest() { ++g_objCount; }       //  オブジェクト数をインクリメント
    ~CTest() { --g_objCount; }      //  オブジェクト数をデクリメント
};
int main() {
    const int N_OBJECT = 10;
    const int N_RESIZED = 7;
//-----ここから-----
    //  ToDo: 以下を書き換え、lst を resize() で縮小するとオブジェクトが自動的に破棄されるよう修正
    vector<CTest*> lst;
    for (int i = 0; i != N_OBJECT; ++i)
        lst.push_back(new CTest);
//-----ここまで-----
    DO_TEST(g_objCount == N_OBJECT);
    lst.resize(N_RESIZED);      //  lst を縮小
    DO_TEST(g_objCount == N_RESIZED);
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・new したメモリを自動解放したい場合はスマートポインタを使うといいぞ。
・スマートポインタにはいくつかの種類があるが、メモリを共有しない場合は std::unique_ptr<T> を使うといいぞ。
・unique_ptr オブジェクトを作成するときは、unique_ptr<型>(new 型) と記述するんだぞ。

解答例
    vector<unique_ptr<CTest>> lst;      //  CTest オブジェクトを指すスマートポインタの動的配列
    for (int i = 0; i != N_OBJECT; ++i)
        lst.push_back(unique_ptr<CTest>(new CTest));      //  CTest オブジェクトを指すスマートポインタを追加
解説

new したメモリを自動解放したい場合はスマートポインタを使うとよい。
本問題の場合は、メモリを共有したりはしないので、std::unique_ptr<T> を使うとよい。

テストコードでは「lst.push_back(new CTest);」と記述していたので、動的配列には CTest オブジェクトへのポインタが格納される。 したがって、「lst.resize(N_RESIZED)」で配列が縮小されても、ポインタが消えるだけで、ポインタが指している先のオブジェクトは破棄されない。

それに対して、回答例のように unique_ptr を使用した場合、動的配列には unique_ptr オブジェクトが格納されるので、 配列が縮小された場合は、unique_ptr オブジェクトが破棄され、 その時自動的に unique_ptr が指している CTest オブジェクトが破棄されるという寸法だ (unique_ptr オブジェクトが破棄されない限り、それが指している CTest オブジェクトは破棄されないことに注意)。

ちなみに、スマートポインタには unique_ptr 以外にも shared_ptr, weak_ptr がある。 shared_ptr はメモリを共有する場合、weak_ptr はメモリを所有しない場合に使用する。 ここでは詳しく説明しないので、各自ググったりして勉強してほしい。 また、以前から auto_ptr というのもあったのだが、これはコピーした場合に動作不良になる場合があるので、 非推奨または環境によっては廃止になっている。

マルチスレッド(難易度:★★☆☆☆)

問題

テストコードの ToDo 部分を書き換え、複数の関数 foo(char) が同時並行的に実行されるようにしなさい。

テストコードをそのまま実行すると、foo(‘A’) で「AAAAAAAAAA」が、foo(‘Z’) で「ZZZZZZZZZZ」が表示されるので、 トータルで「AAAAAAAAAAZZZZZZZZZZ」と表示され。 それらを同時並行的に実行すると「AZAZAZAZAZAZAZAZAZAZ」のように ‘A’ と ‘Z’ が混ざって表示される (ただし、このようにキレイに交互に混ざるとは限らない)。

#include <iostream>       //  標準入出力ライブラリ
#include <thread>
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
string g_out;
void foo(char ch) {
    for(int i = 0; i != 10; ++i) {
        g_out += ch;
        cout << ch;
        std::this_thread::sleep_for(std::chrono::milliseconds(100));     //  100ミリ秒ウェイト
    }
}
int main() {
//-----ここから-----
    //  ToDo: マルチスレッドで foo('A'), foo('Z') を起動するよう修正
    foo('A');
    foo('Z');
    //  ToDo: マルチスレッドで起動された foo('A'), foo('Z') が終了するまで待つよう修正
//-----ここまで-----
    DO_TEST(g_out != "AAAAAAAAAAZZZZZZZZZZ");
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・関数を別スレッドで起動するには thread(関数, 引数…) を使うぞ。
・スレッドの終了を待つには thread の join() メンバ関数を使うぞ。

解答例
    //  マルチスレッドで foo('A'), foo('Z') を起動
    thread f1(foo, 'A');
    thread f2(foo, 'Z');
    //  マルチスレッドで起動された foo('A'), foo('Z') が終了するまで待つ
    f1.join();
    f2.join();
解説

関数を別スレッドで起動するには thread(関数、引数…) を使う。 「thread f1(foo, ‘A’);」「thread f2(foo, ‘Z’);」と記述すれば、foo(‘A’) と foo(‘Z’) が別スレッドで起動され、 同時並行的に実行される。
それぞれのスレッドが終了するのを待つには「f1.join();」「f2.join();」と記述するだけだ。

ちなみに、本問題では値を返さない関数を別スレッドで起動したが、なんらかの計算をスレッドを分けて行い、 その結果を利用するには「auto f = std::async(フラグ, 関数, 引数…)」で別スレッドを起動し、 f.get() で関数が返す値を受け取ることができる。

関連記事

投稿が見つかりません。

筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。