cplusplus.com表示std::string的结尾“不应被解引用”。

Question

我希望你能为我澄清一些困惑。我正在编写一个函数，用于删除字符串中的重复字符，例如"AB --> "AAABB"。

void remove_dups(std::string& str) { 
    std::string::iterator it = str.begin();
    while (it != str.end()) {
        if (*(it+1) == *it) {
            str.erase(it+1);
        } else {
            ++it;
        }
    }
} 

测试时似乎可以正常工作。但是，我想知道，难道不应该有一个“栅栏问题”吗？当'it'是字符串的结尾时，if语句会查看不存在的下一个字符。根据cplusplus.com的说法，

“超过末尾字符”是一个理论上的字符，它将跟随字符串中的最后一个字符。它不应被引用。” (http://www.cplusplus.com/reference/string/string/end/)

所以我想知道为什么我的函数似乎通过了测试，以及如何以一种优雅的方式重新编写整个函数来解决“栅栏问题”。（请对我温柔点，我是一个新手。）

重写方式如下：

void remove_dups(std::string& str) { 
    std::string::iterator it = str.begin();
    while (it != str.end()) {
        if ((it+1) != str.end() && *(it+1) == *it) {
            str.erase(it+1);
        } else {
            ++it;
        }
    }
} 

看起来不太优雅。

- user3178285

---

@chris 我不认为那会有帮助。看起来这个算法是用来去除重复的连续字符的。 - ta.speot.is

@ta.speot.is，这正是std::unique所做的。 - chris

@chris 当然可以，str.erase(std::unique(str.begin(), str.end()), str.end()); 和 str.resize(std::unique(str.begin(), str.end()) - str.begin()); 应该会产生相同的效果，我认为两者的复杂度都差不多。 - user743382

@hvd，不是真的，如果迭代器不支持operator-，那么一个就行不通。使用erase的主要原因是为了使其看起来类似于擦除-删除惯用法。我没有看到resize这个，但它应该在大部分情况下都能工作。 - chris

@chris 哦，好的，我只考虑了字符串，没有考虑其他容器。这也是为什么我没有在我的答案中看到it-1是一个问题（Jeffrey的答案中的end()-1也是如此）。 （编辑：澄清一下：我知道从迭代器中减去整数与从两个迭代器中减去不同。） - user743382

Answer 1

我想知道为什么我的函数似乎通过了测试。未定义行为并不意味着它不能做你想要的事情。它可能会做你想要的事情，只是出于错误的原因。我猜测未定义行为表现为获取\0字符，这不太可能与字符串中的其他字符相等。

有很多选项，但我个人偏好的方式是：如下重写整个函数以避免栅栏问题。

if (it != str.end()) {
  ++it;
  while (it != str.end()) {
    /* compare *it and *(it-1) */
  }
}

但是请注意，erase需要移动元素。假设您总共删除了20个字符，那么您将把字符串的其余部分向后移动一个字符，这样重复20次。如果您稍微修改一下算法，就不需要这样做：

void remove_dups(std::string& str) { 
  std::string::iterator src = str.begin();
  std::string::iterator dst = str.begin();
  if (src != str.end()) {
    ++src;
    ++dst;
    while (src != str.end()) {
      if (*src != *(src-1)) {
        *dst = *src;
        ++dst;
      }
      ++src;
    }
    str.resize(dst - str.begin());
  }
}

这种方法的好处在于，即使erase将字符串在内存中移动，也能正常工作，这可能会导致迭代器失效。

- user743382

Answer 2

标准允许与最后一个数组元素进行比较，但不允许对其进行解引用操作。因此，您可以比较其地址以验证循环是否应该结束，但不允许读取内容。由于迭代器大多是指针，所以这个规则也适用于字符串、向量等。

另外，请注意，string::erase的非序列版本返回指向被移除元素占用的字符的迭代器，您可以将其用作新的循环迭代器。

- marcinj

Answer 3

我认为最干净的解决方案是在字符串末尾停止（字符串的最后一个字符），因为此时不会执行任何进一步的操作。

因此，while (it != str.end()) 应该改为 while (it != str.end() && it != (str.end() - 1))。

- Shoe

---

如果字符串可能为空，str.end() - 1 将无法工作，而且我没有看到任何迹象表明空字符串是无效的。 - user743382