最近、アルゴリズムとデータ構造に関して学び直しを行っています。Pythonを用いて、LeetCodeの問題を解くことに主軸を置いています。参考に書籍を読むこともありますが、書籍のコードにC++が使われていることが多く、読み解くのに少し時間がかかります。そこで、アルゴリズムとデータ構造に関する書籍に頻出するC++の記法のみを、Pythonと対応付けながらざっと学習したいと考えました。上記のことをChatGPTに依頼したところ、個人的に満足の行くものが出力できたので、本ブログに掲載しておきます。

(ブログに載せておくと目次をつけることで見たいコンテンツにすぐにたどり着けるため、主に個人用途です。)

1. 入出力
- C++
- Python
- 複数入力
  - C++
  - Python
- 配列入力
  - C++
  - Python
2. 変数宣言
- C++
- Python
- よく見る型
  - C++
3. 配列・vector
- C++
- Python
- 長さ n の配列を作る
  - C++
  - Python
- 2次元配列
  - C++
  - Python
4. ループ
- for 文
  - C++
  - Python
- 1 から n まで
  - C++
  - Python
- 逆順ループ
  - C++
  - Python
- while 文
  - C++
  - Python
5. 条件分岐
- C++
- Python
6. 関数
- C++
- Python
- bool を返す関数
  - C++
  - Python
7. 文字列
- C++
- Python
- 部分文字列
  - C++
  - Python
8. pair
- C++
- Python
- pair の配列
  - C++
  - Python
9. auto
- C++
- Python
10. sort
- 昇順ソート
  - C++
  - Python
- 降順ソート
  - C++
  - Python
- pair のソート
  - C++
  - Python
- key を使ったソート
  - C++
  - Python
11. 最大値・最小値
- C++
- Python
- 配列の最大最小
  - C++
  - Python
12. 合計
- C++
- Python
13. 二分探索
- lower_bound
  - C++
  - Python
- upper_bound
  - C++
  - Python
14. set
- C++
- Python
- 違い
  - C++
  - Python
15. map
- C++
- Python
- Counter 的な使い方
  - C++
  - Python
16. queue
- C++
- Python
17. stack
- C++
- Python
18. priority_queue
- C++
- Python
- 最小値を取りたい C++ と対応させる
  - C++
  - Python
- pair を入れる
  - C++
  - Python
19. foreach のような書き方
- C++
- Python
- pair を同時に受け取る
  - C++
  - Python
20. 添字つきループ
- C++
- Python
21. 参照
- C++
- Python
22. const
- C++
- Python
23. 無限大の表現
- C++
- Python
24. 構造体 struct
- C++
- Python
25. グラフの隣接リスト
- C++
- Python
- 重み付きグラフ
  - C++
  - Python
26. DP 配列
- C++
- Python
- 2次元DP
  - C++
  - Python
27. bit演算
- AND, OR, XOR
  - C++
  - Python
- シフト
  - C++
  - Python
- i ビット目が立っているか
  - C++
  - Python
28. 全探索でよくある bit 列挙
- C++
- Python
29. lambda
- C++
- Python
30. 三項演算子
- C++
- Python
31. よくあるマクロ・別名
- C++
- Python
- よくある省略
  - C++
32. emplace_back と push_back
- C++
- Python
33. begin(), end()
- C++
- Python
34. size()
- C++
- Python
35. empty()
- C++
- Python
36. first, second
- C++
- Python
37. よくある C++ のアルゴリズムコードを Python に読む例
- 例1: 配列の和
  - C++
  - Python
- 例2: 最小値を探す
  - C++
  - Python
- 例3: BFS
  - C++
  - Python
- 例4: ダイクストラ
  - C++
  - Python
38. まず読めるようになるための対応表
39. 読書中に特に困りやすいポイント
- 1. 型はあまり気にしすぎなくてよい
- 2. vector は Python の list だと思ってよい
- 3. pair はタプル
- 4. priority_queue だけは注意
- 5. lower_bound は bisect_left
- 6. 競プロ特有の省略記法は展開して読む
40. おすすめの読み方

競プロやアルゴリズム本でよく出る C++の定番記法 を、意味と Pythonでの対応 がすぐ分かる形でまとめるね。

最初に結論を言うと、アルゴリズム本を読むために必要なのは、C++を全部覚えることではなくて、

配列・文字列
ループ
関数
pair / vector
sort
queue / stack / priority_queue
set / map
lower_bound / upper_bound
bit演算

このあたりを読めるようになることです。ここを押さえるだけで、かなり読みやすくなる。

1. 入出力

C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << n << endl;
}

Python

n = int(input())
print(n)

複数入力

C++

int a, b;
cin >> a >> b;

Python

a, b = map(int, input().split())

配列入力

C++

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

Python

n = int(input())
a = list(map(int, input().split()))

2. 変数宣言

C++

int x = 3;
long long y = 10000000000;
double z = 1.5;
string s = "abc";
bool ok = true;

Python

x = 3
y = 10000000000
z = 1.5
s = "abc"
ok = True

よく見る型

C++

int : 普通の整数
long long : 大きい整数
double : 実数
string : 文字列
bool : 真偽値

Python は整数がかなり大きくなってもそのまま扱えるので、 C++ の long long を Python では普通の int と考えてよいことが多い。

3. 配列・vector

C++

vector<int> a = {1, 2, 3};
cout << a[0] << endl;
a.push_back(4);

Python

a = [1, 2, 3]
print(a[0])
a.append(4)

長さ n の配列を作る

C++

vector<int> a(n);

これは 0 で初期化された長さ n の配列。

Python

a = [0] * n

2次元配列

C++

vector<vector<int>> dp(n, vector<int>(m, 0));

Python

dp = [[0] * m for _ in range(n)]

注意として、Python で次はダメなことが多い。

dp = [[0] * m] * n

これだと内側のリストが同じものを参照してしまう。

4. ループ

for 文

C++

for (int i = 0; i < n; i++) {
    cout << i << endl;
}

Python

for i in range(n):
    print(i)

1 から n まで

C++

for (int i = 1; i <= n; i++) {
}

Python

for i in range(1, n + 1):
    pass

逆順ループ

C++

for (int i = n - 1; i >= 0; i--) {
}

Python

for i in range(n - 1, -1, -1):
    pass

while 文

C++

while (x > 0) {
    x--;
}

Python

while x > 0:
    x -= 1

5. 条件分岐

C++

if (x > 0) {
    cout << "positive" << endl;
} else if (x == 0) {
    cout << "zero" << endl;
} else {
    cout << "negative" << endl;
}

Python

if x > 0:
    print("positive")
elif x == 0:
    print("zero")
else:
    print("negative")

6. 関数

C++

int add(int a, int b) {
    return a + b;
}

Python

def add(a, b):
    return a + b

bool を返す関数

C++

bool is_even(int x) {
    return x % 2 == 0;
}

Python

def is_even(x):
    return x % 2 == 0

7. 文字列

C++

string s = "abc";
cout << s[0] << endl;
cout << s.size() << endl;

Python

s = "abc"
print(s[0])
print(len(s))

部分文字列

C++

string s = "abcdef";
cout << s.substr(2, 3) << endl;  // "cde"

Python

s = "abcdef"
print(s[2:5])  # "cde"

C++ の substr(開始位置, 長さ) と Python の s[l:r] は少し感覚が違うので注意。

8. pair

C++本ではかなりよく出る。

C++

pair<int, int> p = {3, 5};
cout << p.first << " " << p.second << endl;

Python

p = (3, 5)
print(p[0], p[1])

pair の配列

C++

vector<pair<int, int>> vp;
vp.push_back({2, 10});
vp.push_back({1, 20});

Python

vp = []
vp.append((2, 10))
vp.append((1, 20))

9. auto

C++ では型を省略して auto をよく使う。

C++

auto x = 10;
auto p = make_pair(3, 4);

Python

x = 10
p = (3, 4)

Python は基本的に全部これに近い。

10. sort

昇順ソート

C++

sort(a.begin(), a.end());

Python

a.sort()

降順ソート

C++

sort(a.begin(), a.end(), greater<int>());

Python

a.sort(reverse=True)

pair のソート

C++

vector<pair<int, int>> vp = {{2, 3}, {1, 5}, {2, 1}};
sort(vp.begin(), vp.end());

これは first を優先し、同じなら second で昇順。

Python

vp = [(2, 3), (1, 5), (2, 1)]
vp.sort()

Python のタプルも同じルールで比較される。

key を使ったソート

C++

sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
});

Python

v.sort(key=abs)

11. 最大値・最小値

C++

int x = max(a, b);
int y = min(a, b);

Python

x = max(a, b)
y = min(a, b)

配列の最大最小

C++

int mx = *max_element(a.begin(), a.end());
int mn = *min_element(a.begin(), a.end());

Python

mx = max(a)
mn = min(a)

12. 合計

C++

int sum = accumulate(a.begin(), a.end(), 0);

Python

total = sum(a)

C++ では #include <numeric> が必要なことが多い。

13. 二分探索

これは本当に頻出。

lower_bound

C++

int idx = lower_bound(a.begin(), a.end(), x) - a.begin();

意味:

a[idx] >= x となる最初の位置

Python

import bisect
idx = bisect.bisect_left(a, x)

upper_bound

C++

int idx = upper_bound(a.begin(), a.end(), x) - a.begin();

意味:

a[idx] > x となる最初の位置

Python

import bisect
idx = bisect.bisect_right(a, x)

14. set

C++

set<int> st;
st.insert(3);
st.insert(1);
st.insert(3);
cout << st.count(3) << endl;

Python

st = set()
st.add(3)
st.add(1)
st.add(3)
print(3 in st)

違い

C++ の set は 常にソートされた状態。 Python の set は 順序なし。

だから、

C++

set<int> st = {3, 1, 2};
// 取り出すと 1, 2, 3 の順になりやすい

Python

st = {3, 1, 2}
# 順序は保証されない

C++ の set に近いことを Python でやりたいなら、

set に入れて
必要時に sorted(st)

とすることが多い。

15. map

C++

map<string, int> mp;
mp["apple"] = 3;
mp["banana"]++;
cout << mp["apple"] << endl;

Python

mp = {}
mp["apple"] = 3
mp["banana"] = mp.get("banana", 0) + 1
print(mp["apple"])

Counter 的な使い方

C++

map<int, int> cnt;
for (int x : a) cnt[x]++;

Python

cnt = {}
for x in a:
    cnt[x] = cnt.get(x, 0) + 1

または

from collections import Counter
cnt = Counter(a)

16. queue

C++

queue<int> q;
q.push(3);
q.push(5);
cout << q.front() << endl;
q.pop();

Python

from collections import deque

q = deque()
q.append(3)
q.append(5)
print(q[0])
q.popleft()

BFS ではこれを使う。

17. stack

C++

stack<int> st;
st.push(3);
st.push(5);
cout << st.top() << endl;
st.pop();

Python

st = []
st.append(3)
st.append(5)
print(st[-1])
st.pop()

Python ではリストを stack として使うことが多い。

18. priority_queue

ヒープ。ダイクストラ法などでよく出る。

C++

priority_queue<int> pq;
pq.push(3);
pq.push(5);
cout << pq.top() << endl;  // 5

これは 最大ヒープ。

Python

import heapq

pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 5)
print(pq[0])  # 3

Python の heapq は 最小ヒープ。

最小値を取りたい C++ と対応させる

C++

priority_queue<int, vector<int>, greater<int>> pq;

Python

import heapq
pq = []

このときは両方とも最小ヒープとして考えられる。

pair を入れる

C++

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({dist, v});

Python

import heapq
pq = []
heapq.heappush(pq, (dist, v))

タプル比較で先頭から比較されるので、かなり対応しやすい。

19. foreach のような書き方

C++

for (int x : a) {
    cout << x << endl;
}

Python

for x in a:
    print(x)

pair を同時に受け取る

C++

for (auto [x, y] : vp) {
    cout << x << " " << y << endl;
}

Python

for x, y in vp:
    print(x, y)

20. 添字つきループ

C++

for (int i = 0; i < a.size(); i++) {
    cout << i << " " << a[i] << endl;
}

Python

for i, x in enumerate(a):
    print(i, x)

21. 参照

本でこれが出ると一気に読みづらくなりやすい。

C++

void add_one(int& x) {
    x++;
}

これは x を直接変更する。

Python

Python には同じ意味の参照構文はないので、普通は返り値で書く。

def add_one(x):
    return x + 1

ただし、list などのミュータブルなものは中身を直接変えられる。

def push_item(a):
    a.append(1)

22. const

C++

const int INF = 1e9;

Python

INF = 10**9

Python に厳密な const はない。大文字で「定数っぽい」と表すことが多い。

23. 無限大の表現

C++

const int INF = 1e9;
const long long INF = 1e18;

Python

INF = 10**18

または

INF = float('inf')

ただし競プロでは整数で持つほうが扱いやすいことも多い。

24. 構造体 struct

C++

struct Node {
    int to;
    int cost;
};

Python

簡単にはタプルで済ませることが多い。

node = (to, cost)

あるいは class。

class Node:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost

アルゴリズムでは Python ではタプルで十分なことが多い。

25. グラフの隣接リスト

C++

vector<vector<int>> graph(n);
graph[u].push_back(v);
graph[v].push_back(u);

Python

graph = [[] for _ in range(n)]
graph[u].append(v)
graph[v].append(u)

重み付きグラフ

C++

vector<vector<pair<int, int>>> graph(n);
graph[u].push_back({v, w});

Python

graph = [[] for _ in range(n)]
graph[u].append((v, w))

26. DP 配列

C++

vector<int> dp(n, INF);
dp[0] = 0;

Python

dp = [INF] * n
dp[0] = 0

2次元DP

C++

vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

Python

dp = [[0] * (m + 1) for _ in range(n + 1)]

27. bit演算

AND, OR, XOR

C++

a & b
a | b
a ^ b

Python

a & b
a | b
a ^ b

同じ。

シフト

C++

1 << i

Python

1 << i

これも同じ。

i ビット目が立っているか

C++

if (x & (1 << i)) {
}

Python

if x & (1 << i):
    pass

28. 全探索でよくある bit 列挙

C++

for (int bit = 0; bit < (1 << n); bit++) {
    for (int i = 0; i < n; i++) {
        if (bit & (1 << i)) {
            // i を使う
        }
    }
}

Python

for bit in range(1 << n):
    for i in range(n):
        if bit & (1 << i):
            # i を使う
            pass

29. lambda

C++

auto f = [](int x, int y) {
    return x + y;
};

Python

f = lambda x, y: x + y

ただし Python では複雑な処理なら普通に def を使うほうが読みやすい。

30. 三項演算子

C++

int x = (a > b ? a : b);

Python

x = a if a > b else b

31. よくあるマクロ・別名

本や競プロ解説でかなり出る。

C++

using ll = long long;
using pii = pair<int, int>;

Python

対応する特別な文法はない。普通にそのまま書く。

# ll -> int と考えて読む
# pii -> tuple[int, int] くらいの気持ちで読む

よくある省略

C++

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)

これは競プロ特有。

rep(i, n) {
    cout << i << endl;
}

実質こういう意味。

for (int i = 0; i < n; i++) {
    cout << i << endl;
}

Pythonなら普通に

for i in range(n):
    print(i)

32. `emplace_back` と `push_back`

C++

v.push_back({x, y});
v.emplace_back(x, y);

アルゴリズム本を読む範囲では、どちらも「末尾に追加してる」くらいで読んで大丈夫。

Python

v.append((x, y))

33. `begin()`, `end()`

C++

sort(a.begin(), a.end());
reverse(a.begin(), a.end());

a 全体に対して処理していると思えばよい。

Python

a.sort()
a.reverse()

34. `size()`

C++

a.size()
s.size()

Python

len(a)
len(s)

35. `empty()`

C++

if (q.empty()) {
}

Python

if not q:
    pass

36. `first`, `second`

C++

pair<int, int> p = {2, 5};
cout << p.first << p.second << endl;

Python

p = (2, 5)
print(p[0], p[1])

あるいはアンパック。

x, y = p
print(x, y)

37. よくある C++ のアルゴリズムコードを Python に読む例

例1: 配列の和

C++

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];
}

Python

total = 0
for i in range(n):
    total += a[i]

または

total = sum(a)

例2: 最小値を探す

C++

int ans = INF;
for (int i = 0; i < n; i++) {
    ans = min(ans, a[i]);
}

Python

ans = INF
for i in range(n):
    ans = min(ans, a[i])

例3: BFS

C++

queue<int> q;
q.push(s);
dist[s] = 0;

while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int nv : graph[v]) {
        if (dist[nv] != -1) continue;
        dist[nv] = dist[v] + 1;
        q.push(nv);
    }
}

Python

from collections import deque

q = deque([s])
dist[s] = 0

while q:
    v = q.popleft()
    for nv in graph[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + 1
        q.append(nv)

例4: ダイクストラ

C++

priority_queue<pair<long long, int>,
               vector<pair<long long, int>>,
               greater<pair<long long, int>>> pq;

pq.push({0, s});
dist[s] = 0;

while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop();
    if (d > dist[v]) continue;

    for (auto [nv, cost] : graph[v]) {
        if (dist[nv] > dist[v] + cost) {
            dist[nv] = dist[v] + cost;
            pq.push({dist[nv], nv});
        }
    }
}

Python

import heapq

pq = [(0, s)]
dist[s] = 0

while pq:
    d, v = heapq.heappop(pq)
    if d > dist[v]:
        continue

    for nv, cost in graph[v]:
        if dist[nv] > dist[v] + cost:
            dist[nv] = dist[v] + cost
            heapq.heappush(pq, (dist[nv], nv))

38. まず読めるようになるための対応表

かなり実用的な最小セットだけ抜くとこうです。

C++	Python
`vector<int> a(n)`	`a = [0] * n`
`a.push_back(x)`	`a.append(x)`
`a.size()`	`len(a)`
`sort(a.begin(), a.end())`	`a.sort()`
`reverse(a.begin(), a.end())`	`a.reverse()`
`pair<int,int>`	`(x, y)`
`p.first`, `p.second`	`p[0]`, `p[1]`
`queue<int>`	`deque`
`stack<int>`	`list`
`priority_queue`	`heapq`
`set<int>`	`set`
`map<int,int>`	`dict`
`lower_bound`	`bisect_left`
`upper_bound`	`bisect_right`
`for (int i=0; i<n; i++)`	`for i in range(n)`
`for (auto x : a)`	`for x in a`
`if (...) continue;`	`if ...: continue`

39. 読書中に特に困りやすいポイント

最後に、C++本をPython学習者が読むときのコツを書いておくね。

1. 型はあまり気にしすぎなくてよい

int, long long, pair<int,int> などが並んでいても、まずは

整数
配列
2つ組

くらいにざっくり読む。

2. `vector` は Python の list だと思ってよい

ほとんどの場面でそれで十分。

3. `pair` はタプル

{dist, v} は (dist, v) と読めばかなり楽になる。

4. `priority_queue` だけは注意

C++ はデフォルトで最大ヒープ、Python は最小ヒープ。ここは混乱しやすい。

5. `lower_bound` は `bisect_left`

二分探索の章ではほぼこれと思ってよい。

6. 競プロ特有の省略記法は展開して読む

たとえば

rep(i, n)

を見たら、頭の中で

for (int i = 0; i < n; i++)

に展開する。

40. おすすめの読み方

本を読むときは、C++ を Python に逐一完全翻訳しようとすると遅いので、

データ構造だけ対応づける
- vector → list
- pair → tuple
- queue → deque
ループだけ読み替える
- for (int i = 0; i < n; i++) → for i in range(n)
アルゴリズムの本質だけ追う
- 何を状態にしているか
- どこで更新しているか
- 何を最小化 / 最大化しているか

この順で見ると、かなり楽になる。