Как разделить вектор по индексам, указанным в другом векторе?

Question

У меня есть источник std::vector<double>, который я хотел бы разделить в соответствии с индексами, содержащимися в std::vector<int>. Разделение включительно, и начало следующего среза должно начинаться там, где остановился предыдущий, начиная с начала исходного вектора.

Например:

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

и после применения функции должно получиться:

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

У меня есть это, которое не даст мне третий вектор и так далее:

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

Я предлагаю следующий код, который намного проще и понятнее

#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
        */

        }
   }

это показывает ваши результаты

 1.1 2.2 3.3 
 4.4 5.5 
 6.6 7.7 8.8 

Answer 2

Если мы можем предположить, что ends отсортировано в порядке возрастания, а значения в ends никогда не превышают размер nets, то есть довольно простая функция, которая может дать вам желаемый результат:

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;
}

Вся программа с данными вашего примера может выглядеть так:

#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;
}

Вывод будет:

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

Плохой алгоритм

Даже если это сработало, оно выполняет слишком много ненужных операций. Начиная с цикла по всем элементам, заканчивая push_back ing, вместо резервирования / изменения размера.

Лучший алгоритм

Предположим, что ends отсортировано. Тогда можно просто взять два «ползунка» и продолжать их перемещать. Левый ползунок начинается с начала исходного вектора, а правый - с первого конца. По мере выполнения алгоритма он копирует текущий диапазон внутри ползунков, перемещает левый ползунок в правый ползунок, и правый ползунок становится следующим концом.

#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';
    }
}

Демонстрация на Wandbox .

Выход:

1.1 2.2 3.3 
4.4 5.5 
6.6 7.7 8.8 

---

Приведенный выше алгоритм предполагает, что ends отсортировано и не содержит индексов вне диапазона. Если копия не нужна, можно просто сохранить итераторы конечных точек и напрямую внести изменения в источник.

Answer 4

Есть много деталей, которые я не уверен, что вы рассмотрели. Мой ответ настраиваемый.

В частности, я бы предпочел, чтобы WEIRD_OFFSET было равно 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;
}

Это производит:

1.1 2.2 3.3 
4.4 5.5 
6.6 7.7 8.8 
9.9 

Answer 5

Ошибка в if(i == ends[i])

Один из вариантов - использовать другую переменную.

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;
}