CODEWITHSUNDEEP
c++c++11vectorstdstdvector
Surbhi Jain
Surbhi Jain

Reputation: 369

Error while concatenating a vector to itself in c++

I am simply trying to concatenate a vector to itself but the following code is not working and I am not able to find the issue. If my input vector is {1,2,1}, the o/p I am getting is {1,2,1,1,16842944,1}. Please tell where I am wrong. The output I want is [1,2,1,1,2,1]

 vector<int> getConcatenation(vector<int>& nums) {
        
        int size=nums.size();
        auto itr=nums.begin();

        while(size--)
        {

            nums.push_back(*itr);
             itr++;
        }
        
        return nums;      
    }

Upvotes: 0

Views: 162

Answers (2)

Pete Becker
Pete Becker

Reputation: 76245

The problem, as has been thoroughly pointed out, is that the vector reallocates its storage while the modifications are being done. There are at least three general approaches to this.

First, use an index instead of an iterator:

vector<int> getConcatenation(vector<int>& nums) {
    int size = nums.size();
    for (int i = 0; i < size; ++i)
        nums.push_back(nums[i]);
    return nums;
}

Second, use an iterator but ensure that the vector doesn't have to reallocate:

vector<int> getConcatenation(vector<int>& nums) {
    int size = nums.size();
    nums.reserve(2 * size);
    auto itr = nums.begin();
    while (--size)
        nums.push_back(*itr++);
    return nums;
}

(and that approach includes less labor-intensive things like using a builtin algorithm that copies based on iterators)

Third, unless you have to modify the input argument, just build a vector that's the right size and copy into it:

vector<int> getConcatenation(const vector<int>& nums) {
    vector<int> result(2 * nums.size());
    std::copy(nums.begin(), nums.end(), result.begin());
    std::copy(nums.begin(), nums.end(), result.begin() + nums.size());
    return result;
}

Upvotes: 1

user12002570
user12002570

Reputation: 1

In your original program push_back invalidates the iterators and using those invalidated iterators can lead to undefined behavior.

One way to solve this would be to use std::copy_n with std::vector::resize as shown below:

 vector<int> getConcatenation(vector<int>& nums) {
        
       std::vector<int>::size_type old_Size = nums.size();
       nums.resize(2 * old_Size);
       std::copy_n(nums.begin(), old_Size, nums.begin() + old_Size);
        
        return nums; //NO NEED for this return since the function took vector by reference and so the change is already reflected on passed vector     
    }

Also you would need to add #include <algorithm> for std::copy_n.

Note that since your function takes the vector be reference, there is no need to return nums because the changes you do on nums is already reflected on the original vector. So you can use void as the return type of the function and then remove the return statement.

Upvotes: 2

Related Questions