C++ における string の iterator と erase

　友人に「最初の投稿で既に日本語が怪しい」と言われたにわぽんです。これから頑張っていきます。今回はC++における string 型についてです。ABC120に出場している間に調べたことを、自分なりにまとめてみました。
atcoder.jp

毎回コンテストの後は、記事を投稿することにしました。出場した結果としましては、、、

 A～Cの３問を解いて1515位でした。無事レートを上げることができました。また、前回のABC119では、A と B の２問しか解けませんでした。今回はC問題を解きたいと思っていたので、それも達成できました。コンテストの結果としては、とても満足しています。

　全問題の解法は、自分よりもっと優秀な人が書く内容だと思っています。今回は私がC問題で使った、C++における string の仕様についてまとめていきます。
atcoder.jp
解説では、0の個数と1の個数を数えて解いています。この解法が一番よさそうです。私はこの解法に気づかず、次のアルゴリズムでこの問題を解けると考えて、実装しました。

1. 整数の変数 i を用意し、i = 0 としておく
2. ( i + 1 ) が S の文字数を超えているなら、ステップ5 へ
3. i 番目の文字と ( i + 1 ) 番目の文字が異なる場合、その 2 文字をSから削除し、i = 0 でないなら、i = i - 1として、ステップ 2 に戻る
4. i 番目の文字と ( i + 1 ) 番目の文字が同じ場合、i = i + 1 としてステップ 2 へ
5. ステップ 3 の計算で削除した文字の数を出力

文字列の先頭から見ていき、違う 2 文字の組があれば、その 2 文字を削除します。一応このアルゴリズムでも O(N) 時間で計算できている、と思っていますが自信はないです。

　このアルゴリズムを実装するのに string に実装されている erase というメソッドを使いました。この erase の使い方と、iterator についてをまとめたいと思います。
vivi.dyndns.org

こちらのサイトを参考にさせていただきました。

　まず、string に実装されている、文字列の一部を削除するメソッドを探しました。そして、 erase というメソッドがそれにあたることが分かりました。erase は iterator という型を引数にとっています。iterator とはなんなのでしょうか？

　自分なりに iterator が何なのかをまとめてみました。S を string 型の変数とします。このとき S の iterator である変数 itr は、「S の itr 番目の文字が保存してある場所」を表す変数です。C言語におけるポインタに近いものみたいですね。今回重要なのは次のことでした。

• S.begin() で「S の 0 番目の文字が保存してある場所」にあたる iterator を取得できる
• itr + k は 「S の (itr + k) 番目の文字が保存してある場所」にあたる iterator になる
• *itr で「S の itr 番目の文字」を取得できる
• S.erase(itr1, itr2)は「S の itr1 番目の文字から、( itr2 - 1 ) 番目の文字を削除する」という計算を行う

これらを踏まえて書いたコードが以下のものです。

#include <iostream>
using namespace std;
int main(){
	string S;
	cin >> S;
	string::iterator itr = S.begin();
	int cnt = 0;
	int i = 0;
	while(i + 1< S.length()){
		if(*(itr + i) != *(itr + 1 + i)){
			S.erase(itr + i, itr + 2 + i);
			cnt = cnt + 2;
			itr = S.begin();
			if(i > 0){
				i--;
			}
		}
		else{
			i++;
		}
	}
	cout << cnt << endl;
}

このコードは、コンテスト中に提出したものを少し整理したものです。提出してみるとACでした(見やすいコードを書く練習もしたいですね)。
　コンテスト中にこういった言語の仕様を調べています。これにかかる時間を減らすためにも、一度調べたことは記事にまとめることにしました。iterator については、まだよく分かっていないので、これからも勉強していきたいです。