How to split vector according to indices given in another vector?

Question

I have a source std::vector<double>, which I'd like to split according to indices contained in std::vector<int>. The split is inclusive, and start of next slice should start where previous left off, starting from start of the source vector.

For example:

{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9 } -> source
{2, 4, 7 } -> split indices

and after applying the function it should produce:

{1.1, 2.2, 3.3}
{4.4, 5.5} 
{6.6, 7.7, 8.8}

I have this which won't give me the third vector and so on:

vector<double> nets{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9 };
vector<int> ends{2, 4, 7 };

vector<vector<double>> periodnumbers;
vector<double> numbers;

for (int i = 0; i < nets.size(); i++)
{
    double temp;
    temp = nets[i];
    numbers.push_back(temp);
    for (int j = 0; j < ends.size(); j++)
    {
        if (i == ends[j])
        {
            periodnumbers.push_back(numbers);
            numbers.clear();
        }
    }
}

Answer 1

I propose the following code which is much simpler and easier to understand

#include <iostream>
#include <vector>

using namespace std;

int main(){
  vector<double> nets{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9 };
  vector<int> ends{2, 4, 7 };
  ends.push_back(nets.size()-1);
  vector<vector<double>> periodnumbers;
  vector<double> numbers;
  int j=0;
  int coming_split_index=ends[j];
  for (int i = 0; i < nets.size(); i++){
     if(i<=coming_split_index){
       numbers.push_back(nets[i]);
     }else{
         j++;
         coming_split_index=ends[j];
         periodnumbers.push_back(numbers);
         numbers.clear();
         i--;

        /*when the index i reaches the coming index the corresponding 
        *value won't be added to any subvector because It will skip the 
        *pervious instruction for this reason I decrement the counter i so 
        *that it repeats it and the next time the one in the previous will 
        *be executed
        */

        }
   }

this displays your results

 1.1 2.2 3.3 
 4.4 5.5 
 6.6 7.7 8.8 

Answer 2

If we can assume that ends is sorted in ascending order and the values in ends are never larger than the size of nets allows them to be, then there is a rather simple function that can give you the desired result:

template<typename T>
std::vector<std::vector<T>> split(const std::vector<T>& nets, const std::vector<int>& ends)
{
    std::vector<std::vector<T>> result;
    int previous_offset = 0;
    for (int i : ends)
    {
        const std::vector<T> piece(nets.begin() + previous_offset, nets.begin() + i + 1);
        previous_offset = i;
        result.push_back(piece);
    }
    return result;
}

The whole program with your example data could look like that:

#include <iostream>
#include <vector>

// function from above
template<typename T>
std::vector<std::vector<T>> split(const std::vector<T>& nets, const std::vector<int>& ends)
{
    std::vector<std::vector<T>> result;
    int previous_offset = 0;
    for (int i : ends)
    {
        const std::vector<T> piece(nets.begin() + previous_offset, nets.begin() + i + 1);
        previous_offset = i;
        result.push_back(piece);
    }
    return result;
}


int main()
{
    // input data
    std::vector<double> nets{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9 };
    std::vector<int> ends{2, 4, 7 };
    // variable that will hold the result
    std::vector<std::vector<double>> periodnumbers;

    // This is where the work happens.
    periodnumbers = split(nets, ends);

    // Write result to standard output.
    std::cout << "There are " << static_cast<int>(periodnumbers.size()) << " pieces:" << std::endl;
    for (auto vec : periodnumbers)
    {
        std::cout << "Next piece is: ";
        for (auto elem: vec)
        {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

The output will be:

There are 3 pieces:
Next piece is: 1.1 2.2 3.3 
Next piece is: 3.3 4.4 5.5 
Next piece is: 5.5 6.6 7.7 8.8

Answer 3

There is an error in if(i == ends[i])

One option is to use another variable.

vector<double> nets{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9 };
vector<int> ends{2, 4, 7};

vector<vector<double>> periodnumbers;
vector<double> numbers;
int j=0;
for (int i = 0; i < nets.size(); i++)
{
    double temp;
    temp = nets[i];
    numbers.push_back(temp);
    //cout<<numbers[i]<<endl;

    if (i == ends[j])
    {
        //cout<<i<<"  "<<nets[i]<<endl;
        periodnumbers.push_back(numbers);
        numbers.clear();
        j++;
        //break;
    }
    //cout<<numbers[i]<<endl;

    }
    cout<<"Size"<<periodnumbers.size()<<endl;
    for(int i=0;i<periodnumbers.size();i++){
        for(int j=0;j<periodnumbers[i].size();j++){
            cout<<periodnumbers[i][j]<<" ";
        }
        cout<<endl; 
    }
    return 0;
}

Answer 4

There are a lot of details that I'm not sure you've considered. My answer is tweakable.

In particular, I would prefer WEIRD_OFFSET to be 0.

#include <cassert>
#include <iostream>
#include <vector>

using std::cout;
using std::vector;


const bool ONLY = true;
const bool BEFORE_FIRST = true;
const bool AFTER_LAST = true;

const bool ALLOW_EMPTY = true;
const size_t WEIRD_OFFSET = 1;

template<class T>
vector<vector<T>> frob(const vector<T>& nets, const vector<int>& ends)
{
    vector<vector<T>> rv;
    if (ends.empty())
    {
        if (ONLY)
        {
            if (ALLOW_EMPTY || !nets.empty())
                rv.push_back(nets);
        }
    }
    else
    {
        if (BEFORE_FIRST)
        {
            auto bi = 0;
            auto ei = ends[0] + WEIRD_OFFSET;

            assert (0 <= bi && bi <= ei && ei <= nets.size());
            auto b = nets.begin() + bi;
            auto e = nets.begin() + ei;
            if (ALLOW_EMPTY || b != e)
                rv.push_back(vector<T>(b, e));
        }
        for (size_t i = 0; i < ends.size() - 1; ++i)
        {
            auto bi = ends[i] + WEIRD_OFFSET;
            auto ei = ends[i+1] + WEIRD_OFFSET;

            assert (0 <= bi && bi <= ei && ei <= nets.size());
            auto b = nets.begin() + bi;
            auto e = nets.begin() + ei;
            if (ALLOW_EMPTY || b != e)
                rv.push_back(vector<T>(b, e));
        }
        if (AFTER_LAST)
        {
            auto bi = ends.back() + WEIRD_OFFSET;
            auto ei = nets.size();

            assert (0 <= bi && bi <= ei && ei <= nets.size());
            auto b = nets.begin() + bi;
            auto e = nets.begin() + ei;
            if (ALLOW_EMPTY || b != e)
                rv.push_back(vector<T>(b, e));
        }
    }
    return rv;
}

int main()
{
    vector<double> nets{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9 };
    vector<int> ends{2, 4, 7};

    vector<vector<double>> periodnumbers = frob(nets, ends);
    for (const auto& v : periodnumbers)
    {
        for (const auto& i : v)
        {
            cout << i << ' ';
        }
        cout << '\n';
    }
    cout << std::flush;
}

This produces:

1.1 2.2 3.3 
4.4 5.5 
6.6 7.7 8.8 
9.9 

Answer 5

Bad algorithm

Even if it worked, it is doing too many unnecessary operations. Starting from looping over all elements, ending with push_backing, instead of reserving/resizing.

Better algorithm

Lets assume ends is sorted. Then one can just take two "sliders", and keep moving them. The left slider starts on start of the source vector, and the right one starts on the first end. As algorithm progresses, it copies current range inside sliders, moves left slider to right slider, and right slider becomes next end.

#include <vector>
#include <algorithm>

std::vector<std::vector<double>> split_ends(const std::vector<double>& source, const std::vector<int>& ends) {
    std::vector<std::vector<double>> result;
    result.reserve(ends.size());
    auto anchor_front = source.begin();
    for (auto one_end: ends) {
        auto anchor_end = std::next(source.begin(), one_end + 1);
        result.emplace_back(anchor_front, anchor_end);
        anchor_front = anchor_end;
    }

    return result;
}

#include <iostream>

void print(const std::vector<double>& v)
{
    for (auto x: v) {
        std::cout << x << ' ';
    }
}

int main() {
    std::vector<double> nets{1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9};
    std::vector<int> ends{2, 4, 7};

    auto splitted = split_ends(nets, ends);
    for (const auto& v: splitted) {
        print(v);
        std::cout << '\n';
    }
}

Demo on Wandbox.

Output:

1.1 2.2 3.3 
4.4 5.5 
6.6 7.7 8.8 

---

The algorithm above assumes ends is sorted and doesn't contain out of range indices. If a copy is not needed, one might just save the endpoints iterators, and perform changes on the source directly.