在 C++ 中获取向量中项目最后索引的最快方法？

Question

假设您有一个整数向量，未排序且包含多个重复项，如下所示：

vector<int> myVec{1, 0, 0, 0, 1, 1, 0, 1,0,0}

除了从末尾循环遍历之外，获取 1 的最后一个索引（在此示例中为 8）的最快方法是什么？

如果向量包含除 0 和 1 之外的其他项目，这会有所不同吗？

在 C++ 中执行此操作的最快方法是什么？ L.E。我已经看到了重复的主题建议，但即使它部分解决了我正在寻找的问题，这与向量中的最小元素无关，所以我保留这个问题，也许它也会帮助其他人。

Answer 1

我能想到的唯一更快的方法是在填充向量时保存最后一个索引...这会增加插入时间，但访问速度会更快。

如果这对您的用例来说是可以接受的，您可能还需要考虑向量中唯一值的数量，在您的示例中这是可行的，如果大多数值都是唯一的，您会很快增加内存使用量。

如果您想这样做，您可能想要继承 std::vector 并实现您自己的插入和构造函数。

Answer 2

使用std::max_element 和反向迭代器。那就是循环遍历向量。如果是unsorted，没有更快的方法了。

Answer 3

取决于您是否受困于 vector<int>。如果你可以用 bitset 或 unsigned int 存储位，那么你可以通过按位运算找到最正确的设置位：Efficient bitwise operations for counting bits or find the right|left most ones

在 C++ 中获取向量中项目最后索引的最快方法？

Fastest way for getting last index of item in vector in C++?

c++

vector