今日の勉強会は豪華2本建て。後半は「連想配列」についてです。
可変長配列 vector の使い方
C++では今まで扱ってきた固定長配列の他に、vectorという可変長配列を用いることができるようになっています。このvector、今までの配列とは毛色が結構違うので慣れが必要です。使う場合は#include<vector>を忘れずに。
宣言はvector<型> オブジェクト名;のように書きます。この時点では、大きさ0の空っぽの配列です。
では、実際に要素を受け取って追加、出力してみましょう。
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v;
int x;
while(cin >> x){
v.push_back(x);
}
for(int i=0; i<v.size(); i++){
cout << v[i] << "\n";
}
return 0;
}
/*
--input--
1
5
8
-4
2
--output--
1
5
8
-4
2
*/
cin は入力を受け取らないと0を返すので、while文と組み合わせると入力が終わるまで受け取ることができます。
push_back(x) は x を vector の末尾に追加するメソッドです。
そして、size()は vector の要素数を返してくれます。このプログラムは、与えられた入力をvectorに格納し、それを1行1つずつ表示するものです。要素の参照は固定長と同様、[ ]で位置（インデックス）を指定することで参照できます。
連想配列
配列は、（語弊がありますが）連続して置かれた変数の集まりだと思ってもらえればいいです。メモリ上では連続的に確保されているので、値の取り出しや探索にはインデックスを1~Nまで動かして取得したり探すことになり、\(O(N)\)だけかかります（線形探索）。
一方、連想配列はインデックスの代わりにキーというものを持ちます。キーと値がペアになって格納されています。計算量は\(O(\log N)\)になるので、より高速にデータの取り出しや探索が可能になります。何度も値の出し入れを行う場合などでは有効ですね。
C++における連想配列クラスはmapです。
宣言はmap<keyの型, valueの型> オブジェクト名;のようにします。
キーに対応する値を追加するには、以下のようにします。
map<string, int> mp; mp["Japan"] = 81; cout << mp["Japan"] << "\n"; // 81 cout << mp["USA"] << "\n"; // 0(intのデフォルト値)
値が設定されていないキーを指定した場合、値型のデフォルト値というのが返ってきます。
座標圧縮
ここでひとつ問題を解いてみましょう。ABC036 C問題
大小関係を維持したまま、その差をぎゅっと縮めて値のとる範囲を狭めるという問題ですね。これは座標圧縮というテクニックで、探索時間を短くするのに役立ちます（問題名の座圧はそれが由来）。
愚直な解法を考えると、まず、値を格納している配列をソートし、順番に値を割り当てていきます。もとの並び順を保持したもうひとつの配列の値と、割り当てた結果を照らし合わせ、割り当てた値を出力していくと答えになります。
割り当てた結果は2次元配列などを使って格納できます（1次元固定長配列のインデックスをもとの値、中身を割り当てた値にするのも考えられるが、もとの値 a のとる範囲が大きすぎる）。
例えば、固定長ならint a[100000][2];という2次元配列の1番目にもとの値、2番目に割り当てた値を格納すればいいでしょう。ただ、せっかくなのでC++標準ライブラリのデータ構造のひとつ、pairを使ってみましょう。
pairクラスは、2つの値の組を効率よく扱えるクラスです。こんな風に使います。
#include <iostream>
#include <utility> // pairを扱うライブラリ
using namespace std;
int main(){
pair<int, int> p; // 2つの値の型を指定して宣言
p = make_pair(3, 5); // pair型で値を渡す際はmake_pairを使う
// 1番目, 2番目にはぞれぞれメンバ変数first、secondでアクセスできる
cout << p.first << " " << p.second << "\n";
return 0;
}
/*
--output--
3 5
*/
それと、配列のソートですが、これにも便利な関数があります。
・sort(配列の始点, 配列の終点, 比較関数)
vectorのオブジェクトを（デフォルトでは）昇順にソートします。こんな風に使います。
#include <iostream>
#include <vector>
#include <algorithm> // sortが入ったライブラリ
using namespace std;
int main(){
vector<int> v;
int a;
while(cin >> a){
v.push_back(a);
}
sort(v.begin(), v.end()); // 始点と終点を指定
for(int i=0; i<v.size(); i++) cout << v[i] << "\n";
return 0;
}
/*
--input--
1
5
8
-4
2
--output--
-4
1
2
5
8
*/
begin() はvectorの始点を、end() はvectorの終点を返します。ソートの基準は比較関数というものに与えてやることで決めることもできるので、自分で調べてみましょう。
では、実装していきましょう。2次元配列の代わりに、vector<pair<int, int> >を使いましょう。
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main(){
int N;
cin >> N;
vector<int> v_def; // もとの並びを保持しておくvector
vector<pair<int, int> > v; // もとの値と割り当てられる値を保持するvector
for(int i=0; i<N; i++){
int a;
cin >> a;
v_def.push_back(a);
v.push_back(make_pair(a, 0)); // 割り当てする前はとりあえず0を入れておく
}
sort(v.begin(), v.end());
int before = v[0].first; // 直前のもとの値
int idx = 0; // 割り当てる値
for(int i=1; i<N; i++){
if(v[i].first != before){ // 前の値と違うならば(つまり差があるならば)
idx++;
before = v[i].first;
}
v[i].second = idx; // 値の割り当て
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(v_def[i] == v[j].first){
cout << v[j].second << "\n";
break;
}
}
}
return 0;
}
この計算量は \(O(N^2)\) です。そのため、\(N \leq 10^5\) ではTLEしてしまいます。これは、割り当てた値をvectorから取り出すのに時間がかかっているからです。
ここで、vector<pair<int, int> >の代わりにmap<int, int>を使ってみましょう。
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> v;
vector<int> v_def;
map<int, int> mp; // map(連想配列), 特定のキーに対応する値を素早く返します.
int N;
cin >> N;
for(int i=0; i<N; i++){
int a;
cin >> a;
v.push_back(a);
v_def.push_back(a);
}
sort(v.begin(), v.end());
int before = v[0];
int idx = 0;
for(int i=1; i<N; i++){
if(v[i] != before){
idx++;
before = v[i];
}
mp[v[i]] = idx; // v[i]:もとの値, idx:座標圧縮した値 という形でmapに保存されます
}
for(int i=0; i<N; i++){
cout << mp[v_def[i]] << "\n"; // もとの順番どおりに呼び出し, それぞれの座標圧縮した値を表示
}
return 0;
}
pairはfirstでソートされ、同じ値のpairが複数あればsecondの値でそれらの順番が決まります。
計算量は \(O(N\log N)\) になり、満点を獲得できました。
なんか冗長じゃない？
vectorを2つとmap、さらにあまり意味のないbeforeなどの一時的な変数など、このコードはまだまだ冗長です。もっときれいに書けないでしょうか？
実は、mapは常にkeyでソートされた状態になっています。なので、最初からmapに入れ、上から順番に値を割り当てていけばいいことになります。
…ん？順番に？
mapはインデックスの代わりにkeyを渡して値を参照していました。ではどうやって順番に値を取り出せばいいでしょうか？
そこで、イテレータ(iterator)を使います。iteratorは、連続に格納されているデータにひとつずつアクセスする方法のことです。
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> v_def;
map<int, int> mp;
int N;
cin >> N;
for(int i=0; i<N; i++){
int a;
cin >> a;
v_def.push_back(a);
mp[a] = 0;
}
int idx = 0;
// イテレータ
for (map<int, int>::iterator itr = mp.begin(); itr != mp.end(); itr++) {
itr->second = idx++;
}
/* C++14以降では、こんな記法もあります. 意味は上と同じです
for(auto x : mp){
x.second = idx++;
}
*/
for(int i=0; i<N; i++){
cout << mp[v_def[i]] << "\n";
}
return 0;
}
map<int, int> （mpのクラス）のデータを順番に取り出すイテレータは map<int, int>::iterator のように宣言します。開始位置をmp.begin() に設定し、mp.end() に到達するまで順番にデータを読んでいく、という仕組みになっています。
mapのkeyにはitr->first 、値にはitr->second でアクセスできます。
これで、コードもすっきりしましたね！なかなか難しいですが、ゆっくりマスターしたいなと思ったのでした。
Pingback: 9/28定例勉強会(1) 「C++標準ライブラリの基本」 – 東北大学puzzleknot 公式サイト
Pingback: 10/26定例勉強会「第一回バーチャルコンテスト」 – 東北大学puzzleknot 公式サイト