C++ Partition a vector of vectors using <algorithm>

user_9494363 0
Viewed 405

Suppose you have a 2D vector defined as follows: 

std::vector<vector<int>> v

and which represents a matrix: 

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

I want to stable-partition (say with predicate el != 0) this matrix, but in all directions. This means that I want to be able to get:

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)

For two directions, this can be done very simply by iterating through the outer vector and partitioning the inner vectors (in order or in reverse). However for the other directions I do not know how to go about doing the same.

Is there a way to achieve this using std::stable_partition. Is there maybe another data structure (which supports indexing like vectors) which will allow me to do this more easily?
If I have ti implement this by scratch, is there maybe a standard or recommended way to do it?

data-partitioning c++14 algorithm c++
2 Answers

You don't need to write your own implementation of the algorithm. Iterators are the customization point when you want to use an existing algorithm for a custom data structure. Unfortunately, writing your own iterator requires quite some boilerplate. I think boost can help, but if you want to stay with what the standard library offers, to my knowledge there is no way around writing it yourself.

The following is to be taken with a grain of salt. I assume all inner vectors are of same size. I do not take into account const_iterators, because you wont need them to use std::stable_partition. I have omitted some member functions that you will have to add yourself. The algorithm requires the iterator to adhere to two named concepts, namely LegacyBidirectionalIterator and ValueSwappable. That being said, here is how you can implement an iterator that enables you to iterate columns of the 2d vector:

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

Output:

2 5

Live example

Efficiency is not a really big issue, the matrices will be relatively small. I just want to find the simplest, clearest way of doing this. Preferably without having to write a stable_partition implementation from scratch.

If the matrices are really small (lets say ~20x20 elements) and efficiency is really not a concern, then the simplest is perhaps to use std::stable_partition only on the inner vectors. You can transpose the matrix, call the algorithm in a loop for all inner vectors, transpose again. Done. Thats basically ~10 lines of code. Your choice ;)

user_41177280

With range-v3, you might do:

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

Demo

user_26845390
Related