if (j <= list[i].ko.size() - 2) { cout << ",g "; }でjが０でlist[i].ko.size()-2が-1の時にcout << ",g ";が実行される

Question

Tree - Rooted Trees
↑のアルゴリズムの問題を解いているのですが書いたプログラムの一部が変な動きをします。
以下に書いたプログラムを載せます。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };

struct MyStruct
{
	int parent = -1;
	int depth;
	vector<int>ko;
};


signed main() {
	int i, j;
	int n;
	vector<MyStruct>list(100005);


	cin >> n;

	for (i = 0; i < n; i++) {
		int num, num2;
		cin >> num >> num2;

		for (j = 0; j < num2; j++) {
			int num3;
			cin >> num3;
			list[num].ko.push_back(num3);
			list[num3].parent = num;
		}

	}


	for (i = 0; i < n; i++) {
		int cnt = 0;
		int num = list[i].parent;

		while ( num != -1 )
		{
			cnt++;
			num = list[num].parent;
		}

		list[i].depth = cnt;
	}


	for (i = 0; i < n; i++) {
		cout << "node " << i << ": parent = " << list[i].parent << ", depth = " << list[i].depth << ", ";
		if (list[i].parent == -1) {
			cout << "root, [";
			for (j = 0; j < list[i].ko.size(); j++) {
				cout << list[i].ko[j];
				if (j <= list[i].ko.size() - 2) { cout << ",g "; } //←ここがおかしな動きをする
			}
			cout << "]" << endl;
		}
		else if (list[i].ko.size() >= 1) {
			cout << "internal node, [";
			for (j = 0; j < list[i].ko.size(); j++) {
				cout << list[i].ko[j];
				if (j <= list[i].ko.size() - 2) { cout << ", "; }
			}
			cout << "]" << endl;
		}
		else if (list[i].ko.size() == 0) {
			cout << "leaf, []" << endl;
		}

	}


	getchar();
	getchar();
	return 0;
}

↑のプログラムに下記のデータを入力します。
2
0 1 1
1 0

すると以下のように出力されます。
node 0: parent = -1, depth = 0, root, [1,g ]
node 1: parent = 0, depth = 1, leaf, []

どうやらif (j <= list[i].ko.size() - 2) { cout << ",g "; }でjが０でlist[i].ko.size() - 2 が-1の時にcout << ",g ";が実行されるようです。条件式の通りに動くならjが0で右辺より大きいので実行されないような気がするのですがどうなっているのでしょうか。

Answer 1

どうやらif (j <= list[i].ko.size() - 2) { cout << ",g "; }でjが０でlist[i].ko.size() - 2 が-1の時にcout << ",g ";が実行されるようです。

vector.sizeの返り値が符号なし整数で、オーバーフローを起こしているのでは。
条件式をj + 2 <= list[i].ko.size()にしてみてはいかがでしょう。

なお、カウンタの型を符号なし整数にした方が無用なトラブルを避けられそうです。

Comments

[tada_tadaa]

回答ありがとうございます。
よく分かりませんが言われた通りにしてみるとうまく動きました。

上手く動いた
if (j <= (int)list[i].ko.size() - 2) { cout << ",g "; }
if (j + 2 <= list[i].ko.size()) { cout << ",g "; }

上手く動かない
if (j <= list[i].ko.size() - 2) { cout << ",g "; }
if (j <= (list[i].ko.size()) - 2) { cout << ",g "; }

今まではこのやり方で特に不具合が出ていなかったので思わぬ落とし穴って感じです。
ちなみに
＞なお、カウンタの型を符号なし整数にした方が無用なトラブルを避けられそうです。

とは変数 j を符号なし整数にした方が良いという事でしょうか？

[tada_tadaa]

https://anond.hatelabo.jp/20090817145359
↑ここに説明っぽいものが載っていました。

引用
■C++ STLのvectorコンテナのsize()関数

醜悪なことにこいつの返り値はintではなくunsigned intのようだ。
従って、サイズ0のvectorに対して
vec.size()-1
という演算をすると結果は-1ではなく、オーバーフローしてunsigned intの最大値になる。
サイズがゼロだったら-1になるだろjkとか思ってコーディングすると酷い目にあう。

引用終わり
vector.size()の返り値がマイナスの値を受け付けないとは知りませんでした。いい勉強になりました。
ありがとうございました。

[LouiS0616]

> よく分かりませんが言われた通りにしてみるとうまく動きました。

次のコードを実行してみると良いです。
unsigned int n = 1;
std::cout << n - 2 << "\n";

---
> 変数 j を符号なし整数にした方が良い

そのとおりです。

ついでに。カウンタ変数をmain関数のスコープで宣言する意味が無いので、for文の初期化部で宣言した方がすっきりしたコードになると思います。
文字数的には増えますが、幾分か動作を追いやすくなります。

[tada_tadaa]

unsigned int n = 1;
int n2 = 1;
std::cout << n - 2 << "\n";
std::cout << n2 - 2 << "\n";

結果
4294967295
-1

となりました。原因がよく分かりました。カウンタ変数に対するアドバイスもありがとうございました。