c++ - 如何将 `std::lower_bound` 与这个定制容器一起使用？

Question

我想要一个 std::vector<std::vector<T>> 的 wrapper 目的。下面是在Wrapper下实现的几个基本方法

template<class T>
class Wrapper
{
private:
    std::vector<std::vector<T>>& data;
    int totalSize;
    std::vector<int> indicesMap;

public:
    Wrapper(std::vector<std::vector<T>>& input):data(input)
    {
        totalSize = 0;
        for (int i = 0 ; i < data.size() ; i++)
        {
            totalSize += data[i].size();
            indicesMap.push_back(totalSize);
        }
    }

    T operator[](int index)
    {
        int whichVector = std::upper_bound(
            indicesMap.begin(),
            indicesMap.end(),
            index
        ) - indicesMap.begin();

        int i = whichVector == 0 ? index : index - indicesMap[whichVector-1];

        return data[whichVector][i];
    }

    int size()
    {
        return totalSize;
    }
};

这是一个简单的测试

int main()
{
    std::vector<std::vector<int>> x;
    std::vector<int> x1 = {1,2,3};
    std::vector<int> x2 = {10,20,30};
    std::vector<int> x3 = {100,200,300};
    x.push_back(x1);
    x.push_back(x2);
    x.push_back(x3);

    Wrapper<int> w(x);
    std::cout << w[4] << "\n"; // prints 20 as expected

    return 0;
}

我希望能够使用 upper_bound和 lower_bound在对象上 Wrapper .我真的不明白如何为定制对象制作迭代器并且未能实现它，即便如此，我不太确定将 being 和 end 迭代器提供给 lower_bound 是否可行。 .

你能帮我实现upper_bound吗？和 lower_bound对于对象 Wrapper ？

我的目标是能够做到

std::lower_bound(w.begin(), w.end(), object);

Answer 1

您必须为满足概念 ForwardIterator 的包装器创建和实现迭代器.有关如何执行此操作的详细信息，请参阅此主题的答案 How to correctly implement custom iterators and const_iterators? .然后提供包装器的方法，这些方法先返回过去的迭代器，然后返回过去的迭代器(通常它们称为 begin() 和 end() 最好是，但您可以随意调用它们)。

迭代器可以实现为std::pair<size_t,size_t>职位在 data加上引用 data本身正确实现 operator++ .

可选地，为了优化，您可能希望使迭代器满足 RandomAccessIterator概念和std::lower_bound或 std::upper_bound可能会更有效率(当然取决于您如何实现随机访问)。