シーズン1(?)リンク:
↓第1回
標準C++ライブラリとは、C++で標準的に用意されているクラス・関数ライブラリのことだ。 ヘッダをインクルードするだけですぐに使える便利なクラス・関数が多数用意されている。 同じようなものを自作しようとすると、そこそこの工数も必要だし、高品質(バグがなく高速)にするのは大変だ。 なので、これを使わないC++erは人生をずいぶん損していることになる。
合計4回の本連載では、標準C++ライブラリの競技プログラミング風問題を全部で12問用意した。 問題難易度は比較的簡単なものなので、気軽にどんどん解けるものばかりだ。 正確に言えば、標準C++ライブラリを使用すれば簡単という問題なので、 標準C++ライブラリをマスターしようという動機づけになることを意図している。 競技プログラミング風の問題を多数解くことで、標準C++ライブラリの基本を少しでも知ってもらいたいというわけだ。
各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。
まず、問題を読んで正しく理解し、テストコード部分をIDEやテキストエディタまたはweb上のコンパイラ
(ideonなど)で保存・ビルド・実行し、
NGが出ないようにテストコードの「ToDo:」部分のコードを完成させてほしい。
「ヒント」「解答例」「解説」はデフォルトでは非表示になっており、中身を読みたい場合は【show】ボタンを押せば表示される。 これらをすぐに読むのではなく、ちゃんと解答を考え、使用する標準ライブラりのクラス・関数をweb検索して勉強し、 コード記述・ビルド・実行してからそれらを読むのを強く推奨する。なにごとも自分で考え、いろいろ試した上で、解答などを見るようにするのが肝要だ。 その方が解答が印象に残り問題解決方法が記憶に定着しやすいのだ。
目次:
文字列 "Hello, World." を返す関数 string hello() を実装しなさい。
#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 hello() { return ""; // ToDo: ここを書き換えて "Hello, World." を返す } int main() { DO_TEST( hello() == "Hello, World." ); cout << "\nGood Job!\n"; return 0; }
string hello() { return "Hello, World."; // "Hello, World." を返す //return string("Hello, World."); // 明示的に string オブジェクトを返す }
string 型関数で、特定の文字列を返したい場合は、単に「return "文字列";」と記述すればよい。
string 型を強調するために「return string("文字列");」と書いてもいいのだが、
単に文字列リテラルを書いても、暗黙的な型変換により自動的に string 型に変換される。
なお、念のために解説しておくと、std::string のように毎回 std:: を書くのは個人的に面倒なので、
テストコードのように「using namespace std;」と書いておき、「std::」の記述を省略するようにしている。
これは好みの問題だと思うので、標準クラス名・関数名には必ず「std::」を前置してもよい。お好きにどうぞ。
参照引数で渡された動的配列に、{3, 1, 4, 1, 5} の要素を設定する関数 void setPI(vector<int>& v) を実装しなさい。
#include <iostream> // 標準入出力ライブラリ #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 setPI(vector<int>& v) { // ToDo: ここにコードを追加し v の要素を {3, 1, 4, 1, 5} に設定する } int main() { vector<int> v; setPI(v); DO_TEST( v.size() == 5 ); DO_TEST( v[0] == 3 ); DO_TEST( v[1] == 1 ); DO_TEST( v[2] == 4 ); DO_TEST( v[3] == 1 ); DO_TEST( v[4] == 5 ); cout << "\nGood Job!\n"; return 0; }
void setPI(vector<int>& v) { // v の要素を {3, 1, 4, 1, 5} に設定 v = {3, 1, 4, 1, 5}; //v = vector<int>{3, 1, 4, 1, 5}; }
「vector<int>& v」の要素全体を設定するには「v = vector<int>{3, 1, 4, 1, 5};」と記述すればよい。 または、解答例のように単に「v = {3, 1, 4, 1, 5};」と記述してもよい。
あえて各要素を順に設定したい場合は以下のように記述する。
v.clear(); // v の要素をクリア v.push_back(3); // 末尾に 3 を追加 v.push_back(1); v.push_back(4); v.push_back(1); v.push_back(5);
別の方法として、以下のように記述してもよい。
v.resize(5); v[0] = 3; v[1] = 1; v[2] = 4; v[3] = 1; v[4] = 5;
vector は最もよく使われるコンテナクラスだ。高速で使い勝手がよく大変便利なので、 「C++ 動的配列クラス std::vector 入門」 などを読んで、 ぜひともマスターしていただきたい。;^p
引数で渡された vector<int>型への参照の各要素に第2引数を加える関数 void geta(vector<int>& v, int a) を実装しなさい。
例えば、v に {1, 2, 3}, a に 1 が渡された場合、v の内容は {2, 3, 4} となる。
※ オーバーフローは考慮しなくてよいものとする。
#include <iostream> #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 geta(vector<int>& v, int a) { // ToDo: ここにコードを追加し v の各要素に a を加える } int main() { vector<int> v1 = {1, 2, 3}; geta(v1, 1); DO_TEST( v1 == vector<int>({2, 3, 4}) ); vector<int> v2 = {1, 2, 3, 4}; geta(v2, -2); DO_TEST( v2 == vector<int>({-1, 0, 1, 2}) ); cout << "\nGood Job!\n"; return 0; } // ※ vector<int>({1,2,3}) という書き方は まみむめも氏(https://twitter.com/hu_123456)にご教授いただきました。さんくす
void geta(vector<int>& v, int a) { // v の各要素に a を加える for(int i = 0; i != v.size(); ++i) v[i] += a; }
↑第1回、↓第2回
今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。
問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック!
目次:
int[] 型のar, 要素数szを受け取り、要素を昇順にソートする関数 void sortArray(int ar[], int sz) を実装しなさい。
例えば、{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5} が渡された場合は、結果は {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9} となる。
#include <iostream> #include <vector> #include <algorithm> 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 sortArray(int ar[], int sz) { // ToDo: 標準ライブラリの関数を使って、サイズ sz の配列 ar をソートする } int main() { int ar0[] = {123}; const int sz0 = sizeof(ar0)/sizeof(int); sortArray(ar0, sz0); DO_TEST( vector<int>(ar0, ar0+sz0) == vector<int>({123}) ); int ar[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; const int sz = sizeof(ar)/sizeof(int); sortArray(ar, sz); DO_TEST( vector<int>(ar, ar+sz) == vector<int>({1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}) ); cout << "\nGood Job!\n"; return 0; }
void sortArray(int ar[], int sz) { sort(ar, ar+sz); // サイズ sz の配列 ar をソート }
sort(first, last) 関数を使うと、データを簡単に昇順ソートすることができる。
使い方は簡単で、第1・2引数に配列アドレス・配列末尾アドレス+1を渡すだけだ。
配列末尾アドレス+1は配列先頭アドレス+要素数で計算できるぞ。
または、sort(&ar[0], &ar[sz]); と書いてもいいぞ。
引数で渡された文字列strの文字順序を逆転した文字列を返す関数 string my_reverse(const string &str) を実装しなさい。
例えば、my_reverse("abcxyz") は "zyxcba" を返す。
#include <iostream> #include <algorithm> #include <string> 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); } string my_reverse(const string& str) { return ""; // ToDo: 標準ライブラリの関数を使い、str を反転した文字列を返すようにする } int main() { DO_TEST( my_reverse("") == "" ); DO_TEST( my_reverse("a") == "a" ); DO_TEST( my_reverse("abc") == "cba" ); DO_TEST( my_reverse("abcd") == "dcba" ); cout << "\nGood Job!\n"; return 0; }
string my_reverse(const string& str) { string s = str; // 作業用文字列にコピー reverse(s.begin(), s.end()); // s の文字を順序反転 return s; }
コンテナクラスの要素を逆順にするには、 reverse(first, last) 関数を使う。 解答例の reverse() 関数は、引数が const string& で、string を返すので、最初に作業用文字列にコピーし、 標準関数の reverse(first, last) をコールして要素順序を反転させ、作業用文字列を値として返す。
文字列str、ローテイトする文字数Nを引数で渡され、strを左にN文字ローテイトしたものを返す関数 string my_rotate(string str, int N) を実装しなさい。
例えば、my_rotate("abcxyz", 2) は "cxyzab" を返す。
#include <iostream> #include <algorithm> #include <string> 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); } string my_rotate(const string& str, int n) { return ""; // ToDo: 標準ライブラリの関数を使い、str をn文字左にローテイトした文字列を返す } int main() { DO_TEST( my_rotate("", 0) == "" ); DO_TEST( my_rotate("abc", 0) == "abc" ); DO_TEST( my_rotate("abc", 1) == "bca" ); DO_TEST( my_rotate("abc", 2) == "cab"); cout << "\nGood Job!\n"; return 0; }
string my_rotate(const string& str, int n) { if( n < 0 || n >= str.size() ) return str; // 範囲チェック string s = str; // 作業用文字列にコピー rotate(s.begin(), s.begin() + n, s.end()); // s をn文字ローテイト return s; }
コンテナの要素をローテイトするには rotate(first, middle, last) 関数を使う。
first, last はコンテナの先頭, 末尾+1だ。そして middle はローテイト後の先頭になるデータ位置を示す。
例えば、v が vector の場合は「rotate(v.begin(), v.begin()+n, v.end())」をコールすると、
左にn個だけローテイトされるぞ。
↑第2回、↓第3回
今回も、標準C++ライブラリ入門のための競技プログラミング風問題を解いて、標準C++ライブラリに親しんでいただきたい。
問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させて、「Good Job!」を表示させていただきたい。グッドラック!
目次:
const vector<int>参照型のv, カウントする要素の値 d を受け取り、d に等しい要素の数を返す関数 int my_count(const vector<int>& v, int d) を実装しなさい。
例えば {0, 3, 2, 3} と 3 が渡されると 2 を、{9, 8} と 9 が渡されると 1 を返す。
#include <iostream> #include <algorithm> #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); } int my_count(const vector<int>& v, int d) { return 0; // ToDo: 標準ライブラリの関数を使い、d に等しい v の要素数を返す } int main() { DO_TEST( my_count(vector<int>({3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}), 1) == 2 ); DO_TEST( my_count(vector<int>({3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}), 10) == 0 ); DO_TEST( my_count(vector<int>({3, 3, 3, 3, 3}), 3) == 5 ); cout << "\nGood Job!\n"; return 0; }
int my_count(const vector<int>& v, int d) { return count(v.begin(), v.end(), d); }
コンテナの要素をコンテナクラスの特定要素数を取得するには、int std::count(first, last, value) 関数を使う。 first, last はコンテナの先頭, 末尾+1だ。そして value はカウントするデータ値を指定する。
vector<string>参照型のlstを受け取り、文字列を昇順(辞書順)にソートする関数 void my_sort(vector<string>& lst) を実装しなさい。
例えば、{"abc", "xz", "ab", "ac", "abb", "xyz"} が渡された場合、結果は {"ab", "abb", "abc", "ac", "xyz", "xz"} となる。
#include <iostream> #include <algorithm> #include <vector> #include <string> 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_sort(vector<string>& lst) { // ToDo: 標準ライブラリの関数を使い、lst の要素を昇順ソートする } int main() { vector<string> vs = {"abc", "xz", "ab", "ac", "abb", "xyz"}; my_sort(vs); DO_TEST( vs == vector<string>({"ab", "abb", "abc", "ac", "xyz", "xz"}) ); vs.clear(); my_sort(vs); DO_TEST( vs.empty() ); cout << "\nGood Job!\n"; return 0; }
void my_sort(vector<string>& lst) { sort(lst.begin(), lst.end()); // lst の要素を昇順ソート }
コンテナクラスの要素を昇順ソートするには、void std::sort(first, last) 関数を使う。 first, last はソート範囲の先頭, 末尾+1で、配列アドレスまたはイテレータで指定可能だぞ。
vector<int>参照型のlst, 削除する値aを引数にとり、lstの要素でaに等しいものをすべて削除する関数 void my_remove(vector<int>& v, int a) を実装しなさい。
例えば v: {1, 2, 3} と 2 が渡された場合は v: {1, 3} となり、v: {3, 1, 4, 1} と 1 が渡された場合は v: {3, 4} となる。
#include <iostream> #include <algorithm> #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_remove(vector<int>& v, int a) { // ToDo: 標準ライブラリの関数を使い、a に等しい v の要素を削除する } int main() { vector<int> v0 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; my_remove(v0, 8); DO_TEST( v0 == vector<int>({3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}) ); vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; my_remove(v, 1); DO_TEST( v == vector<int>({3, 4, 5, 9, 2, 6, 5, 3, 5}) ); cout << "\nGood Job!\n"; return 0; }
void my_remove(vector<int>& v, int a) { auto itr = remove(v.begin(), v.end(), a); // 要素aを削除 v.resize(itr - v.begin()); // 不要な要素を削除 }
コンテナクラスの特定要素を削除するには、Iterator std::remove(first, last, d) 関数を使う。
first, last は削除対象範囲の先頭, 末尾+1で、d は削除する要素の値を指定する。
std::remove() は削除されたデータ分縮小された範囲の末尾+1を指すイテレータを返すので、
v.resize(itr - v.begin()); を実行し、引数で渡された v の不要になった要素を削除する必要があるぞ。
↑第3回、↓第4回
今回で本シリーズも最後だ。今回も競技プログラミング風問題を解いて、標準C++ライブラリにより詳しくなっていただこう。
問題を理解したら、テストコードをコンパイル・実行してほしい。そのままだと実行時に「NG」が表示されるので、 コードを完成させて、「Good Job!」を表示させていただきたい。グッドラック!
目次:
int[] 型のar, 要素数sz, データdを受け取り、ar から sz個の要素にdを充填する関数 void my_fill(int ar[], int sz, int d) を実装しなさい。
例えば、int v[] = {0, 0, 0, 0, 0, 0, 0} のとき、my_fill(v+2, 3, 1) がコールされると、 v は {0, 0, 1, 1, 1, 0, 0} となる。
#include <iostream> #include <algorithm> #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_fill(int ar[], int sz, int d) { // ToDo: 標準ライブラリの関数を使い、サイズ sz の配列 ar のすべての要素を d にする } int main() { int ar[] = {0, 0, 0, 0, 0, 0, 0}; // 要素数:7 const int sz = sizeof(ar)/sizeof(int); my_fill(ar+2, 3, 1); DO_TEST( vector<int>(ar, ar+sz) == vector<int>({0, 0, 1, 1, 1, 0, 0}) ); my_fill(ar, 7, 2); DO_TEST( vector<int>(ar, ar+sz) == vector<int>({2, 2, 2, 2, 2, 2, 2}) ); cout << "\nGood Job!\n"; return 0; }
void my_fill(int ar[], int sz, int d) { fill(ar, ar + sz, d); // 範囲 [ar, ar + sz) の値を d に設定 }
コンテナクラスの全要素を設定するには、std::fill(first, last, value) 関数を使う。 first, last は充填範囲の先頭, 末尾+1で、配列アドレスまたはイテレータを指定可能だぞ。
vector<string>参照型のlstを引数で受け取り、重複する要素を削除し、さらに小さい順にソートする関数 void uniqSort(vector<string>& lst) を実装しなさい。
例えば、{"abc", "abb", "abc"} が渡された場合は、"abc" が重複しているのでひとつ消され、昇順ソートされた {"abb", "abc"} を返す。
#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 uniqSort(vector<string>& lst) { // ToDo: 標準ライブラリの関数を使い、lst の重複する要素を削除・昇順ソートする } int main() { vector<string> vs = {"abc", "xz", "ab", "ac", "abb", "xyz", "ab", "abc", "xz"}; uniqSort(vs); DO_TEST(vs == vector<string>({"ab", "abb", "abc", "ac", "xyz", "xz"})); vector<string> vs2 = {"abc", "abc", "abc"}; uniqSort(vs2); DO_TEST(vs2 == vector<string>({"abc"})); vector<string> vs3 = {}; uniqSort(vs3); DO_TEST(vs3 == vector<string>()); cout << "\nGood Job!\n"; return 0; }
void uniqSort(vector<string>& lst) { sort(lst.begin(), lst.end()); // 要素を昇順ソート auto itr = unique(lst.begin(), lst.end()); // 重複要素を削除 lst.resize(itr - lst.begin()); // 不要な要素を削除 }
問題では重複を削除してからソートと書いているが、先にソート処理を行う。
昇順ソートは std::sort(first, last) を使う。first, last は言うまでもないが、ソート範囲だ。
コンテナ全体をソートするので、lst.first(), lst.end() を渡すんだぞ。
最後に std::unique(first, last) をコールして重複した要素を削除する。
この関数も std::remove(first, last) 同様にコンテナの要素そのものを削除せず、前にデータを詰めて、
最後のデータ+1を指すイテレータを返すので、lst.resize(itr - lst.begin()); で、不要な要素を削除しているぞ。
文字列を第1引数で受け取り、その文字列のすべての順列を辞書順で第2引数に格納する関数 void permutation(string str, vector<string>& lst) を実装しなさい。
例えば、"abc" が引数で渡された場合は、{"abc", "acb", "bac", "bca", "cab", "cba"} が第2引数に格納される。
"cba" のように各文字が昇順でない場合、"aab" のように重複がある場合などにもちゃんと対応しなさい。
#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 permutation(string str, vector<string>& lst) { // ToDo: 標準ライブラリの関数を使い、昇順に順列をすべて生成し、lst に格納する } int main() { vector<string> lst; permutation("abc", lst); DO_TEST( lst == vector<string>({"abc", "acb", "bac", "bca", "cab", "cba"}) ); permutation("cba", lst); DO_TEST( lst == vector<string>({"abc", "acb", "bac", "bca", "cab", "cba"}) ); permutation("aba", lst); DO_TEST( lst == vector<string>({"aab", "aba", "baa"}) ); cout << "\nGood Job!\n"; return 0; }
void permutation(string str, vector<string>& lst) { lst.clear(); // lst クリア sort(str.begin(), str.end()); // 全順列が生成されるように、str の各文字をソート do { lst.push_back(str); // 生成された順列テキストを lst に保存 } while (next_permutation(str.begin(), str.end())); // 次の順列を生成 }
文字列の順列を生成するには next_permutation(str.begin(), str.end()) を用いる。
結果文字列は昇順に生成されるので、最初に文字列の各文字をソートしておく。
lst は最初に内容をクリアし、生成された順列文字列を push_back() で追加していく。
標準C++ライブラリ入門向けの競技プログラミング風問題を12問解いていただいた。
標準C++ライブラリを知って、使いこなせれば、いろいろなコードを楽に、かつ高品質に書けることを実感していただけたものと思っている。
本連載を機に標準C++ライブラリに興味を持っていただき、使いこなせるようになっていただけたら幸いである。