C ++ Разделить вектор векторов, используя <algorithm> - PullRequest
Новая
       19

C ++ Разделить вектор векторов, используя <algorithm>

2 голосов
/ 02 апреля 2020

Предположим, у вас есть двумерный вектор, определенный следующим образом: 

std::vector<vector<int>> v

и представляющий собой матрицу: 

1 1 0 1 3
0 4 6 0 1
5 0 0 3 0
6 3 0 2 5

Я хочу стабильное разбиение (скажем, с помощью предиката el! = 0) это матрица, но по всем направлениям. Это означает, что я хочу получить: 

1 1 6 1 3     0 0 0 0 0      1 1 1 3 0     0 1 1 1 3
5 4 0 3 1     1 1 0 1 3      4 6 1 0 0     0 0 4 6 1
6 3 0 2 5     5 4 0 3 1      5 3 0 0 0     0 0 0 5 3
0 0 0 0 0     6 3 6 2 5      6 3 2 5 0     0 6 3 2 5
 (down)         (up)          (right)       (left)

Для двух направлений это можно сделать очень просто, перебирая внешний вектор и разбивая внутренние векторы (по порядку или в обратном порядке). Однако для других направлений я не знаю, как сделать то же самое.

Есть ли способ добиться этого с помощью std::stable_partition. Может быть, есть другая структура данных (которая поддерживает индексирование как векторы), которая позволит мне сделать это более легко?
Если у меня есть возможность реализовать это на пустом месте, есть ли стандартный или рекомендуемый способ сделать это?

Ответы [ 2 ]

2 голосов
/ 02 апреля 2020

С range-v3 вы можете сделать: 

const std::vector<std::vector<int>> v = /*..*/;
auto is_zero = [](int e){ return e == 0; };
auto right = v;

for (auto& row : right) {
    ranges::stable_partition(row | ranges::view::reverse, is_zero);
}
print(right);

auto top = v;
for (std::size_t i = 0; i != v[0].size(); ++i) {
    auto col_view = top | ranges::view::transform([i](auto& row)-> int& { return row[i]; });    

    ranges::stable_partition(col_view, is_zero);
}
print(top);

Демо

2 голосов
/ 02 апреля 2020

Вам не нужно писать собственную реализацию алгоритма. Итераторы - это точка настройки, когда вы хотите использовать существующий алгоритм для пользовательской структуры данных. К сожалению, написание собственного итератора требует довольно много шаблонов. Я думаю, что boost может помочь, но если вы хотите остаться с тем, что предлагает стандартная библиотека, то, насколько я знаю, нет никакого способа написать это самостоятельно.

Следующее должно быть принято с зерном соли. Я предполагаю, что все внутренние векторы имеют одинаковый размер. Я не принимаю во внимание const_iterators, потому что вам не нужно, чтобы они использовали std::stable_partition. Я опустил некоторые функции-члены, которые вы должны будете добавить самостоятельно. Алгоритм требует, чтобы итератор придерживался двух названных концепций, а именно LegacyBidirectionalIterator и ValueSwappable. Тем не менее, вот как вы можете реализовать итератор, который позволяет перебирать столбцы 2-го вектора: 

#include <iostream>
#include <vector>

struct vector2d_col_iterator {
    using container_t = std::vector<std::vector<int>>;
    container_t& container;
    size_t row;
    size_t col;
    vector2d_col_iterator& operator++(){
        ++row;
        return *this;
    }
    bool operator==(const vector2d_col_iterator& other) const {
        return col == other.col && row == other.row;
    }
    bool operator !=(const vector2d_col_iterator& other) const {
        return !(*this == other);
    }
    int& operator*() { return container[row][col]; }
    static vector2d_col_iterator begin(container_t& container,int col) {
        return {container,0,col};
    }
    static vector2d_col_iterator end(container_t& container,int col) {
        return {container,container.size(),col};
    }
};

int main() {
    std::vector<std::vector<int>> v{ {1,2,3},{4,5,6}};
    auto begin = vector2d_col_iterator::begin(v,1);
    auto end = vector2d_col_iterator::end(v,1);
    for ( ; begin != end; ++begin) std::cout << *begin << " ";
}

Вывод: 

2 5

Живой пример

Эффективность не очень большая проблема, матрицы будут относительно небольшими. Я просто хочу найти самый простой и понятный способ сделать это. Желательно без необходимости писать реализацию stable_partition с нуля.

Если матрицы действительно маленькие (скажем, ~ 20x20 элементов) и эффективность на самом деле не имеет значения, то, возможно, проще всего использовать std::stable_partition только на внутренних векторах. Вы можете транспонировать матрицу, вызвать алгоритм в al oop для всех внутренних векторов, снова транспонировать. Выполнено. Это в основном ~ 10 строк кода. Твой выбор;)

...