[C++][std::string]std::string型の文字列の改行コードを高速で取り除く方法について

Question

###前提・実現したいこと
c++のstd::string型の文字列に含まれる改行コードのみを高速で取り除きたい
c++11, c++14の機能は使用せず実現したい

###発生している問題・エラーメッセージ
改行を含む文字ファイルをstd::stringに読み込み、findメソッドで改行コードを先頭から検索→見つかるたびにreplaceメソッドで空文字に置換するような処理を作成しました。
元データが10万行を超えるような長いものになるととても時間がかかるのですが、より良い方法はないでしょうか。
よろしくお願いいたします。

###該当のソースコード
```c++
//あらかじめstd::string targetStrに対象の文字列が読み込まれているものとする。
const std::string CRLF = "
";
const std::string CR = "";
const std::string LF = "
";
std::string::size_type pos = 0;
while(pos = targetStr.find(CRLF, pos), pos != std::string::npos) {
	targetStr.replace(pos,CRLF.length(), "");
	pos += CRLF.length();
}
pos = 0;
while(pos = targetStr.find(CR, pos), pos != std::string::npos) {
	targetStr.replace(pos,CR.length(), "");
	pos += CR.length();
}
pos = 0;
while(pos = targetStr.find(LF, pos), pos != std::string::npos) {
	targetStr.replace(pos,LF.length(), "");
	pos += LF.length();
}
```


###補足情報(言語/FW/ツール等のバージョンなど)
cまたはc++
ただしc++11, c++14の機能は使用せず実現したい

Accepted Answer

`std::string::replace`はコストが高い処理なので、きついのだと思います。また、CRの処理とLFの処理だけでCRLFも削除されるので必要ありません。ということで、別途、stringを新たに作る形にして、最後にコピーすれば良いのでは無いでしょうか？ただし、メモリは2倍必要になるので、その点はご注意を。

```C++
void deleteNl(std::string &targetStr)
{
	const char CR = '';
	const char LF = '
';
	std::string destStr;
	for (std::string::const_iterator it = targetStr.begin();
			it != targetStr.end(); ++it) {
		if (*it != CR && *it != LF) {
			destStr += *it;
		}
	}
	targetStr = destStr;
}
```

---
おまけ

C++11が使えるならムーブにすることで、ちょっとだけ速くなるような気がします。

```C++
void deleteNl2(std::string &targetStr)
{
	const char CR = '';
	const char LF = '
';
	std::string destStr;
	for (const auto c : targetStr) {
		if (c != CR && c != LF) {
			destStr += c;
		}
	}
	targetStr = std::move(destStr);
}
```

Answer

How about this?

```C++
void remove_crlf(std::string& s)
{
    size_t i, j;
    for( i = 0, j = 0; i < s.size(); i++ ){
        if( s[i] != '' && s[i] != '
' ){
            s[j] = s[i];
            j++;
        }
    }
    s.resize(j);
}
```

Without resizing, this string is not null-terminating.

Answer

C++98/03縛りでもBoostライブラリの利用OKなら、1行で実現できます。速度は未計測ですが、replaceを3回呼び出すよりは速いと期待したいところ...

C++
1#include <boost/range/algorithm_ext/erase.hpp>
2#include <boost/algorithm/string/classification.hpp>
3
4void remove_crlf(std::string& s)
5{
6  boost::remove_erase_if(s, boost::is_any_of("\r\n"));
7}

Answer

「CRまたはLF」を除外してみた: ```C++ #include #include #include using namespace std; int main() { string str = "abc def ghi "; string::iterator last = remove_if(str.begin(), str.end(), [](char ch) { return ch == ' ' || ch == ' '; }); str.erase(last, str.end()); cout << '[' << str << "] "; } ```

Answer

10万行ともなるとコピーコストも莫迦にできませんね。文字列の途中の文字を削除しようとすると、その位置にそれ以降を文字列終端までコピーすることになり、結果、同じ部分を何度もコピーするので非効率です。
raccyさんのように別の文字列に移し替えるようにすれば最小限のコピーで済みます。

raccyさんとは別のやり方で作ってみました。文字列領域を若干多めに取ることになりますが、コピーは最小限だと思います。
※reserveで領域サイズを決め打ちしているので、もしかしたら領域の節約になっているかもしれません。

非C++11版
```C++
struct IfCrLf
{
	bool operator ()(char ch)
	{
		return ch == '' || ch == '
';
	}
};

struct IfNotCrLf
{
	bool operator ()(char ch)
	{
		return ch != '' && ch != '
';
	}
};

std::string str;
str.reserve(targetStr.length());
auto iter = targetStr.begin();
while(iter != targetStr.end())
{
	auto iter2 = std::find_if(iter, targetStr.end(), IfCrLf());
	str.append(iter, iter2);
	iter = std::find_if(iter2, targetStr.end(), IfNotCrLf());
}
targetStr.swap(str);
```

C++11版
```C++
auto ifcrlf = [](char ch){return ch == '' || ch == '
';};
std::string str;
str.reserve(targetStr.length());
auto iter = targetStr.cbegin();
while(iter != targetStr.cend())
{
	auto iter2 = std::find_if(iter, targetStr.cend(), ifcrlf);
	str.append(iter, iter2);
	iter = std::find_if_not(iter2, targetStr.cend(), ifcrlf);
}
targetStr.swap(str);
```

Answer

こんにちは。

string::find_first_of()でCRとLFの最初に出現したものをサーチしつつ、リプレースすれば１パスで済むので1.5倍強くらいの速度になるだろうと思います。

---
【追記】
文字は削除するだけなので、前方へコピーすれば済む筈です。
```C++
std::size_t n=0;
std::string::iterator dst=targetStr.begin();
std::string::iterator end=targetStr.end();
for (std::string::iterator src=targetStr.begin() ; src != end; ++src)
{
    if ((*src == '') || (*src == '
'))
continue;

    *dst++=*src;
    ++n;
}
targetStr.resize(n);
```
最後のresize()で変なコピーしないかちょっとだけ心配ですが、縮める方向なので管理領域を書き換えるだけと期待。