CODEWITHSUNDEEP
c++vectoriterator
Syfu_H
Syfu_H

Reputation: 615

How can I print a vector in a recursive function?

I have a problem here: I am to write a function that prints the elements of a vector recursively so no loop is allowed.

I tried this code but it crashes at runtime:

void print(const std::vector<int> ivec, std::vector<int>::const_iterator it) {
    if (it == ivec.end())
        return;
    std::cout << *it++ << std::endl;
    print(ivec, it);
}

int main(){

    vector<int> v{
        5, 7, 77, 23, 10, 81
    };

    print(v, v.begin());
}

If I run the program I get the assertion dialog!?

Upvotes: 1

Views: 4065

Answers (5)

Durval Carvalho
Durval Carvalho

Reputation: 195

If you just need to print the vector, I think a much more elegant solution would be to use iterators.

#include <iostream>
#include <vector>

using namespace std;

void print_vector(vector<int>::iterator it, const vector<int>::iterator &end)
{
    if(it == end) {
        cout << '\n';
        return;
    }

    cout << *it << " ";
    print_vector(++it, end);
}

int main() {

    vector<int> v = {1,2,3,4,5,6,7,8,9};
    print_vector(v.begin(), v.end());

    return 0;
}

If you want to reuse the function with other structures (perhaps to impress a friend or a teacher) you can use the templates.

#include <iostream>
#include <set>
#include <vector>

using namespace std;

template<class TContainer>
void print_structure(typename TContainer::iterator it, const typename TContainer::iterator end)
{
    if(it == end) {
        cout << '\n';
        return;
    }

    cout << *it << " ";
    print_structure<TContainer>(++it, end);
}

int main() {

    vector<int> vi = {1,2,3,4,5,6,7,8,9};
    print_structure<vector<int>>(vi.begin(), vi.end());


    vector<double> vd = {1.2, 3.4, 5.6, 7.8, 9.0};
    print_structure<vector<double>>(vd.begin(), vd.end());

    set<int> si = {10, 10, 10, 10, 20, 20, 20, 20, 30, 30, 30};
    print_structure<set<int>>(si.begin(), si.end());

    set<double> sd = {10.10, 10.10, 20.20, 20.20, 30.30, 3.0};
    print_structure<set<double>>(sd.begin(), sd.end());

    return 0;
}

Does it look like a bazooka to kill mosquitoes? Sure it is! But it's pretty crazy yeah?!

Upvotes: 0

Gardener
Gardener

Reputation: 2660

No need to pass in two arguments to the print function. If the vector is zero-length, print nothing.

if the vector is length of 1, print that element.

if the vector is of length greater than 1, then print a smaller vector (recursively) that does not include the last character, and then print the last character.

yes, this will create a copy of the vector for each recursion, but I guess that feels more like recursion to me. Incrementing a pointer on each loop does not feel like recursion.

#include <iostream>
#include <vector>

void print(const std::vector<int> vec) {
    if (!vec.size())
        return; 
    else {
        print(std::vector<int>(vec.begin(), vec.end() - 1));
        std::cout << " " << *(vec.end() - 1);
    }
}

int main(){

    std::vector<int> v{
            5, 7, 77, 23, 10, 81
    };

    print(v);
}

Upvotes: 0

Raindrop7
Raindrop7

Reputation: 3911

You have to pass the vector by reference so that to avoid multiple copies thus the iterator is guaranteed to be compared with the iterators of the same vector only not with others':

void print(const std::vector<int>& ivec, std::vector<int>::const_iterator it) {
    if (it == ivec.end())
        return;
    std::cout << *it++ << std::endl;
    print(ivec, it);
}

int main(){
    vector<int> v{
        5, 7, 77, 23, 10, 81
    };

    print(v, v.begin()); // ok

    vector<int>::iterator it = v.begin();
    auto v2{ v };

    if (it == v.begin())
        cout << "it = v.begin()" << endl;
    if (it == v2.begin()) // causes crash
        cout << "it =v2.begin()" << endl;
}

Upvotes: 0

Sam Varshavchik
Sam Varshavchik

Reputation: 118330

void print(const std::vector<int> ivec, std::vector<int>::const_iterator it) {

The ivec parameter is passed by value. Both of these parameters are passed by value. Passing by value by means that inside the function these are copies of the original parameters.

Your main() calls this recursive function passing it its vector and the beginning iterator of its vector. However because all parameters are passed by value, each recursive iteration of the function compares the iterator to the end() of a completely different vector. Undefined behavior.

You obviously forgot to pass the vector by reference. The first parameter to should be const std::vector<int> &ivec.

Upvotes: 3

Alecto
Alecto

Reputation: 10740

When you call print, you pass the vector by value. This means that it creates an entirely new vector each time, but the iterator still comes from the original vector. Because the iterator comes from a different vector, the test it == ivec.end() is always going to fail.

We can fix this just by passing ivec by const reference:

void print(const std::vector<int>& ivec, std::vector<int>::const_iterator it) 
{
    if (it == ivec.end())
        return;
    std::cout << *it++ << std::endl;
    print(ivec, it);
}

And the code works fine!

Upvotes: 1

Related Questions