问题是：从给定的字符串中删除指定的字符。
Input: The string is "Hello World!" and characters to be deleted are "lor"
Output: "He Wd!"
解决这一问题涉及两个子部分：
- 确定是否要删除给定字符
- 如果是，则删除该字符
为了解决第一部分，我将要删除的字符读取到std::unordered_map中，即我解析字符串"lor"，并将每个字符插入哈希图中。稍后，当我解析主字符串时，我会查看这个以每个字符为键的哈希图，如果返回的值为非零，那么我会从字符串中删除该字符。
问题1:这是最好的方法吗？
问题2:对于这个问题，哪一个更好？std::map还是std::unordered_map？由于我对订购不感兴趣，所以我使用了unordered_map。但是，创建哈希表的开销是否更高？在这种情况下该怎么办？使用map（平衡树）还是unordered_map（哈希表）？
现在进入下一部分，即从字符串中删除字符。一种方法是删除字符并将数据从该点向后移动一个位置。在最坏的情况下，我们必须删除所有字符，这将需要O（n^2）。
第二种方法是只将所需的字符复制到另一个缓冲区。这将涉及到分配足够的内存来保存原始字符串，并逐个字符地复制，不包括要删除的字符串。尽管这需要额外的内存，但这将是一个O（n）操作。
第三种方法是从第0个位置开始读取和写入，每次读取时递增源指针，仅在写入时递增目标指针。由于源指针总是相同或位于目标指针之前，所以我可以在相同的缓冲区上进行写入。这节省了内存，也是一个O（n）运算。我也在做同样的事情，最后调用resize来删除额外的不必要字符？
这是我写的函数：
// str contains the string (Hello World!)
// chars contains the characters to be deleted (lor)
void remove_chars(string& str, const string& chars)
{
unordered_map<char, int> chars_map;
for(string::size_type i = 0; i < chars.size(); ++i)
chars_map[chars[i]] = 1;
string::size_type i = 0; // source
string::size_type j = 0; // destination
while(i < str.size())
{
if(chars_map[str[i]] != 0)
++i;
else
{
str[j] = str[i];
++i;
++j;
}
}
str.resize(j);
}
问题3：我可以通过哪些不同的方法来改进此功能。还是这是我们能做的最好的事情？
谢谢！
干得好，现在学习标准库算法和boost:
str.erase(std::remove_if(str.begin(), str.end(), boost::is_any_of("lor")), str.end());
假设您正在研究算法，而对库解决方案不感兴趣：
当可能的密钥数量很大时，哈希表是最有价值的，但您只需要存储其中的几个。如果您要从数字序列中删除特定的32位整数，那么您的哈希表是有意义的。但是对于ASCII字符来说，这太过分了。
只需制作一个由256个bool组成的数组，并为要删除的字符设置一个标志。每个输入字符只使用一个表查找指令。哈希映射至少还包含一些计算哈希函数的指令。就空间而言，一旦你把所有的辅助数据加起来，它们可能就不再紧凑了。
void remove_chars(string& str, const string& chars)
{
// set up the look-up table
std::vector<bool> discard(256, false);
for (int i = 0; i < chars.size(); ++i)
{
discard[chars[i]] = true;
}
for (int j = 0; j < str.size(); ++j)
{
if (discard[str[j]])
{
// do something, depending on your storage choice
}
}
}
关于存储选择：根据是否需要保留输入数据，在选项2和选项3之间进行选择。3显然是最有效的，但你并不总是想要一个到位的程序。
这里有一个具有许多优点的KISS解决方案：
void remove_chars (char *dest, const char *src, const char *excludes)
{
do {
if (!strchr (excludes, *src))
*dest++ = *src;
} while (*src++);
*dest = ' 00';
}
您可以在strcspn和strspn之间进行乒乓球，以避免使用哈希表：
void remove_chars(
const char *input,
char *output,
const char *characters)
{
const char *next_input= input;
char *next_output= output;
while (*next_input!=' ')
{
int copy_length= strspn(next_input, characters);
memcpy(next_output, next_input, copy_length);
next_output+= copy_length;
next_input+= copy_length;
next_input+= strcspn(next_input, characters);
}
}