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++練度上がり次第、足していきます。