无需拼接双字符串的C++跨字符串模式搜索及缓冲区处理

这问题我之前做网络数据解析时经常碰到——直接拼接b和p太浪费内存了，尤其是当b已经很大的时候。咱们可以用更聪明的方式实现需求，既不用拼接整个缓冲区，还能尽可能避免b的频繁扩容。

核心思路拆解 #

要实现“不拼接b+p就找到分隔符sep的位置”，关键是处理分隔符跨b和p的情况——毕竟sep可能一部分在b的末尾，另一部分在p的开头。我们可以分两步走：

1. 定位分隔符的位置：

   • 先算出sep的长度sep_len（实际场景里分隔符不会是空串，不过还是做个兼容处理）。
   • 取b的最后min(b.size(), sep_len - 1)个字符（因为如果sep长度是n，最多只需要b的最后n-1个字符就能和p的开头组成完整的sep），和p拼接成一个临时的“候选匹配串”。
   • 在这个候选串里用std::search找sep的位置，再结合b的长度，就能算出b+p中sep的实际结束位置。

2. 迁移内容到b并优化扩容：

   • 如果找到了sep：计算需要从p中迁移到b的长度，先给b预留足够的空间，再把p的对应部分追加到b，最后截断p保留剩余内容。
   • 如果没找到sep：同样先预留空间，把整个p追加到b后清空p。

完整代码实现 #

#include <string>
#include <algorithm>

void process_buffer(std::string& b, std::string& p, const std::string& sep) {
    const size_t sep_len = sep.size();
    if (sep_len == 0) {
        // 分隔符为空的特殊情况，按需处理
        b.append(p);
        p.clear();
        return;
    }

    size_t b_suffix_len = std::min(b.size(), sep_len - 1);
    std::string candidate(b.end() - b_suffix_len, b.end());
    candidate += p;

    auto it = std::search(candidate.begin(), candidate.end(), sep.begin(), sep.end());
    if (it != candidate.end()) {
        // 找到了分隔符，计算在b+p中的结束位置
        size_t match_pos_in_candidate = std::distance(candidate.begin(), it);
        size_t total_match_end = b.size() - b_suffix_len + match_pos_in_candidate + sep_len;

        // 需要从p中迁移的长度：total_match_end - b.size()
        size_t move_len = total_match_end - b.size();

        // 预留空间避免过度扩容
        if (b.capacity() < b.size() + move_len) {
            b.reserve(b.size() + move_len);
        }
        // 迁移p的对应部分到b
        b.append(p.begin(), p.begin() + move_len);
        // 截断p，保留分隔符之后的内容
        p = std::string(p.begin() + move_len, p.end());
    } else {
        // 没找到分隔符，把p全部追加到b
        if (b.capacity() < b.size() + p.size()) {
            b.reserve(b.size() + p.size());
        }
        b.append(p);
        p.clear();
    }
}

关键细节解释 #

• 避免不必要的拼接：我们只拼接b的末尾最多sep_len-1个字符和p，这个临时串的长度最多是(sep_len-1) + p.size()，比直接拼接整个b+p小得多，内存开销可以忽略。
• 优化扩容：在追加内容前调用reserve，让b一次性分配足够的空间，避免多次扩容带来的内存拷贝和碎片。
• 处理跨缓冲区匹配：通过候选串的方式，完美覆盖了sep一部分在b末尾、一部分在p开头的场景，和直接拼接b+p找结果完全一致，但效率更高。

内容的提问来源于stack exchange，提问作者Uprooted