1

文字列 txt, in-placeから特定の文字を削除する方法を実装していました。以下は私のコードです。結果は「bdeg」として期待されます。ただし、結果は「bdegfg」で、null ターミネータが設定されていないようです。奇妙なことは、nullターミネータを設定した後、gdbを使用してデバッグするときです

(gdb) p txt
$5 = (std::string &) @0xbffff248: {static npos = <optimized out>, 
  _M_dataplus = {<std::allocator<char>> = {<__gnu_cxx::new_allocator<char>> = {<No data fields>}, <No data fields>}, _M_p = 0x804b014 "bdeg"}}

それは私には正しく見えます。では、ここで何が問題なのですか？

#include <iostream>
#include <string>

using namespace std;

void censorString(string &txt, string rem)
{
    // create look-up table
    bool lut[256]={false};
    for (int i=0; i<rem.size(); i++)
    {
        lut[rem[i]] = true;
    }
    int i=0;
    int j=0;

    // iterate txt to remove chars
    for (i=0, j=0; i<txt.size(); i++)
    {
        if (!lut[txt[i]]){
            txt[j]=txt[i];
            j++;
        }
    }

    // set null-terminator
    txt[j]='\0';
}

int main(){
    string txt="abcdefg";
    censorString(txt, "acf");

    // expect: "bdeg"
    std::cout << txt <<endl;
}

フォローアップの質問:

文字列が c 文字列のように切り詰められていない場合。それで何が起こるtxt[j]='\0' のか、なぜそれが「bdeg'\0'g」またはいくつかの破損した文字列ではなく「bdegfg」なのか。

別のフォローアップ：私が使用する場合 txt.erase(txt.begin()+j, txt.end()）; それは正常に動作します。だから私は文字列関連のAPIを使ったほうがいいです。ポイントは、これらの API の基礎となるコードの時間の複雑さがわからないということです。

4

5 に答える 5

2

a 内に null ターミネータを埋め込むことstd::stringは完全に有効であり、文字列の長さは変わりません。ただし、たとえばストリーム抽出を使用して出力しようとすると、予期しない結果が得られます。

達成しようとしている目標は、はるかに簡単に達成できます。

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

int main()
{
    std::string txt="abcdefg";
    std::string filter = "acf";
    txt.erase(std::remove_if(txt.begin(), txt.end(), [&](char c) 
    { 
        return std::find(filter.begin(), filter.end(), c) != filter.end(); 
    }), txt.end());

    // expect: "bdeg"
    std::cout << txt << std::endl;
}

Himanshuの答えと同じように、次のようにO（N）の複雑さ（追加のメモリを使用）を達成できます。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_set>

int main()
{
    std::string txt="abcdefg";
    std::string filter = "acf";

    std::unordered_set<char> filter_set(filter.begin(), filter.end());
    std::string output;

    std::copy_if(txt.begin(), txt.end(), std::back_inserter(output), [&](char c)
    {
        return filter_set.find(c) == filter_set.end();  
    });

    // expect: "bdeg"
    std::cout << output << std::endl;
}
于 2013-09-19T20:46:10.253 に答える
2

あなたが考えるように std::string は null で終了していないため、これを行うには他の方法を使用する必要があります

関数を次のように変更します。

void censorString(string &txt, string rem)
{
    // create look-up table
    bool lut[256]={false};
    for (int i=0; i<rem.size(); i++)
    {
        lut[rem[i]] = true;
    }

    // iterate txt to remove chars
    for (std::string::iterator it=txt.begin();it!=txt.end();)
    {

        if(lut[*it]){
            it=txt.erase(it);//erase the character pointed by it and returns the iterator to next character
            continue;
        }
        //increment iterator here to avoid increment after erasing the character
        it++;
    }
}

ここでは基本的にstd::string::erase、イテレータを入力として取り、次の文字にイテレータを返す文字列内の任意の文字を消去する関数 を使用する必要がありますhttp://en.cppreference.com/w/cpp/string/basic_string/erase http://www. cplusplus.com/reference/string/string/erase/

消去関数の複雑さは O(n) です。したがって、関数全体の複雑さは o(n^2) になります。非常に長い文字列、つまり >256 文字のスペースの複雑さは O(n) になります。時間に対して O(n) の複雑さしか持たない別の方法があります。txt別の文字列を作成し、検閲されていない文字列を反復しながら文字を追加します。

新しい関数は次のようになります。

void censorString(string &txt, string rem)
{
    // create look-up set
    std::unordered_set<char> luckUpSet(rem.begin(),rem.end());
    std::string newString;

    // iterate txt to remove chars
    for (std::string::iterator it=txt.begin();it!=txt.end();it++)
    {

        if(luckUpSet.find(*it)==luckUpSet.end()){
            newString.push_back(*it);
        }
    }
    txt=std::move(newString);
}

std::unordered_set::find関数とO(1) の複雑さがあるため、この関数の複雑さは O(n) になりますstd::string::push_back。O(log n) の複雑さを持つ通常の std::set find を使用すると、関数全体の複雑さは O(n log n) になります。

于 2013-09-19T20:26:00.443 に答える
1

サイズを変更したことを文字列に伝えていません。resize文字列から文字を削除する場合は、メソッドを使用してサイズを更新する必要があります。

于 2013-09-19T20:26:46.433 に答える
0

問題は、C スタイルの文字列のように C++ 文字列を扱うことができないことです。つまり、C のように 0 を挿入することはできません。これを納得させるには、コードに「cout << txt.length() << endl;」を追加します。- 7 を取得します。ererase() メソッドを使用します。

Removes specified characters from the string.
1) Removes min(count, size() - index) characters starting at index.
2) Removes the character at position.
3) Removes the character in the range [first; last).
于 2013-09-19T20:25:24.333 に答える
0

テキストは文字配列ではなく文字列です。このコード

// set null-terminator
txt[j]='\0';

j 番目の位置で文字列を切り捨てません。

于 2013-09-19T20:26:35.727 に答える