CODEWITHSUNDEEP
c++arraysvectorstltime-complexity
Ricardo
Ricardo

Reputation: 255

Extract subvector in constant time

I have a std::vector<int> and I want to throw away the x first and y last elements. Just copying the elements is not an option, since this is O(n). Is there something like vector.begin()+=x to let the vector just start later and end earlier? I also tried

items = std::vector<int> (&items[x+1],&items[0]+items.size()-y);

where items is my vector, but this gave me bad_alloc

Upvotes: 1

Views: 455

Answers (3)

davidhigh
davidhigh

Reputation: 15468

The other answers are correct: usually iterators will do.

Nevertheless, you can also write a vector view. Here is a sketch:

template<typename T>
struct vector_view
{
    vector_view(std::vector<T> const& v, size_t ind_begin, size_t ind_end)
        : _v(v)
        , _size(/* size of range */)
        , _ind_begin(ind_begin) {}

    auto size() const { return _size; }

    auto const& operator[](size_t i) const
    {
        //possibly check for input outside range
        return _v[ i + _ind_begin ];
    }

    //conversion of view to std::vector
    operator std::vector<T>() const
    {
        std::vector<T> ret(_size);
        //fill it
        return ret;
    }

private:
    std::vector<T> const& _v;
    size_t _size;
    size_t _ind_begin;
}

Expose further methods as required (some iterator stuff might be appropriate when you want to use that with the standard library algorithms).

Further, take care on the validity of the const reference std::vector<T> const& v; -- if that could be an issue, one should better work with shared-pointers.

One can also think of more general approaches here, for example, use strides or similar things.

Upvotes: 2

eerorika
eerorika

Reputation: 238281

If you only need a range of values, you can represent that as a pair of iterators from first to last element of the range. These can be acquired in constant time.

Edit: According to the description in the comments, this seems like the most sensible solution. If your functions expect a vector reference, then you'll need to refactor a bit.

Other solutions:

If you don't need the original vector, and therefore can modify it, and the order of elements is not relevant, you can swap the first x elements with the n-x-y...n-y elements and then remove the last x+y elements. This can be done in O(x+y) time.

If appropriate, you could choose to use std::list for which what you're asking can be done in constant time if you have iterators to the first and last node of the sublist. This also requires that you can modify the original list but the order of elements won't change.

If those are not options, then you need to copy and are stuck with O(n).

Upvotes: 3

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385088

C++ standard algorithms work on ranges, not on actual containers, so you don't need to extract anything: you just need to adjust the iterator range you're working with.

void foo(const std::vector<T>& vec, const size_t start, const size_t end)
{
    assert(vec.size() >= end-start);
    auto it1 = vec.begin() + start;
    auto it2 = vec.begin() + end;

    std::whatever(it1, it2);
}

I don't see why it needs to be any more complicated than that.

(trivial live demo)

Upvotes: 4

Related Questions