How to insert multiple elements in the vector at different positions using iterator?

Question

I want to write a function that changes the vector [2, 1, 4, 0, 5] to

[2, 2, 1, 4, 4, 4, 4, 5, 5, 5, 5, 5]

I could do it by popping the vector into an array and then pushing the elements back to the vector.

How can I use insert to do it? Can I modify the following program? What is the most efficient way?

void timesDuplicates(vector<int>& a) 
{
    int s = a.size(), count = 0;
    for(int i = 0; count < s ; i+=a[i], count++) {
        if(a[i] == 0) continue;
        a.insert(a.begin()+i, a[i], a[i]); 
    }
}

This program inserts but never erases. It cannot possibly transform `[2, 1, 4, 0, 5]` into `[2, 2, 1, 4, 4, 4, 4, 5, 5, 5, 5, 5]`, as the zero element will remain. — Igor Tandetnik, Jun 30 '19 at 00:11
Also, it inserts too many copies. One copy of the element with value `x` is already present; you only need to insert `x-1` more copies. — Igor Tandetnik, Jun 30 '19 at 00:14
`void timesDuplicates(vector& a) { int s = a.size(), count = 0; for(int i = 0; count < s ; count++) { if(a[i] == 0) { a.erase(a.begin()+i); continue; } a.insert(a.begin()+i, a[i]-1, a[i]); i += a[i]; } }` — user3112666, Jun 30 '19 at 17:38

JeJo · Answer 1 · 2019-06-30T01:15:27.747

How can I use insert to do it? Can I modify the following program?

Regarding efficiency, your vector might undergo several reallocations on each time when insertion happens, as in provided code no memory has been std::vector::reserve ed, even it could have been done by summing up the elements. Like @IgorTandetnik pointed out, transforming the passed vector, wouldn't be possible as well.

The easiest way you could do is, create a new vector in which simply std::vector::insert elements as per the number of elements exist in the passed vector.

Following is an example code. (See Live)

#include <iostream>
#include <vector>
#include <numeric>  // std::accumulate

std::vector<int> timesDuplicates(const std::vector<int>& vec)
{
    std::vector<int> result;
    // reserve the amount of memory for unwanted reallocations
    result.reserve(std::accumulate(std::cbegin(vec), std::cend(vec), 0));
    // you do not need to check element == 0 here
    // as std::vector::insert(end, 0, 0) will insert nothing
    for (const int element : vec) result.insert(result.end(), element, element);
    // return the result
    return result;
}

int main()
{
    const auto result{ timesDuplicates({ 2, 1, 4, 0, 5 }) };
    for (const int ele : result) std::cout << ele << " ";
    return 0;
}

Or if you do not believe in NRVO or copy elision to happen, pass the vector result as a parameter(ref) to the function, after reserving the memory that it needs.

#include <iostream>
#include <vector>
#include <numeric>  // std::accumulate

void timesDuplicates(
    const std::vector<int>& vec,
          std::vector<int>& result)
{
    for (const int element : vec)
        result.insert(result.end(), element, element);
}

int main()
{
    const std::vector<int> vec{ 2, 1, 4, 0, 5 };
    std::vector<int> result;
    result.reserve(std::accumulate(std::cbegin(vec), std::cend(vec), 0));
    timesDuplicates(vec, result);
    for (const int ele : result) std::cout << ele << " ";
    return 0;
}

seccpur · Answer 2 · 2019-06-30T02:26:25.683

Try this snippet with recursion. Since you are popping and pushing into a new temporary vector, push_back will suffice ( insert will require you to locate new insert positions)

void timesDuplicates(vector<int>& vec, int idx = 0)
{
    static vector<int> result;    
    int v = vec[idx];              // get value
    for (int i = 0; i < v; i++)    // multiply value
    {
        result.push_back(v);   // push value to temp vector (result)
    }    
    if (idx == vec.size() - 1) {   // border condition
        vec.swap(result);      // swap result
        return;                
    }    
    timesDuplicates(vec, ++idx);   // increment index   
}

void main()
{
    vector<int> vec = { 2, 1, 4, 0, 5 };
    timesDuplicates(vec);
    for (auto e : vec)
        cout << e << " ";
    cout << "\n";
}

How to insert multiple elements in the vector at different positions using iterator?

2 Answers2