How to use `std::lower_bound` with this custom-made container?

Question

I would like a wrapper for a std::vector<std::vector<T>> object. Here are a few basic methods implemented under 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;
    }
};

Here is a simple test

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;
}

I would like to be able to use upper_bound and lower_bound on the object Wrapper. I don't really understand how to make iterators to custom-made objects though and fail to implement that and even then, I am not quite sure it is feasible to just give the being and end iterators to lower_bound.

Can you help me to implement upper_bound and lower_bound for the object Wrapper?

My goal would be to be able to do

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

I have a function that is aimed to work on `std::vector` and on `std::vector>`. The goal of the wrapper is to allow to template this function and use the STL function `lower_bound`, `upper_bound` and the methods `erase`, `insert` as well as the `operator[]` without having to deal with the underlying complication of the data structure. Does it sound like a very bad idea? @RichardHodges — Remi.b, Apr 10 '18 at 19:43
@Slava They are STL algorithms to perform binary search (in sorted arrays) . The functions take ForwardIt as input and output ForwardIt. Why do you think I misunderstand how they work? My goal is to run something like `std::lower_bound(w.begin(), w.end(), object);`, where `w` is the `Wrapper`. Does it make sense? — Remi.b, Apr 10 '18 at 19:58
I take it back, I misread your existing usage of `upper_bound` — Slava, Apr 10 '18 at 19:58
No worries. As both you and Richard get a hard time with my question, I suspect it is my fault. Is the question clearly defined now? — Remi.b, Apr 10 '18 at 20:00
That looks a bit like a `std::deque`. Are you sure `srd::deque` won't satisfy your needs? Anyway, doing a standard binary search on your data structure will not be optimal; you'd do better to first binary search for the vector holding the value, and then binary search that vector for the value. — rici, Apr 10 '18 at 21:14
No, I don't think it would, although I understand your suggestion. The point of the wrapper is that `data` is a reference to the original data. I did not want to have to copy the input vector over but just to wrap it for a number of operations. — Remi.b, Apr 10 '18 at 21:17
@remi: I was referring to the original "vector of vector s" object, which looks to me something like a `std::deque`. The possible difference is that the individual vectors in the `std::deque` are all the same size, which simplifies some operations; in particular, indexing is O(1) rather than O(log N). But I understand that it might not help you; it was just a thought. The advantage is that `std::deque` already has iterators. I'd suggest looking at an implementation of that to see how it's done, but I've yet to find a standard library implementation optimized for ease of understanding. — rici, Apr 10 '18 at 22:46

Slava · Answer 1 · 2018-04-10T20:12:32.757

You have to create and implement iterators for your wrapper that satisfy concept ForwardIterator. Details on how to do that can be found in answers to this subject How to correctly implement custom iterators and const_iterators?. Then provide methods of your wrapper that return first and behind the past iterator (usually they called begin() and end() and they better be but you can call them whatever way you want).

Iterator can be implemented as std::pair<size_t,size_t> with positions in data plus reference to data itself with proper implementation of operator++.

Optionally for optimization you may want to make your iterator to satisfy RandomAccessIterator concept and std::lower_bound or std::upper_bound could be more efficient (depends on how you implement random access of course).

How to use `std::lower_bound` with this custom-made container?

1 Answers1