日本語を使用している時にstd::stringのfind系が意図通りに動かない問題


# はじめに
この記事はフリューAdvent Calendar 2022の15日目の記事となります。

std::stringのfind関連のお話です。
日本語(マルチバイト文字)を使用している時に起こる問題について記載しています。

# std::stringのfind系の処理で取得できる位置が意図通りにならない問題
早速ですが、下記のコード。

ファイルパスの文字列解析してフォルダ名だけ取得したくて、
フォルダ名の先頭の文字の位置を取得したいとかそんな場合のコードを想定しています。
(変なフォルダ名とかは気にしないでください)

さて、下記のコードを実行した場合表示される結果はどうなるでしょうか？
```C++
int main()
{
	std::string hoge = "C:\\ソうダネ";

	std::cout << "\\の位置を先頭から検索した結果 位置=" << hoge.find( "\\", 0 ) << std::endl;
	std::cout << "\\の位置を末尾から検索した結果 位置=" << hoge.find_last_of( "\\" ) << std::endl;

	return 0;
}
```

先頭の「C」が0番目になるので、普通に考えたら「\」を検索したらどちらも「2」が出るはず。
(※コード上は\\\\で記載されていますが、一つ目の\はエスケープ文字なので\\\\で1文字)
実際の結果はこんな感じになります。

```
\の位置を先頭から検索した結果 位置=2
\の位置を末尾から検索した結果 位置=4
```

もちろんfind_last_ofのバグではないです。
この原因を理解するためにはstd::stringのfindの処理だけでなく、
「文字コード」への理解が必要になります。

# std::stringのfind
std::stringで保持している文字列はchar配列になっています。
findはchar配列に格納されたものを**一つずつ前から比較**していきます。
find_last_ofは**一つずつ後ろから比較**していきます。
find_last_ofは検索する文字列が2文字以上の場合、
**検索する文字列のいずれか1つにヒットした位置**が返ります。
(**※完全一致ではない**)
これは皆さんご存知かと思います。
findについてはこれだけ。でもこれが重要。

# 日本語の文字コード
次に文字コードについて。
日本語は「マルチバイト文字」で表現されます。
「マルチバイト」という言葉が示す通り、複数のバイトで1文字を表現しています。

1文字を表現するために各byteに数値が割り当てられています。
日本語で使用される規格で一般的なものをいくつか挙げておきます。

* Shift-JIS
* Unicode
* EUC-JP

今回問題を起こしている文字コードはどれでしょうか？
先に答えを言ってしまうと「**Shift-JIS**」になります。
Shift-JISは2byteで1文字を表現する文字コードになっています。

## 日本語が入ってる時のchar配列の数は？
マルチバイトについて説明したので次はchar配列に格納されているデータの数について。
今回、`std::string hoge = "C:\\ソうダネ"`という文字列を設定しました。

「マルチバイト文字」を理解していればわかるかと思いますが、
日本語はマルチバイト文字(=Shift-JISは2byteで1文字)として扱われるので、
1byteのcharの配列は「\0」を含めて合計12になります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2969992/a5dad147-18db-9faa-5065-77d20f597579.png)

割り当てはこんな感じ↓
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2969992/6243cd49-19fb-6240-2ad5-435dd6c8c0c1.png)


## Shift-JISでバグる原因は「ダメ文字」！！
先程の文字の割り当てと↑のタイトル見ただけで既に分かった方もいるかもしれませんが、引き続き説明を続けます。
この章のタイトルに書いた通り、原因は「**ダメ文字**」です。

ダメ文字とは**マルチバイト文字を1byteずつに分割した時に「\」や「_」などと同じ文字コードを含む文字**のことです。
他にもダメ文字と呼ばれるものはたくさんありますが、今回は割愛。
詳しくは検索したら出てきます。

実際に`C:\\ソうダネ`の文字コードを16進数で表示してみます。

```C++
int main()
{
	// 16進数で表示する設定
	std::cout.setf( std::ios::hex, std::ios::basefield );

	std::cout << "C=" << ( unsigned int ) 'C' << std::endl;
	std::cout << ":=" << ( unsigned int ) ':' << std::endl;
	std::cout << "\\=" << ( unsigned int ) '\\' << std::endl;
   	std::cout << "ソ=" << ( unsigned int ) 'ソ' << std::endl;
   	std::cout << "う=" << ( unsigned int ) 'う' << std::endl;
   	std::cout << "ダ=" << ( unsigned int ) 'ダ' << std::endl;
   	std::cout << "ネ=" << ( unsigned int ) 'ネ' << std::endl;
	std::cout << "\\0=" << ( unsigned int ) '\0' << std::endl;

	return 0;
}
```

結果↓
```
C=43
:=3a
\=5c
ソ=835c
う=82a4
ダ=835f
ネ=836c
\0=0
```

これを先程の表に割り当てるとこんな感じ↓
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2969992/b0b1a401-376b-5b8c-b302-a71d489d8138.png)

ここまで来たらfind_last_ofのバグではないことがお分かりいただけるかな？と思います。
`C:\\ソうダネ`の文字のうち、**「ソ」は「\」(0x5c)を含むダメ文字**です。
(「ダ」もダメ文字ですが今回は割愛)

この文字列を後ろから「\」(0x5c)を**1byteずつ**探索したらどうなるでしょうか？

最初にヒットするのは **「ソ」に含まれる「0x5c」**
つまり位置的には「4」なのでfind_last_ofはバグってないです。正常です。


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2969992/311a9a25-376d-2906-c1ec-3519785055b3.png)
黄色：前から検索した時にヒットする「\」(0x5c)
赤色：後ろから検索した時にヒットする「\」(0x5c)

# ダメ文字を回避するには？
ダメ文字を回避するためには取得したcharがマルチバイト文字かシングルバイト文字かを判定して、
マルチバイト文字なら検索位置を余分に進める処理を実装する必要があります。


## こんなコード作ってみました
find_last_ofは**完全一致の位置を返してくれない**ので、ちょっと挙動を改造してコードを作ってみました。

たとえばこんな感じ

**【先頭から検索】**
```C++
std::string::size_type GetFirstPos( const std::string& str, const std::string& searchStr )
{
	std::string::size_type pos = 0;

	while( pos < str.length() )
	{
		//文字列が一致するか確認
		if( str.substr( pos, searchStr.length() ) == searchStr )
		{
			//一致したら終了
			return pos;
		}


		//一致しなかった場合
		//マルチバイトか確認
		if( _mbclen( ( unsigned char* ) &str[ pos ] ) == 2 )
		{
			//マルチバイトだったら2つ進める
			pos += 2;
			continue;
		}

		//マルチバイトじゃなかったとき
		++pos;
	}

	//一致しなかったとき
	return std::string::npos;
}
```

**【末尾から検索】**
```C++
// 文字列を探索し、一番最後の位置を返す
// 後ろから検索するとマルチバイト文字の2byte目がマルチバイト判定の文字コードと一致するとバグるので前から順に見る
std::string::size_type GetLastPos( const std::string& str, const std::string& searchStr )
{
	// find_last_of の仕様にある程度合わせる
	if( searchStr.empty() == true || str.length() < searchStr.length() )
	{
		return std::string::npos;
	}

	std::string::size_type pos = 0;
	std::string::size_type lastPos = std::string::npos;

	while( pos < str.size() )
	{
		//探してる文字と一致
		if( str.substr( pos, searchStr.length() ) == searchStr )
		{
			// 一致した位置を保持しておく
			lastPos = pos;
		}

		//マルチバイトだったら次の文字
		if( _mbclen( ( unsigned char* ) &str[ pos ] ) == 2 )
		{
			pos += 2;
		}
		else
		{
			++pos;
		}
	}

	return lastPos;
}
```

上記を呼び出してみる↓

```C++
int main()
{
	std::string hoge = "C:\\ソうダネ";
	
	// ↑のhogeより長い文字列
    std::string long_hoge = "0123456789abcdef";

	std::cout << "\\の位置を先頭から検索した結果 位置=" << GetFirstPos( hoge, "\\" ) << std::endl;
	std::cout << "\\の位置を末尾から検索した結果 位置=" << GetLastPos( hoge, "\\" ) << std::endl;

	std::cout << std::endl;
	
	std::cout << "ダの位置を先頭から検索した結果 位置=" << GetFirstPos( hoge, "ダ" ) << std::endl;
	std::cout << "ダの位置を末尾から検索した結果 位置=" << GetLastPos( hoge, "ダ" ) << std::endl;

	std::cout << std::endl;


	std::cout << "一致しない文字列を先頭から検索した結果(通常のfind) 位置=" << hoge.find( "ab", 0 ) << std::endl;
	std::cout << "一致しない文字列を末尾から検索した結果(通常のfind) 位置=" << hoge.find_last_of( "ab" ) << std::endl;

	std::cout << std::endl;

	std::cout << "一致しない文字列を先頭から検索した結果 位置=" << GetFirstPos( hoge, "ab" ) << std::endl;
	std::cout << "一致しない文字列を末尾から検索した結果 位置=" << GetLastPos( hoge, "ab" ) << std::endl;

	std::cout << std::endl;

	std::cout << "空文字列の位置を先頭から検索した結果(通常のfind) 位置=" << hoge.find( "", 0 ) << std::endl;
	std::cout << "空文字列の位置を末尾から検索した結果(通常のfind) 位置=" << hoge.find_last_of( "" ) << std::endl;

	std::cout << std::endl;

	std::cout << "空文字列の位置を先頭から検索した結果 位置=" << GetFirstPos( hoge, "" ) << std::endl;
	std::cout << "空文字列の位置を末尾から検索した結果 位置=" << GetLastPos( hoge, "" ) << std::endl;

	std::cout << std::endl;

	std::cout << "サイズオーバーを先頭から検索した結果(通常のfind) 位置=" << hoge.find( long_hoge, 0 ) << std::endl;
	std::cout << "サイズオーバーを末尾から検索した結果(通常のfind) 位置=" << hoge.find_last_of( long_hoge ) << std::endl;

	std::cout << std::endl;

	std::cout << "サイズオーバーを先頭から検索した結果 位置=" << GetFirstPos( hoge, long_hoge ) << std::endl;
	std::cout << "サイズオーバーを末尾から検索した結果 位置=" << GetLastPos( hoge, long_hoge ) << std::endl;

	return 0;
}
```


結果↓
```
\の位置を先頭から検索した結果 位置=2
\の位置を末尾から検索した結果 位置=2

ダの位置を先頭から検索した結果 位置=7
ダの位置を末尾から検索した結果 位置=7

一致しない文字列を先頭から検索した結果(通常のfind) 位置=18446744073709551615
一致しない文字列を末尾から検索した結果(通常のfind) 位置=18446744073709551615

一致しない文字列を先頭から検索した結果 位置=18446744073709551615
一致しない文字列を末尾から検索した結果 位置=18446744073709551615

空文字列の位置を先頭から検索した結果(通常のfind) 位置=0
空文字列の位置を末尾から検索した結果(通常のfind) 位置=18446744073709551615

空文字列の位置を先頭から検索した結果 位置=0
空文字列の位置を末尾から検索した結果 位置=18446744073709551615

サイズオーバーを先頭から検索した結果(通常のfind) 位置=18446744073709551615
サイズオーバーを末尾から検索した結果(通常のfind) 位置=18446744073709551615

サイズオーバーを先頭から検索した結果 位置=18446744073709551615
サイズオーバーを末尾から検索した結果 位置=18446744073709551615
```

※上記の実行結果で出てくる`18446744073709551615`の値は`std::string::npos`の数値

敢えて`GetLastPos`の仕様を`find_last_of`と変えてたりしています。
下記の場合の結果を変えています。

```
・2文字以上の文字列を検索
・マルチバイト文字を検索
・サイズオーバーかつ一部が一致している文字列を検索
```

例えばこんな時↓
```C++
int main()
{
	std::string fuga = "01234567";

	std::cout << "文字列を先頭から検索した結果(通常のfind) 位置=" << fuga.find( "23", 0 ) << std::endl;
	std::cout << "文字列を末尾から検索した結果(通常のfind) 位置=" << fuga.find_last_of( "23" ) << std::endl;

	std::cout << std::endl;

	std::cout << "文字列を先頭から検索した結果 位置=" << GetFirstPos( fuga, "23" ) << std::endl;
	std::cout << "文字列を末尾から検索した結果 位置=" << GetLastPos( fuga, "23" ) << std::endl;

	std::cout << std::endl;

	std::string hoge = "C:\\ソうダネ";

	// ↑のhogeより長い文字列
	std::string long_hoge = "C:\\ソうダネソうダネ";

	std::cout << "ダの位置を先頭から検索した結果(通常のfind) 位置=" << hoge.find( "ダ", 0 ) << std::endl;
	std::cout << "ダの位置を末尾から検索した結果(通常のfind) 位置=" << hoge.find_last_of( "ダ" ) << std::endl;

	std::cout << std::endl;

	std::cout << "ダの位置を先頭から検索した結果 位置=" << GetFirstPos( hoge, "ダ" ) << std::endl;
	std::cout << "ダの位置を末尾から検索した結果 位置=" << GetLastPos( hoge, "ダ" ) << std::endl;

	std::cout << std::endl;

	std::cout << "サイズオーバーを先頭から検索した結果(通常のfind) 位置=" << hoge.find( long_hoge, 0 ) << std::endl;
	std::cout << "サイズオーバーを末尾から検索した結果(通常のfind) 位置=" << hoge.find_last_of( long_hoge ) << std::endl;

	std::cout << std::endl;

	std::cout << "サイズオーバーを先頭から検索した結果 位置=" << GetFirstPos( hoge, long_hoge ) << std::endl;
	std::cout << "サイズオーバーを末尾から検索した結果 位置=" << GetLastPos( hoge, long_hoge ) << std::endl;
}
```


結果↓
```
文字列を先頭から検索した結果(通常のfind) 位置=2
文字列を末尾から検索した結果(通常のfind) 位置=3

文字列を先頭から検索した結果 位置=2
文字列を末尾から検索した結果 位置=2

ダの位置を先頭から検索した結果(通常のfind) 位置=7
ダの位置を末尾から検索した結果(通常のfind) 位置=9

ダの位置を先頭から検索した結果 位置=7
ダの位置を末尾から検索した結果 位置=7

サイズオーバーを先頭から検索した結果(通常のfind) 位置=18446744073709551615
サイズオーバーを末尾から検索した結果(通常のfind) 位置=10

サイズオーバーを先頭から検索した結果 位置=18446744073709551615
サイズオーバーを末尾から検索した結果 位置=18446744073709551615
```

結果の違いはこんな感じ↓
```
・2文字以上の文字列を検索
find_last_of：検索文字列のうち最初にヒットした末尾の文字の位置が返る
GetLastPos：先頭の文字の位置が返る

・マルチバイト文字を検索
find_last_of：検索した文字を1byteずつに分割した文字のうち最初にヒットした末尾の文字の位置が返る
GetLastPos：マルチバイトの1byte目の位置が返る

・サイズオーバーかつ一部が一致している文字列を検索
find_last_of：検索文字列のうち最初にヒットした末尾の文字の位置が返る
GetLastPos：std::string::nposが返る
```

何故このような実装にしたのか？とかこのあたりについてもう少し書きたいのですが、
長くなりすぎるので今回はここまで。
また次回続きを書きます。