シーズン３ 全体目次：
↓第9回
これまでに競技プログラミング風 標準C++ライブラリ入門 を2シーズン、8回にわたりお届けしたが、各方面に好評だったので、 さらにおかわり（シーズン3）として【第9回】～【第12回】をお届けする。
標準C++ライブラリを知っていれば比較的簡単な問題をたくさん解いて、 標準C++ライブラリに親しんでいただこうというのが本連載の趣旨だ。
各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。
まず、問題を読んで正しく理解し、テストコード部分をIDEやテキストエディタまたはweb上のコンパイラ
（ideonなど）で保存・ビルド・実行し、
NGが出ないようにテストコードの「ToDo:」部分のコードを完成させてほしい。
「ヒント」「解答例」「解説」はデフォルトでは非表示になっており、中身を読みたい場合は【show】ボタンを押せば表示される。 これらをすぐに読むのではなく、ちゃんと解答を考え、使用する標準ライブラりのクラス・関数をweb検索して勉強し、 コード記述・ビルド・実行してからそれらを読むのを強く推奨する。なにごとも自分で考え、いろいろ試した上で、解答などを見るようにするのが肝要だ。 その方が解答が印象に残り問題解決方法が記憶に定着しやすいのだ。
目次：
引数で、配列アドレス・要素数を受け取り、配列要素が昇順にソート済みかどうかを判定する関数 bool my_is_sorted(const int ar[], int sz) を実装しなさい。
例えば、ar[]: {1, 1, 2, 5, 100}、sz: 5 が渡された場合は true を、ar[]: {1, 5, 2, 1, 100}、sz: 5 が渡された場合は false を返す。
#include <iostream> // 標準入出力ライブラリ
#include <algorithm>
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);
}
bool my_is_sorted(const int ar[], int sz) { // ar: 配列アドレス、sz: 要素数
return true; // ToDo: 標準関数を使い、ここを書き換えて、ar[] の要素が昇順ソート済みかどうかを返す
}
int main() {
const int ar1[] = {1, 1, 2, 5, 100};
const int SZ1 = sizeof(ar1, sizeof(int));
DO_TEST( my_is_sorted(ar1, SZ1) );
const int ar2[] = {1, 5, 2, 1, 100};
const int SZ2 = sizeof(ar2, sizeof(int));
DO_TEST( !my_is_sorted(ar2, SZ2) );
cout << "\nGood Job!\n";
return 0;
}
bool my_is_sorted(const int ar[], int sz) { // ar: 配列アドレス、sz: 要素数
return is_sorted(ar, ar + sz); // [ar, ar+sz) がソート済みか？
}
指定範囲が昇順ソート済みかどうかを判定するには std::is_sorted(first, last) を使うだけだ。 本問題では配列要素を判定するので、is_sorted(ar, ar+sz) を呼ぶだけだ。
ちなみに、第3引数で要素の順序を判定する関数オブジェクトを指定可能なので、 is_sorted(ar, ar+sz, std::greater()) とすれば、指定範囲が降順ソートされているかどうかを判定できるぞ。
X軸方向が実数、Y軸方向が虚数の複素平面上で、引数で与えられた複素数と原点を結んだ直線とX軸との角度
（反時計回りがプラス）を返す関数
int angle(const complex<double>& c) を実装しなさい。
なお、角度の単位は度（degree）とする。
例えば、実数1, 虚数1 が与えられた場合は 45 を返す。
#include <iostream> // 標準入出力ライブラリ
#include <complex>
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);
}
#define PI 3.1415926535
int angle(const complex<double>& c) {
return 0; // ToDo: 標準ライブラリの関数を使い、複素数cのX軸からの角度を返す
}
int main() {
DO_TEST( angle(complex<double>(1, 0)) == 0 );
DO_TEST( angle(complex<double>(0, 1)) == 90 );
cout << "\nGood Job!\n";
return 0;
}
int angle(const complex<double>& c) {
return (int)(arg<double>(c) * 180 / PI); // arg() で角度（ラジアン）を求め、度（degree）に変換
}
複素数cのX軸からの角度を求めるには T std::arg<T>(const complex<T>&) を使う。
T は複素数要素の型で、本問題の場合は double だ。
std::arg() の返す値の単位はラジアンで、本問題では度（degree）を返すという仕様なので、返値に *180/PI を適用させて、度に変換している。
const vector<int>& 型の引数 v1, v2 の2つを受け取り、それらの内積（Σv1[i]*v2[i]）を返す関数 int my_inner_product(const vector<int>& v1, const vector<int>& v2) を実装しなさい。
ただし、v1, v2 のサイズが異なる場合は、小さい方のサイズ分の内積を計算するものとする。
#include <iostream> // 標準入出力ライブラリ
#include <numeric>
#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);
}
int my_inner_product(const vector<int>& v1, const vector<int>& v2) {
return 0; // ToDo: 標準関数を使い、ここを書き換えて、v1 と v2 の内積を返す
}
int main() {
vector<int> v1 = {1, 2, 3};
vector<int> v2 = {7, 4, 3};
DO_TEST( my_inner_product(v1, v2) == 24 );
v1 = { 1, 2, 3, 4 };
v2 = { 7, 6 };
DO_TEST(my_inner_product(v1, v2) == 19);
cout << "\nGood Job!\n";
return 0;
}
int my_inner_product(const vector<int>& v1, const vector<int>& v2) {
int sz = min(v1.size(), v2.size()); // 小さい方のサイズに合わせる
return inner_product(v1.begin(), v1.begin() + sz, v2.begin(), 0); // 内積計算
}
内積を計算するには、std::inner_product(first1, last1, first2, init) を使う。
first1, last1 は内積を計算する片方の範囲で、first2 はもう片方の先頭（イテレータまたはアドレス）だ。
本問題の場合は、コンテナクラスが渡されるので、イテレータの begin(), end() を使う。
v1, v2 のサイズが異なる場合は、小さい方のサイズに合わせるという仕様なので、それぞれのサイズの小さい方を sz に設定し、
v1.begin(), v1.begin() + sz で範囲を指定している。残りの引数は v2.begin() と初期値に 0 を指定している。
↓第10回
今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。
問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック！
目次：
int型引数2つを取り、その和を返す関数オブジェクトを返す関数 function<int (int, int)> addFunc() を実装しなさい。
例えば、「auto f = addFunc();」で加算関数オブジェクトを作成後に、f(1,2) を実行すると 3 を返す。
#include <iostream> // 標準入出力ライブラリ
#include <functional>
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);
}
function<int (int, int)> addFunc() {
return nullptr; // ToDo: 標準関数を使い、ここを書き換え、加算関数オブジェクトを返す
}
int main() {
auto f = addFunc();
DO_TEST(f != nullptr);
DO_TEST( f(123, 456) == 579);
cout << "\nGood Job!\n";
return 0;
}
function<int(int, int)> addFunc() {
return [](int lhs, int rhs) { return lhs + rhs; }; // 加算を行う関数オブジェクト（ラムダ式）を返す
}
関数オブジェクトを生成するにはラムダ式を使うのが簡単だ。
ラムダ式の構文は「[](仮引数宣言）{ 関数本体定義 }」だ。
カギ括弧（[]）中にはキャプチャする変数を指定可能だが、本問題では使用しないので空とする。
丸括弧中には、通常の関数定義と同じ用に仮引数リストを記述する。本問題の場合は、加算を行う２つの仮引数を記述する。
最後に、にょろ括弧（{}）中に、関数の本体を記述する。本問題の場合は、仮引数2つの和を返すので「{ return lhs + rhs; }」と記述する。
関数オブジェクトの型は「function<関数型指定>」と記述する。 関数型は「返値型(仮引数型, ...)」と記述するんだぞ。
string型第1引数strのix番目からlen文字を文字列として返す関数 string my_mid(const string& str, int ix, int len) を実装しなさい。
先頭文字からの場合、ix: 0 とする。ix がマイナスの値の場合は、末尾から前に向かってlen文字を文字列として返すものとする。
例えば my_mid("abcde", 0, 3) は "abc" を、my_mid("abcde", -1, 3) は "cde" を返す。
my_mid("abc", 5, 2) や my_mid("abc", -5, 2) の様に、ix が範囲外の場合は "" を返すものとする。
また、len が長すぎる場合は、有効な長さまでの文字列を返すものとする。例えば my_mid("abc", 2, 3) は "c" を返す。
#include <iostream> // 標準入出力ライブラリ
#include <string>
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 my_mid(const string& str, int ix, int len) {
// ToDo: 標準関数を使い、ここを書き換えて、str の ix 番目から len 文字を返す
// ix がマイナス値の場合は末尾からix文字目から、先頭に向かって len 文字を返す
return "";
}
int main() {
DO_TEST( my_mid("123", 1, 1) == "2" );
DO_TEST( my_mid("abcde", -1, 2) == "de" );
DO_TEST( my_mid("123", 5, 1) == "" );
DO_TEST( my_mid("123", -5, 1) == "" );
DO_TEST( my_mid("123", 2, 3) == "3" );
DO_TEST(my_mid("123", -3, 3) == "1");
cout << "\nGood Job!\n";
return 0;
}
string my_mid(const string& str, int ix, int len) {
if (ix >= 0) { // ix が0以上の場合は、substr() をコールするだけ
if (ix >= str.size()) return ""; // ix 範囲チェック
// str.substr(ix, len) はlenが大きすぎる場合に対応しているので、処理不要
return str.substr(ix, len);
}
else { // ix がマイナスの場合は、末尾から文字列を取り出す
if (-ix > str.size()) return ""; // ix 範囲チェック
int first = str.size() + ix + 1 - len; // 取り出し開始位置
if (first < 0) { // 取り出し開始位置がマイナスの場合
len += first; // len を減らし
first = 0; // 文字列先頭から取り出す
}
return str.substr(first, len);
}
}
string から途中の文字列を取り出すには substr(ix, len) を使う。ix は取り出し開始位置、len は文字数だ。
substr() はixがマイナスの場合には対応していないので、まずはif文でixが0以上かどうかを判定し、
そうであればsubstr()をコールする。
ixがマイナスだった場合は、取り出す先頭位置を計算し、そこからlen文字を取り出す。
要素数52の（トランプの）カードデッキ配列を引数で受け取り、要素をシャフル（カード順序をランダムにする）する関数 void my_shuffle(vector<int>& deck) を実装しなさい。
なお、各カードの値は 0～51 で、値を13で割った商はクローバ・スペード・ハート・ダイヤモンドを表し、 値を13で割った剰余はカードの数字-1を表す（0-12 が A, 2,... Q, K を表す）ものとする。 具体的には、値0はクラブのエースを、値14はスペードの2を、値51はダイヤモンドのKを表す。
また、シャフルするために乱数を使用する場合は、テストコードで定義している g_mt() を使用しなさい。
#include <iostream> // 標準入出力ライブラリ
#include <vector>
#include <random>
using namespace std; // std 名前空間使用
std::random_device g_rnd; // 非決定的な乱数生成器
std::mt19937 g_mt(g_rnd()); // メルセンヌ・ツイスタの32ビット版乱数生成関数
#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);
}
const int N_CARD = 52; // 13*4, カード種類数
bool isShuffled(const vector<int>& deck) { // カードがシャフルされているか判定
vector<int> vc(52, 0);
int mx = 0;
for(int i = 1; i != deck.size(); ++i) mx = max(mx, vc[abs(deck[i-1] - deck[i])] += 1);
return mx < 8;
}
void my_shuffle(vector<int>& deck) {
// ToDo: 標準関数を使い、ここを書き換えて、deck の要素をシャフルする
}
int main() {
vector<int> deck;
for(int i = 0; i != N_CARD; ++i) deck.push_back(i);
DO_TEST( !isShuffled(deck) );
my_shuffle(deck);
DO_TEST( isShuffled(deck) );
cout << "\nGood Job!\n";
return 0;
}
void my_shuffle(vector<int>& deck) {
shuffle(deck.begin(), deck.end(), g_mt); // 乱数関数 g_mt を使って、指定範囲をシャフル
}
指定範囲をシャフルしたい場合は std::shuffle(first, last, randFunc) を使う。
first, last はシャフルしたい範囲で、randFunc はシャフル時に使用する乱数関数だ。
本問題では、コンテナクラスの要素をシャフルするので、begin(), end() で範囲を指定する。
乱数関数はテストコードで定義しているメルセンヌ・ツイスタアルゴリズムによる乱数生成関数の g_mt を使用する。
なので、「shuffle(deck.begin(), deck.end(), g_mt);」をコールするだけで、範囲をシャフルしてくれるぞ。
ちなみに、シャフル処理を自前で実装するには、以下のようにするとよい。
void my_shuffle(vector& deck) { for (int i = 0; i != deck.size() - 1; ++i) { int k = g_mt() % (deck.size() - i) + i; // deck[i] と交換する相手を乱数で決める swap(deck[i], deck[k]); // 交換 } }
最初は52枚の中からランダムに1枚を選び、それと1枚目を交換する。
次は2枚目からの51枚目の中からランダムに1枚を選び、それと2枚目を交換する。
これを51枚目まで繰り返すとカードがシャフルされたことになる。
このアルゴリズムは人間が行うシャフルとは異なるが、51回の処理で完全にランダムにシャフルすることができる。
↓第11回
今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。
問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック！
目次：
引数で渡された 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;
}
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;
}
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;
}
// マルチスレッドで 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() で関数が返す値を受け取ることができる。
↓第12回
今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。
問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック！
目次：
第1・2引数に、要素が昇順ソートされた const vector<int>& 型の lst1, lst2 が渡され、 その昇順和集合（重複要素を削除し、マージしたもの）を vector<int>& 型の第3引数に格納する関数 void my_set_union(const vector<int>& lst1, const vector<int>& lst2, vector<int>& u) を実装しなさい。
例えば、{1, 2, 3, 5, 9} と {2, 3, 4, 9} が渡された場合は、昇順和集合の {1, 2, 3, 4, 5, 9} を第3引数に設定する。
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace 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 my_set_union(const vector<int>& lst1, const vector<int>& lst2, vector<int>& u) {
// ToDo: 標準ライブラリの関数を使い、lst1, lst2 の昇順和集合を u に格納する
}
int main() {
vector<int> lst1 = {1, 2, 3, 5, 9};
vector<int> lst2 = {2, 3, 4, 9};
vector<int> u;
my_set_union(lst1, lst2, u);
DO_TEST( u == vector<int>({1, 2, 3, 4, 5, 9}) );
cout << "\nGood Job!\n";
return 0;
}
void my_set_union(const vector<int>& lst1, const vector<int>& lst2, vector<int>& u) {
u.resize(lst1.size() + lst2.size()); // lst1, lst2 の合計サイズ分の領域を確保しておく
auto itr = set_union(lst1.begin(), lst1.end(), // 和集合要素を取り出す範囲その1
lst2.begin(), lst2.end(), // 和集合要素を取り出す範囲その2
u.begin()); // u の先頭イテレータ
u.resize(itr - u.begin()); // 不要な要素を削除
//u.erase(itr, u.end()); // 不要な要素を削除
}
昇順の和集合要素を取り出すには Iterator std::set_union(first1, last1, first2, last2, iout) を使う。 first1, last1, first2, last2 は和集合要素を取り出すデータの範囲だ。具体的にはコンテナクラスのイテレータか配列アドレスを指定する。 最後の iout 引数は和集合要素を格納する場所位置へのイテレータだ。コンテナクラスのイテレータか配列アドレスを指定可能だが、 領域を自動的には確保してくれないので、十分な領域をあらかじめ確保しておく必要がある。 そのためには、解答例のように、2つのコンテナオブジェクトサイズのサイズ合計値を確保しておけばよい。 最後に、set_union() が返すイテレータを使い、和集合要素を格納する u を resize() し、余分な領域を削除しておく。 削除方法としては、回答例最後にコメントアウトしているように、「u.erase(itr, u.end())」と記述してもよい。 人によってはこの方がわかりやすいかもしれない。
テストコードの ToDo 部分を修正し、文字列をキーとし、int型数値を値として保持する
unordered_map型辞書オブジェクトを定義し、
その辞書にキー・値を登録する関数 void doInsert(const string& key, int value)、
辞書を検索し、キーに対応する値を返す関数 int getValue(const string& key) を実装しなさい。
ただし、辞書にキーが登録されていない場合は -1 を返すものとする。
#include <iostream> // 標準入出力ライブラリ
#include <string>
#include <unordered_map>
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);
}
// ToDo: 標準C++ライブラリのクラスを使って、辞書オブジェクトをここで定義
void doInsert(const string& key, int value) {
// ToDo: 標準関数を使い、ここを書き換えて、辞書に (key, value) を登録
}
int getValue(const string& key) {
// ToDo: 標準関数を使い、ここを書き換えて、辞書中の key の値を返す
// 辞書に key が登録されていない場合は -1 を返すものとする
return 0;
}
int main() {
doInsert("abc", 1);
doInsert("xyzzz", 2);
doInsert("bc", 3);
doInsert("bc", 4); // 上書きするものとする
DO_TEST( getValue("abc") == 1);
DO_TEST( getValue("ab") == -1);
DO_TEST( getValue("bc") == 4);
cout << "\nGood Job!\n";
return 0;
}
unordered_map<string, int> g_dict; // 辞書オブジェクト定義
void doInsert(const string& key, int value) {
g_dict[key] = value; // 辞書に (key, value) を登録
}
int getValue(const string& key) {
if (g_dict.find(key) == g_dict.end())
return - 1; // 辞書に key が登録されていない場合
return g_dict[key]; // key に対応する値を返す
}
回答例では std::map ではなく、std::unordered_map を使用している。前者はデータ構造として赤黒木を使用するが、 後者はハッシュを使用するので、より高速だ（挿入・参照の処理時間：前者は O(log N) だが、後者は O(1)）。
まず、「unordered_map<string, int> g_dict;」で辞書オブジェクトを定義する。 テンプレート引数で string, int を指定しているので、文字列をキーとし、整数値を保持する辞書となる。
辞書にキー・値を追加するには、回答例のように「g_dict[キー] = 値;」と記述するだけだ。 すでにキー・値が登録されている場合は上書きされる。
辞書からキーを検索するには find() メンバ関数を使う。辞書に登録されていない場合は、end() が返されるので、仕様どおり -1 を返す。 辞書に登録済みの場合は g_dict[キー] で値を参照できるので、「return g_dict[キー];」と記述するだけだ。
第1引数でconst char*型被検索文字列を、第2引数でconst char*型正規表現文字列を受け取り、
それらが正規表現が被検索文字列に含まれるかどうかを返す関数
bool my_regex_find(const char* str, const char* re, int& ix, int& sz) を実装しなさい。
なお、正規表現が被検索文字列に含まれる場合は、第3引数にその位置を、第4引数にマッチした文字数を設定するものとする。
例えば、my_regex_find("acb", "[a-c]+", ix, sz) は true を返し、ix:0, sz:3 となる。
#include <iostream>
#include <string>
#include <regex>
using namespace 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);
}
bool my_regex_find(const char* str, const char* re, int& ix, int& sz) {
// ToDo: 標準ライブラリの関数を使い、正規表現に最初にマッチする位置を ix に、長さを sz に設定
// ToDo: マッチする場合は true を、しない場合は false を返すコードを記述
return true;
}
int main() {
int ix, sz;
DO_TEST( my_regex_find("123", "[0-9]+", ix, sz) && ix == 0 && sz == 3 );
DO_TEST( my_regex_find("-123-", "[0-9]+", ix, sz) && ix == 1 && sz == 3 );
DO_TEST( my_regex_find("--123123--123--", "[0-9]+", ix, sz) && ix == 2 && sz == 6 );
DO_TEST( my_regex_find("--123--ax123--", "[a-z]+[0-9]+", ix, sz) && ix == 7 && sz == 5 );
cout << "\nGood Job!\n";
return 0;
}
bool my_regex_find(const char* str, const char* re, int& ix, int& sz) {
// match_results result;
cmatch result; // 検索結果格納用オブジェクト
if (!regex_search(str, result, regex(re))) // 正規表現が str の一部とマッチしたか？
false; // 非マッチの場合
ix = result[0].first - str; // マッチ開始位置
sz = result[0].second - result[0].first; // マッチした文字数
return true;
}
被検索文字列から正規表現にマッチする部分があるかどうかを判定するには regex_search(str, result, re) 関数を使う。
str は被検索文字列のアドレス、result は検索結果を格納するオブジェクト（詳しくは後術）、re は regex 型の正規表現オブジェクトだ。
result は match_results<T> 型で、本問題の場合は char へのポインタなので cmatch を使うぞ。
cmatch は「typedef match_results
cmatch オブジェクトには検索結果が格納される。result.size() で何箇所マッチしたかがわかり、
result[0] で最初にマッチした文字列の位置情報などを参照できる。result[0].first がマッチ開始位置、result[0].second がマッチ末尾位置+1だ。
これらの他にもいろいろな情報を保持している。詳しくはぐぐって調べてほしい。
標準C++ライブラリ入門向けの競技プログラミング風問題のさらにおかわりを12問解いていただいた。
標準C++ライブラリを知って、使いこなせれば、いろいろなコードを楽に、かつ高品質に書けることを実感していただけたものと思っている。
本連載を機に標準C++ライブラリに興味を持っていただき、使いこなせるようになっていただけたら幸いだ。