Thread: stable_partition

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    28

    stable_partition

    hi,

    i have a vector of vectors representing a set of d-dimensional points.
    Code:
    vector < vector <int> > points
    I want to use the stl algorithm stable_partition to partition the set according to the values in a dimension. For example

    if my set of 3-d points is:
    0 2 0 ---> every row is a vector of the same size representing a point (3d here)
    9 3 3
    1 8 4
    1 7 5
    3 4 6
    I want to partition it into two parts (less/greater than a given value, or using the median), using a given dimension.
    Say, if want to partition in the 3rd dimension according to the value 3, then
    partition 1 would be
    0 2 0
    9 3 3
    and partition 2
    1 8 4
    1 7 5
    3 4 6
    Of course, I should be able to partition according to any given dimension at a time (I could do it later by the 2nd or the 1st).
    I am a bit confused of how the predicate for such a function would be.
    Code:
      stable_partition( iterator start, iterator end, Predicate p );
    I would appreciate some help.

    thanks

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    You might want to consider creating a class to encapsulate a point to make things easier and clearer, but it should work either way.

    Here is an example with a function object:
    Code:
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <functional>
    
    struct CheckDimension
    {
        int value;
        CheckDimension(int val) : value(val) { }
        bool operator()(const std::vector<int>& data)
        {
            return data.at(2) < value;
        }
    };
    
    int main()
    {
        std::vector<std::vector<int> > data(5, std::vector<int>(3));
        data[0][0] = 1;
        data[0][1] = 8;
        data[0][2] = 4;
        data[1][0] = 3;
        data[1][1] = 4;
        data[1][2] = 6;
        data[2][0] = 0;
        data[2][1] = 2;
        data[2][2] = 0;
        data[3][0] = 9;
        data[3][1] = 3;
        data[3][2] = 3;
        data[4][0] = 1;
        data[4][1] = 7;
        data[4][2] = 5;
    
        for (std::vector<int>::size_type i = 0; i < data.size(); ++i)
        {
            for (std::vector<int>::size_type j = 0; j < data[i].size(); ++j)
                std::cout << data[i][j] << ' ';
            std::cout << '\n';
        }
    
        std::stable_partition(data.begin(), data.end(), CheckDimension(4));
        std::cout << '\n';
    
        for (std::vector<int>::size_type i = 0; i < data.size(); ++i)
        {
            for (std::vector<int>::size_type j = 0; j < data[i].size(); ++j)
                std::cout << data[i][j] << ' ';
            std::cout << '\n';
        }
    }
    Last edited by Daved; 10-30-2006 at 04:00 PM.

  3. #3
    Registered User
    Join Date
    Jun 2006
    Posts
    28
    thanks
    I did the following , and it seems to work
    Code:
    class vec_part{
    	public: 
    		vec_part(const int index = 0, const int median = 0): i(index), m(median) {}
    		bool operator ()(const vector<int> &v){
    			return v[i] <= m;
    		}
      private:
        const int i, m;
    };
    ....
    
    medianIter = stable_partition (M.begin(), M.end(), vec_part(dimension, median_value));
    
    P1.assign(M.begin(), medianIter);  // set 1
    P2.assign(medianIter++, M.end());  // set 2

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Looks good. I was actually hoping you would add the dimension as part of the predicate object so I didn't feel guilty about giving such a complete answer.

Popular pages Recent additions subscribe to a feed