C++のsetのSをS.begin()から一つずつ足して中身を見ると、昇順になる理由がわかりません。

Question

C++のsetのSをS.begin()から一つずつ足して中身を出力、昇順で出力される理由がわかりません。
setの構造が二分木ならS.begin()が根で、その次が根の左の子、その次が根の右の子。というふうにならないのでしょうか？

int main(){
	set<int> S;
	S.insert(2);
	S.insert(7);
	S.insert(1);
	S.insert(9);
	S.insert(32);
	S.insert(0);
	for (auto i = S.begin(); i != S.end(); i++)
	{
		cout<<(*i)<<endl;
		/*
		0
		1
		2
		7
		9
		32
		*/
	}
}

Answer 1

こんにちは。

C++のsetのSをS.begin()から一つずつ足して中身を出力、昇順で出力される理由がわかりません。

「そのように決められていて、お使いの処理系が規格通りに実装されているから」です。

cppreference.comによると、

std::set は Key 型の一意なオブジェクトのソートされた集合を格納する連想コンテナです。ソートはキー比較関数 Compare を使用して行われます。

(中略）

begin 先頭を指すイテレータを返します
end 終端を指すイテレータを返します

提示されているコードでは、 Compare を指定していないため、デフォルトの std::less<int> が使われます。int型は組込み型なので、組込みのoperator<()へ展開されます。
従って、小さい順にソートされますので、begin()～end()で取り出すと昇順で並びます。

Answer 2

setの構造が二分木ならS.begin()が根で、その次が根の左の子、その次が根の右の子。というふうにならないのでしょうか？

(根からじゃなく)左端の末っ子を起点に辿れば小さい順になります。

※ "set::begin() が二分木の根を指す" なんて、標準C++規格にはどこにも書かれていません。
さらに言えば "std::set は二分木で実装されている(or されなければならない)" とも書かれていません。
言語規格書には 検索/削除が時間計算量 O(logN) であること と書かれているだけです。
実際のところほとんどすべて二分木(赤黒木)で実装されてるんですけどね。