Is it possible to send part of vector as a vector to a function?

Question

I want to see if it is possible to pass part of vector to a function so that it appears as a normal vector to the function. More importantly, I want this to be done in O(1), constant time. I don't want to iterate the vector to make a new one. In fact, I also want the size of the new vector to change to 40 in the following example.

void func(vector <int> &v){

    //calling index 10  to 50 of v
    func(v[10..50])
}

It's usually done with iterator ranges (see the functions from ``) — πάντα ῥεῖ, May 27 '17 at 11:29
Sending two iterators is the idiomatic way of doing it in C++. — Sergey Kalinichenko, May 27 '17 at 11:34
Iterators as function parameters is not thread safe. Rather send the vector, the upper and lower limits, use mutex to protect the vector. — ark1974, May 27 '17 at 12:15

Steve Townsend · Accepted Answer · 2017-05-27T11:40:13.563

5

Use iterators as the parameters to the range-based function, and pass in the required range. Your code in the function become

funcWithRange(v.cbegin()+10, v.cbegin()+50);

with function signature

void funcWithRange(std::vector<int>::const_iterator first, std::vector<int>::const_iterator last)

This could be generalized by making this a function template with the vector member type as its template parameter, or still further to any container supporting this type of range iteration. As noted in the comments, <algorithm> has many examples of this pattern.

std::distance(first, last); will return the desired altered size. I don't think you can get closer to meeting your requirements without making a physical copy.

edited May 27 '17 at 11:40

answered May 27 '17 at 11:29

Steve Townsend

53,498
9
91
140

I know, but I was wondering if it is possible to do with only one argument – A. Mashreghi May 27 '17 at 11:31
I doubt it, and wonder how that makes it more efficient anyway. I imagine some transformation would have to occur, and you wanted to avoid that. – Steve Townsend May 27 '17 at 11:34
3

@A.Mashreghi Yes, use a `std::pair::iterator,std::vector::iterator>`. – πάντα ῥεῖ May 27 '17 at 11:35

Jesper Juhl · Answer 2 · 2017-05-27T12:01:13.453

3

If you have a vector of say 100 elements

std::vector<int> v(100);

and you want to call void f(std::vector<int> v) with the first 10 elements, simply call the function as

f({v.cbegin(), v.cbegin() + 10});

That will construct a new vector from the two iterators (by copying the elements) and pass the new vector to f.

edited May 27 '17 at 12:01

answered May 27 '17 at 11:34

Jesper Juhl

30,449
3
47
70

2

This solution has the drawback, that the function will no longer operate on the original vector. – πάντα ῥεῖ May 27 '17 at 11:39
This is really interesting, but does this copy the vector? I don't think it works in constant time independent of the length of the range. – A. Mashreghi May 27 '17 at 11:41
1

@A.Mashreghi Yes, this is copying to create a new vector. You can't avoid copying if you require a new vector. This is why iterators are used so much in C++. You need to rethink your requirements. – Blastfurnace May 27 '17 at 11:51
1

@A.Mashreghi Yes, this would create a copy of the subpart. – πάντα ῥεῖ May 27 '17 at 11:51
@πάντα ῥεῖ true. I just wanted to present it as an option. A. Mashreghi yes, it copies. – Jesper Juhl May 27 '17 at 11:52
`std::vector v{100};` will call the constructor taking `std::initializer_list` and construct a vector with size 1, no? – DeiDei May 27 '17 at 11:56

Galik · Answer 3 · 2019-03-07T10:11:01.063

3

There is a means to achieve something similar to this that is being proposed for inclusion in the C++ standard. It is called a span and it operates like a vector in some ways.

#include <gsl/span>

void func(gsl::span<int> sp)
{
    for(auto& i: sp)
        std::cout << i << '\n';
}

int main()
{
    // ...

    std::vector<int> v(100);

    // put something in the vector (numbers 0 - 99)
    std::iota(std::begin(v), std::end(v), 0);

    // wrap the container in a span
    auto sp = gsl::make_span(v);

    // send parts of it to functions
    func(sp.subspan(10, 50));
}

The span presents a window onto the original vector so it is a reference type. It doesn't contain its own data just pointers to the data in the vector. As such they are lightweight and designed to be passed by value.

An implementation of span can be found here: https://github.com/Microsoft/GSL

This is the recommended way of passing contiguous containers in the Best Practices guide by Bjarne Stroustrup and Herb Sutter.

The guidelines can be found here: CppCoreGuidelines.md

edited Mar 07 '19 at 10:11

answered May 27 '17 at 12:27

Galik

47,303
4
80
117

What's the difference from a `std::pair` of two iterators? – πάντα ῥεῖ May 27 '17 at 12:51
@πάνταῥεῖ The `span` is bounds checked and the `API` supposed to be more robust making it hard to obtain an out-of-bounds range. Doing `v.begin() + 50` out of bounds won't trigger an exception it will quietly do undefined behavior. But `sp.subspan(0, 50)` will be checked. – Galik May 27 '17 at 13:50
@Galik If I manipulate the subspan passed to func, does that change the original values in sp? I mean is this a copy or a reference to originial? – A. Mashreghi May 27 '17 at 16:06
1

@A.Mashreghi It is a reference, the changes happen to the original vector – Galik May 27 '17 at 16:10
@A.Mashreghi Otherwise you would have to make a copy which can't happen in `O(1)` – Galik May 27 '17 at 16:11

Is it possible to send part of vector as a vector to a function?

3 Answers3

Linked