list - vector
C++では#include <vector>で利用する。
要素へのアクセス
例：インデックス1に10を代入し要素をプリント
- Python
xxx_list = [0]*5
xxx_list[1] = 10
print(xxx_list[1])
- C++
vector<int> xxx_list(5, 0);
xxx_list.at(1) = 10;
cout << xxx_list.at(1) << endl;
C++でもxxx_list[1]で要素アクセスできるが、範囲外での動作が不安定なのでatを使ったほうが無難
末尾へ要素追加
- Python
xxx_list = [0]*5
xxx_list.append(1)
- C++
vector<int> xxx_list(5, 0);
xxx_list.push_back(1);
Pythonでは要素の追加に+= [1]の様な手法も使える
末尾から要素削除
- Python
xxx_list = [0]*5
xxx_list.pop()
- C++
vector<int> xxx_list(5, 0);
xxx_list.pop_back();
要素の長さを出力
- Python
xxx_list = [0]*5
print(len(xxx_list))
- C++
vector<int> xxx_list(5, 0);
cout << xxx_list.size() << endl;
dict - map or unordered_map
C++ではそれぞれ#include <map>、#include <unordered_map>を宣言してから使う。
- dict, unordered_mapはハッシュを使った実装(要素の追加、探索などに平均$O(1)$だが最悪$O(n)$)
- mapは平衡二分探索木を使った実装(要素の追加、探索などに$O(\log n)$)
平衡二分探索木を使ったmap、multimapはx以下最大の要素を対数時間で探す事もできる。普通に有能。
キーと値の追加
- Python
xxx_dict = dict()
xxx_dict["A"] = 1
print(xxx_dict["A"])
- C++
map<string, int> xxx_map;
xxx_map["A"] = 1;
cout << xxx_map["A"] << endl;
C++のmapはdefaultdictの挙動に似ていて存在しないキーを指定すると初期値が返ってくる。mapとunordered_mapで指定方法は同じ
キーが存在するかどうかの判定
- Python
xxx_dict = {"A": 1, "B": 2}
if "A" in xxx_dict:
print(xxx_dict["A"])
- C++
map<string, int> xxx_map = {{"A", 1}, {"B", 2}};
if (xxx_map.find("A") != xxx_map.end()){
cout << xxx_map["A"] << endl;
}
キーの削除
- Python
xxx_dict = {"A": 1, "B": 2}
xxx_dict.pop("A")
- C++
map<string, int> xxx_map = {{"A", 1}, {"B", 2}};
xxx_map.erase("A");
forループによる処理
- Python
xxx_dict = {"A": 1, "B": 2}
for k, v in xxx_dict.items():
print(k, v)
- C++
map<string, int> xxx_map = {{"A", 1}, {"B", 2}};
for (auto& [key, value]: xxx_map){
cout << key << " " << value << endl;
}
set - set or unordered_set
C++ではそれぞれ#include <set>、#include <unordered_set>を宣言してから使う。
- Pythonのset, unordered_setはハッシュを使った実装(要素の追加、探索などに平均$O(1)$だが最悪$O(n)$)
- C++のsetは平衡二分探索木を使った実装(要素の追加、探索などに$O(\log n)$)
平衡二分探索木を使ったset、multisetはx以下最大の要素を対数時間で探す事もできる。
Pythonで平衡二分探索木を使ったsetが使いたい時はtatyamさんによるSortedSetライブラリを引っ張ってきて使う。
要素の追加
- Python
xxx_set = set()
xxx_set.add(1)
- C++
set<int> xxx_set;
xxx_set.insert(1);
要素が存在するかの判定
- Python
xxx_set = {1, 2}
if 1 in xxx_set:
print("exist")
- C++
set<int> xxx_set = {1, 2};
if (xxx_set.find(1) != xxx_set.end()){
cout << "exist" << endl;
}
要素の削除
- Python
xxx_set = {1, 2}
xxx_set.pop(1)
- C++
set<int> xxx_set = {1, 2};
xxx_set.erase(1);
forループによる処理
- Python
xxx_set = {1, 2, 4}
for x in xxx_set:
print(x)
- C++
set<int> xxx_set = {1, 2, 4};
for (auto& x: xxx_set){
cout << x << endl;
}
まとめ
Python記述楽だけど遅い。C++とにかく速い。
著者のC++練度上がり次第、足していきます。