質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.50%

  • C++

    3567questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • CRLF

    7questions

    CRLFは、改行コードのことです。 改行コードは、改行を表す制御文字です

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

解決済

回答 6

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 13K+

evans

score 40

前提・実現したいこと

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の機能は使用せず実現したい

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 6

checkベストアンサー

+3

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);
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/05/09 00:08

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

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

    キャンセル

+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"));
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/05/10 00:42

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

    キャンセル

+1

こんにちは。

string::find_first_of()でCRとLFの最初に出現したものをサーチしつつ、リプレースすれば1パスで済むので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()で変なコピーしないかちょっとだけ心配ですが、縮める方向なので管理領域を書き換えるだけと期待。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/05/08 23:35

    つまり
    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';
    こうかな。

    キャンセル

  • 2016/05/08 23:51

    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されてしまいました…
    使い方をもう少し勉強してみます。

    キャンセル

  • 2016/05/08 23:54

    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;
    }

    キャンセル

  • 2016/05/09 00:05

    evansさん。

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

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

    キャンセル

  • 2016/05/09 00:24

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

    キャンセル

+1

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);

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/05/09 00:45

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

    キャンセル

  • 2016/05/10 00:39

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

    キャンセル

+1

「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";
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/05/09 10:18

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

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

    キャンセル

  • 2016/05/10 00:39

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

    キャンセル

+1

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.

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/05/10 00:44

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.50%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C++

    3567questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • CRLF

    7questions

    CRLFは、改行コードのことです。 改行コードは、改行を表す制御文字です