有没有一种方法可以降低C++代码中字符串操作的空间利用率并潜在地提高时间性能

Question

我正在C++中为我的任务编写一个字符串操作代码，其中我必须在字符串中找到一个子字符串，并将其替换为基于其他输入的新计算序列(这里是字符串向量"patterns")。我一直在试图找到一种更好的方法来操作字符串，以提高效率(降低空间成本，并可能进一步降低时间复杂性)。这是我迄今为止所做的一个示例(很抱歉，如果字符串看起来有点奇怪，这是我目前能想到的最好的简单示例)：

// some input variables
std::string& originalString ("__  BB  ++  AA  __  AA  __  CC  __  DD");
std::map<std::string, std::vector<std::string>> patternMap = {
{"AA", {"aaa","AAA"}}, 
{"BB", {"bbb","BBB"}},
};
std::size_t location = 0;
while ((location = originalString.find("__", location)) != std::string::npos) {
const std::string subString = originalString.substr(location+4, location+6);
std::map<std::string, std::vector<std::string>>::iterator patternsIterator = patternMap.find(subString);
if (patternsIterator != patternMap.end()) {
const std::vector<std::string> patterns = patternsIterator -> second;
std::string alternateSubString("*");
for (const std::string& item : patterns) {
alternateSubString.append(item + "__" );
}
alternateSubString.replace(alternateSubString.size() - 5, 5,"*");
originalString.replace(location+4, 2, alternateSubString);
location += alternateSubString.size();
}
++location;
}// Expected  value of the original string should change to: "__  *bbb__BBB*  ++  AA  __  *aaa__AAA*  __  CC  __  DD"

''

有没有关于更好的方法的提示，也许可以去掉变量alternateSubString？尝试在这里实现一些空间/时间优化。

Answer 1

您的算法似乎是：

• 扫描字符串，直到找到下一个__。

• 当找到下一个单词(例如"BB")时，通过使用patternMap中的单词向量构建新字符串来替换

• 这个单词向量包括将在patternMap中找到的每个单词与__连接起来，并且所构建的整个替换字符串以*作为前缀和后缀。(例如{"bbb","BBB"}＝>"*bbb__BBB*")

反馈

您的实现有几个"；回溯"；使用CCD_ 9方法来掩盖在初始替换循环期间所犯的错误。

它还有一些硬编码的长度值，这些值假定令牌之间的间距是一致的。所有这些都让阅读变得有点困难。

CCD_ 10将比CCD_。由于您不需要枚举顺序，因此可以使用unordered_map。如果地图的大小真的很小，这是一个微观优化。

我建议将初始字符串读取为令牌，并跟踪下一个令牌是否需要用patternMap中的单词替换。

考虑一下：

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
typedef unordered_map<string, vector<string>> PatternMap;

// getNext returns a pair of strings:
// The leading whitespace preceeding a word and the word itself
pair<string, string> getNext(const string& s, size_t& location);
// makeMagicWord converts a vector of words 
// into the associated magic replacement pattern
// e.g. {"AA", "BB", CC"} => "*AA__BB__CC*"
string makeMagicWord(const vector<string>& vec);
string ApplyPatterns(const std::string& original, const PatternMap& patterns)
{
string newString;
size_t location = 0;
bool replacing = false;
while (true) {
auto p = getNext(original, location);
string whitespace = p.first;
string token = p.second;
newString += whitespace;
if (token.empty()) {
break;
}
if (replacing) {
auto itor = patterns.find(token);
if (itor != patterns.end()) {
token = makeMagicWord(itor->second); // itor->second = patterns[token]
}
replacing = false;
}
else if (token == "__") {
replacing = true;
}
newString += token;
}
return newString;
}

上面的代码使用辅助函数读取空白/单词标记，根据需要应用替换，并使用另一个辅助函数来生成替换单词。这两个助手函数的实现如下：

然后我们的两个助手的实现如下：

pair<string, string> getNext(const string& s, size_t& location) {
string whitespace, token;
// consume leading whitespace
while (location < s.size() && ::isspace(s[location])) {
whitespace += s[location];
location++;
}
// consume the next token
while (location < s.size() && !::isspace(s[location])) {
token += s[location];
location++;
}
return { whitespace, token };
}
string makeMagicWord(const vector<string>& vec) {
std::string s = "*";
for (size_t i = 0; i < vec.size(); i++) {
s += ((i > 0) ? "__" : "");
s += vec[i];
}
s += "*";
return s;
}

让我们测试一下：

int main() {
string originalString("__  BB  ++  AA  __  AA  __  CC  __  DD");
unordered_map<std::string, std::vector<std::string>> patternMap = {
{"AA", {"aaa","AAA"}},
{"BB", {"bbb","BBB"}}};
string replacement = ApplyPatterns(originalString, patternMap);
cout << originalString << endl;
cout << replacement << endl;
return 0;
}

运行时，上面打印出：

__  BB  ++  AA  __  AA  __  CC  __  DD
__  *bbb__BBB*  ++  AA  __  *aaa__AAA*  __  CC  __  DD