有没有办法在 std::vector 数据的开始和结束处引入透明哨兵？

Question

一些算法（如字典搜索和比较）可以写得更短，无需对数组进行边界检查，特别是当涉及到通过索引比较字符串时。

例如：

    int offset=0;
    for ( ; index–offset >= 0 && *(&index+line)–offset >= 0 
        && text[index-offset ] == text[*(&index+line)-offset ]; ++offset )
        ;

可以缩短为

    int offset=0;
    for ( ;text[index-offset ] == text[*(&index+line)-offset ]; ++offset )
        ;

问题在于，很多地方都有很多这样的边界检查，这使得代码更难阅读。

当然，我可以在数组中添加哨兵，但我只想确保比较会停止；不然我不想看到其他地方的哨兵。所以，我想让它们“透明”。

万一有机会在begin()之前和

end()

处放置一个

sentinel

（不属于向量中数据的值）可以解决问题。当然，我知道这是不可能的，原因有很多：

1. 使用此容器应该处理负索引作为运算符[]的输入
2. 迭代器也将被迫在“数组之前”寻址内存，这是不可能的。
3. 这打破了关于迭代器、容器、begin() 和 end() 的整个想法

那么，实现这一目标最直接的方法是什么？我确信这是编程中的常见技巧，因此应该有一些东西可以简化其语言实现。

当然，这可以很容易解决，涉及另一级间接（另一个索引），但这太昂贵了。

我也会使用带有范围的投影/视图，但我需要具有尚未针对范围实现的执行策略。

是否有一些继承、包装、替换的方法仍然保留在类似数组的容器中（最好是

std::vector

），以便我可以保持大部分代码不变？

Answer 1

没有容器本身支持您想要的功能。但是，没有什么可以阻止您自己编写。您甚至可以（应该）使用现有的容器（如

std::vector

）来处理底层容器功能，允许您的类专注于“透明度”（赋予您的单个类单一责任）。

对我来说，如果你对所有事情都使用迭代器，看起来有些逻辑会很复杂，但这看起来是可能的。我可以为类提供一个函数，该函数接受两个索引（可能为负数），并在索引超出范围或这些索引处的元素相等时返回

true

，而不是依赖迭代器和哨兵。确切的细节可能会发生变化，以符合您实际代码的要求，但这将模拟您建议的哨兵，而不会占用它们占用内存。

---

话虽如此，将其中一个条件从循环条件移至

if

语句不是更简单吗？我还将循环本身移至其自己的函数中，以使代码更易于阅读。 （我还将索引类型从

int

切换为

std::size_t

。这不是必需的，但我建议参数和返回类型之间保持一致。）

std::size_t find_offset(char * text, std::size_t index1, std::size_t index2) {
    // Limit the offset so we do not read past the beginning of the array.
    auto limit = std::min(index1, index2);
    for (std::size_t offset = 0; offset <= limit; ++offset)
        if ( text[index1-offset] == text[index2-offset] )
            return offset;

    // What should happen if no match is found?
    // This matches the loop given in the question.
    return limit + 1;
}

称为

auto offset = find_offset(text, index, *(&index+line));

经验法则：如果您已将循环控制变量的定义移至

for

语句之外，请考虑将循环移至返回循环结束位置的函数中。额外的抽象层可以解决许多问题，有时包括可读性。

Answer 2

如果你想要哨兵，没有什么可以阻止你编写一个容器，用两个额外的元素包装

std::vector

（并通过将底层迭代器偏移适当的量来实现诸如

begin()

/

end()

系列等功能） 。您必须转发

emplace_back()

和

erase()

等等，但仍然比从头开始实现容器要少得多。

C++ 不提供这样的容器，因为没有足够多的人需要它（并且它不能作为

std::vector

的一部分实现，而不会给那些不使用它的人带来成本）。部分原因是，并不总是存在无法呈现的价值。