3

3 つの C スタイルの文字列を受け取り、C スタイルの文字列を返す関数を作成しようとしています。この関数は、サブストリングのすべての出現について c-string を検索し、それらを別のストリングに置き換えます。
このプログラムは機能しますが、非常に洗練されていないようです。もっとかさばらない方法でできたような気がして仕方がありません。

char* replaceSubstring(char *original, char *from, char *to)
{
     int origlen = strlen(original);
     int i = 0;
     int count = 0;
     char *ptr;

     //figure out how many times the sub-string occurs in a string.
     //i couldn't figure out a way to avoid this loop
     while (i<origlen)
     {
           ptr = strstr(original+i, from);
           if (!ptr)
               break;
           else
           {
               i = ptr - original + 1;
               count++;
           }
     }
     //figure out what the size of the output string has to be
     int newsize = origlen + (strlen(to) - strlen(from)) * count;

     char *newstring = new char[newsize];  
     newstring[0] = '\0';  
     i = 0;
     while (i < origlen)
     {
          ptr = strstr(original+i, from);
          if (!ptr)
          {
               strcat(newstring,original+i);
               break;
          }
          else
          {
               //this looks extremely ugly and bulky...
               strncat(newstring, original+i, ptr-(original+i));
               strcat(newstring, to);
               i = i + ptr - (original + i) + strlen(from);
          }
     }
     strcat(newstring,"\0");
     return newstring;
}

このコードをより明確かつ/またはより効率的にする方法について誰か提案がありますか? どんなコメントでも大歓迎です。代わりにクラス文字列を使用することを提案しないでください。それはオプションではありません。関数は c-strings で動作する必要があります

4

4 に答える 4

3

おそらくエレガンスと効率を同時に改善するために私が行う1つの改善点は、

  1. 指定された文字列に一致する部分文字列のインデックスを保持する整数の配列を割り当てます。
  2. 文字列をループし、一致するすべての部分文字列を見つけて、それぞれを配列に追加し、必要に応じて配列を再割り当てします (私が推測する STL を使用したくないため、可能であれば を使用します)。std::vector std::list std::deque
  3. 元の文字列の長さと見つかった部分文字列の数に基づいて、変更された文字列に新しいメモリを割り当てます。
  4. 古い文字列と配列を同時に繰り返し、一致しない部分を古い文字列から新しい文字列にコピーします。
  5. 残った穴を交換用の紐で埋めます。

また、関数内でメモリを動的に割り当てる代わりに、呼び出し元が割り当てたバッファと最大バッファ サイズを受け入れるように変更します。このようにして、呼び出し元はメモリの有効期間に完全に責任を負うことができ（必要に応じて自動メモリを利用します）、バッファサイズの計算について心配する必要はありません（呼び出し元に依存します）。

編集：

これが私が作り上げた実装例です。誰かがエラーを見つけた場合はお知らせください。（自分で理解したい場合は、これを読みたくないかもしれません。）

char* strreplace(const char* haystack, const char* needle, const char* replacement) {
    // using deque for pop_front
    std::deque<const char*> positions;
    unsigned int haystacklen    = strlen(haystack),
                 needlelen      = strlen(needle),
                 replacementlen = strlen(replacement);

    for (const char* cur = haystack, *pos = strstr(cur, needle); pos; cur = pos + 1, pos = strstr(cur, needle))
        positions.push_back(pos);

    char* newstr    = new char[haystacklen + replacementlen * positions.size() + 1],
          dst       = newstr;
    const char* src = haystack;

    while (src <= haystack + haystacklen)
        if (!positions.empty() && src == positions.front()) {
            strcpy(dst, replacement);
            dst += replacementlen;
            src += needlelen;
            positions.pop_front();
        } else
            *dst++ = *src++;

    return newstr;
}

delete[]そして、その関数の戻り値を忘れないでください。

最大限の最適化を行わずに効率化を図りました。たとえば、 false のときにwhile実行されるループを作成しpositions.empty()、それが true になったら、ループを終了してstrcpy、残りの部分をまっすぐに実行することができます。これにより、不要な呼び出しを避けることができますpositions.empty()。置換するものが残っていない場合でも、すべての文字が残っているか、まったくありません。しかし、それは小さな問題だと思います。コードは要点を伝えています。

また、以前はすべてのアレイ管理コードを削除していましたが、自分でやりたい場合は簡単です。std::list std::deque

ildjarn がコメントで述べたように、私はメンバーを使用するためlistからに変更しました。彼のコメントによると、 C++11 より前のすべての実装では(通常は ) ではないため、定数時間の方が効率的です。 .dequesizeO(1)O(n)dequesize

于 2012-04-25T01:21:26.283 に答える
0

これは私が作成したバージョンで、ほとんどポインタのみを使用しています（エラーチェックなどは省略されています）（特定の場合に失敗することにも気づきました）：

#include <cstring>
#include <cstdlib>
#include <iostream>

char* replaceSubstring(char *original, char *from, char *to)
{
// This could be improved (I was lazy and made an array twice the size)
    char* retstring = new char[std::strlen(original) * 2];

    int pos = 0;
    for (int i = 0; *(original + i); ++i)
    {   
        if (*(original + i) == *(from)) 
        {
            // Got a match now check if the two are the same
            bool same = true; // Assume they are the same
            for (int j = 1, k = i + 1; *(from + j) && *(original + k); ++j, ++k)
            {
                if (*(from + j) != *(original + k))
                {
                    same = false;
                    break;
                }
            }
            if (same)
            {
                // They are the same now copy to new array
                for (int j = 0; *(to + j); ++j)
                {
                    retstring[pos++] = *(to + j);
                }
                i += std::strlen(from) - 1;
                continue;
            }
        }
        retstring[pos++] = *(original + i);
    }
    retstring[pos] = '\0';
    return retstring;
}

int main()
{
    char orig1[] = "Replace all the places that say all";
    char* r1 = replaceSubstring(orig1, "all", "Replacement");
    std::cout << r1 << std::endl;
    delete [] r1;

    char orig2[] = "XXXXXX with something else XXXXXX";
    char* r2 = replaceSubstring(orig2, "XXXXXX", "hello");
    std::cout << r2 << std::endl;
    delete [] r2;
}
于 2012-04-25T02:25:33.413 に答える
0

説明不要: http://ideone.com/ew5pL

これは醜くてかさばる様子です - 最後に strlen と memcpy 以外の C 関数はありません。

コンパクトでいい感じだと思います。

于 2012-04-25T20:41:12.210 に答える
0

ソリューションの後で newstring のサイズを可能な最大サイズに設定するだけで、カウントを計算するコードの最初の部分を取り除くことができます。

特に：

int newsize = origlen + (strlen(to) - strlen(from)) * origlen/strlen(from);

また、strlen(from) を複数回呼び出す代わりに、それを変数 (例: srtlen_from) に割り当てて、それを使用するだけです。

于 2012-04-25T01:43:50.143 に答える