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

Question

###前提・実現したいこと
c++のstd::string型の文字列に含まれる改行コードのみを高速で取り除きたい
c++11, c++14の機能は使用せず実現したい

###発生している問題・エラーメッセージ
改行を含む文字ファイルをstd::stringに読み込み、findメソッドで改行コードを先頭から検索→見つかるたびにreplaceメソッドで空文字に置換するような処理を作成しました。
元データが10万行を超えるような長いものになるととても時間がかかるのですが、より良い方法はないでしょうか。
よろしくお願いいたします。

###該当のソースコード

//あらかじめstd::string targetStrに対象の文字列が読み込まれているものとする。
const std::string CRLF = "\r\n";
const std::string CR = "\r";
const std::string LF = "\n";
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の機能は使用せず実現したい

Answer 1

std::string::replaceはコストが高い処理なので、きついのだと思います。また、CRの処理とLFの処理だけでCRLFも削除されるので必要ありません。ということで、別途、stringを新たに作る形にして、最後にコピーすれば良いのでは無いでしょうか？ただし、メモリは2倍必要になるので、その点はご注意を。

void deleteNl(std::string &targetStr)
{
	const char CR = '\r';
	const char LF = '\n';
	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が使えるならムーブにすることで、ちょっとだけ速くなるような気がします。

void deleteNl2(std::string &targetStr)
{
	const char CR = '\r';
	const char LF = '\n';
	std::string destStr;
	for (const auto c : targetStr) {
		if (c != CR && c != LF) {
			destStr += c;
		}
	}
	targetStr = std::move(destStr);
}

Comments

[evans]

raccy様　ご回答ありがとうございます。

取り急ぎ試してみたところ、私のパソコンで10万行のテキストファイルを読み込むと、処理時間が2.32s→0.07s程となりました。

Answer 2

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

#include <boost/range/algorithm_ext/erase.hpp>
#include <boost/algorithm/string/classification.hpp>

void remove_crlf(std::string& s)
{
  boost::remove_erase_if(s, boost::is_any_of("\r\n"));
}

Comments

[evans]

yohhoy様
ご回答ありがとうございます。
外部のライブラリに任せるという選択肢が頭になかったので勉強になりました。
Wiki見てみましたが色々なことができるようですね。
ご回答ありがとうございました。

Answer 3

How about this?

void remove_crlf(std::string& s)
{
    size_t i, j;
    for( i = 0, j = 0; i < s.size(); i++ ){
        if( s[i] != '\r' && s[i] != '\n' ){
            s[j] = s[i];
            j++;
        }
    }
    s.resize(j);
}

Without resizing, this string is not null-terminating.

Comments

[evans]

Dear majiponi.
Thankyou for your answering.
I will use that as reference from now on.

Answer 4

「CRまたはLF」を除外してみた:

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
  string str = "abc\r\ndef\r\nghi\r\n";
  string::iterator last = 
    remove_if(str.begin(), str.end(), 
              [](char ch) { return ch == '\r' || ch == '\n'; });
  str.erase(last, str.end());
  cout << '[' << str << "]\n";
}

Comments

[episteme]

lambda使うなってことでしたら
struct cr_or_lf {
　bool operator()(char ch) const { return ch=='\r' || ch == '\n'; }
};

を用意して、lambdaんトコを cr_or_lf() にさしかえ。

[evans]

episteme様
ご回答ありがとうございます。
参考にさせていただきます。

Answer 5

10万行ともなるとコピーコストも莫迦にできませんね。文字列の途中の文字を削除しようとすると、その位置にそれ以降を文字列終端までコピーすることになり、結果、同じ部分を何度もコピーするので非効率です。
raccyさんのように別の文字列に移し替えるようにすれば最小限のコピーで済みます。

raccyさんとは別のやり方で作ってみました。文字列領域を若干多めに取ることになりますが、コピーは最小限だと思います。
※reserveで領域サイズを決め打ちしているので、もしかしたら領域の節約になっているかもしれません。

非C++11版

struct IfCrLf
{
	bool operator ()(char ch)
	{
		return ch == '\r' || ch == '\n';
	}
};

struct IfNotCrLf
{
	bool operator ()(char ch)
	{
		return ch != '\r' && ch != '\n';
	}
};

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版

auto ifcrlf = [](char ch){return ch == '\r' || ch == '\n';};
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);

Comments

[Chironian]

ああ、完全に思い違いしてました。「空文字に置換」って文字削除だったのですね。
それは重いはず。

[evans]

catsforepaw様　ご回答ありがとうございます。
参考にさせていただきます。

Answer 6

こんにちは。

string::find_first_of()でCRとLFの最初に出現したものをサーチしつつ、リプレースすれば１パスで済むので1.5倍強くらいの速度になるだろうと思います。

---

【追記】
文字は削除するだけなので、前方へコピーすれば済む筈です。

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 == '\r') || (*src == '\n'))
continue;

    *dst++=*src;
    ++n;
}
targetStr.resize(n);

最後のresize()で変なコピーしないかちょっとだけ心配ですが、縮める方向なので管理領域を書き換えるだけと期待。

Comments

[yumetodo]

つまり
static const char CRLF[] = "\r\n";
for(std::size_t pos = targetStr.find_first_of(CRLF, 0, sizeof(CRLF)); std::string::npos != pos; pos = targetStr.find_first_of(CRLF, pos, sizeof(CRLF))) targetStr[pos] = '\0';
こうかな。

[evans]

Chironian様　ご回答ありがとうございます。
以下のようなコードで認識あっておりますでしょうか？
std::string::size_type pos = 0;
while(pos = targetStr.find_first_of("\r\n", pos), pos != std::string::npos) {
targetStr.replace(pos, 1, "");
pos += 1;
}
しかし上記のコードをCRLFを含むテキストファイルに試してみたところ、CRだけがreplaceされてしまいました…
使い方をもう少し勉強してみます。

[evans]

yumetodo様　ご回答ありがとうございます。

いただいたコードでコンパイルして実行してみたのですが、どこかで止まってしまい終了しなくなりました。
↓書いたコード全文

--------------------------------------------
#include <fstream>
#include <iostream>
#include <string>
#include <iterator>

int main() {
std::ifstream ifs("test.txt");
if (ifs.fail())
{
std::cerr << "失敗" << std::endl;
return -1;
}
std::string targetStr((std::istreambuf_iterator<char>(ifs)),
std::istreambuf_iterator<char>());

//const std::string CRLF = "\r\n";
//const std::string CR = "\r";
//const std::string LF = "\n";

static const char CRLF[] = "\r\n";
for(std::size_t pos = targetStr.find_first_of(CRLF, 0, sizeof(CRLF)); std::string::npos != pos; pos = targetStr.find_first_of(CRLF, pos, sizeof(CRLF))) targetStr[pos] = '\0';

std::cout << "[" << targetStr << "]" << std::endl;

return 0;
}

[Chironian]

evansさん。

replace()が悪さしているようです。targetStr[pos]=0;にすればちゃんと0に置き換えられました。また、raccyさんによるとreplaceは遅いようなので、targetStr[pos]の方が速いと思います。（operator[]は指定文字への参照を返却しますので変更可能です。）

yumetodoさん。
sizeof(CRLF)は3になるのでちょっとまずいかも。

[evans]

Chironian様
どうもありがとうございます。
targetStr.replace(pos, 1, "");　を
targetStr[pos]=0;　にしたところ、意図したとおりに動作しました。