sort and get index?

Discussion in 'C++' started by b83503104, May 21, 2004.

  1. b83503104

    b83503104 Guest

    In matlab, the sort function returns two things:

    [a,b]=sort([5, 8, 7])

    a = 5 7 8
    b = 1 3 2

    where a is the sorted result, and b is the corresponding index.
    Is there C++ code available to achieve this?
    Better compatible with STL vector.
    Thanks
    b83503104, May 21, 2004
    #1
    1. Advertising

  2. "b83503104" <> wrote...
    > In matlab, the sort function returns two things:
    >
    > [a,b]=sort([5, 8, 7])
    >
    > a = 5 7 8
    > b = 1 3 2
    >
    > where a is the sorted result, and b is the corresponding index.
    > Is there C++ code available to achieve this?


    Probably. You could simply sort pairs based on their 'first'
    members, then get the 'second' members (which you should set
    to ordinal numbers before sorting).

    V
    Victor Bazarov, May 21, 2004
    #2
    1. Advertising

  3. b83503104

    Me Guest

    template<class T> struct index_cmp {
    index_cmp(const T arr) : arr(arr) {}
    bool operator()(const size_t a, const size_t b) const
    { return arr[a] < arr; }
    const T arr;
    };

    vector<int> a;
    a.push_back(5); a.push_back(8); a.push_back(7);

    vector<size_t> b;
    for (unsigned i = 0; i < a.size(); ++i)
    b.push_back(i);
    // b = [0, 1, 2]
    sort(b.begin(), b.end(), index_cmp<vector<int>&>(a));
    // b = [0, 2, 1]

    then just offset into the a vector with the indices in b. I recomend
    just sorting the indices this way and not touching the a vector.
    Me, May 21, 2004
    #3
  4. b83503104

    Siemel Naran Guest

    (b83503104) wrote in message

    > In matlab, the sort function returns two things:
    >
    > [a,b]=sort([5, 8, 7])
    >
    > a = 5 7 8
    > b = 1 3 2
    >
    > where a is the sorted result, and b is the corresponding index.
    > Is there C++ code available to achieve this?
    > Better compatible with STL vector.
    > Thanks


    There is no such way in C++. But you can build it yourself.

    Here is one suggestion: make your original vector { 5, 8, 7 }, make a
    vector of pointers { &orig[0], &orig[1], &orig[2] }, sort the vector
    of pointers using std::sort of 3 arguments which should yield {
    &orig[0], &orig[2], &orig[1] }.

    A second suggestion is: make your original vector a vector of
    pair<int, index> as { {5,0}, {8,1}, {7,2} }, sort the vector using
    std::sort of 3 arguments which should yield { {5,0}, {7,2}, {8,1} }.

    The first way would look something like this:

    std::vector<int> orig;
    orig.push_back(5);
    orig.push_back(7);
    orig.push_back(8);
    std::vector<const int *> pointer;
    pointer.reserve(orig.size());
    const int *const start = &orig[0];
    const int *const end = start + orig.size();
    for (int * iter = start; iter != end; ++iter) pointer.push_back(iter);
    std::sort(pointer.begin(), pointer.end(), LessDereference());

    where

    struct LessDereference {
    template <class T>
    bool operator()(const T * lhs, const T * rhs) const {
    return *lhs < *rhs;
    }
    };

    To print the results, choose whatever option you want. There are many
    ways, and here is one:

    for (int i=0; i<pointer.size(); i++) {
    const int * p = pointer;
    cout << "(" << *p << "," << p-start << " ";
    }
    Siemel Naran, May 21, 2004
    #4
  5. b83503104

    Siemel Naran Guest

    (b83503104) wrote in message

    > In matlab, the sort function returns two things:
    >
    > [a,b]=sort([5, 8, 7])
    >
    > a = 5 7 8
    > b = 1 3 2
    >
    > where a is the sorted result, and b is the corresponding index.
    > Is there C++ code available to achieve this?
    > Better compatible with STL vector.
    > Thanks


    There is no such way in C++. But you can build it yourself.

    Here is one suggestion: make your original vector { 5, 8, 7 }, make a
    vector of pointers { &orig[0], &orig[1], &orig[2] }, sort the vector
    of pointers using std::sort of 3 arguments which should yield {
    &orig[0], &orig[2], &orig[1] }.

    A second suggestion is: make your original vector a vector of
    pair<int, index> as { {5,0}, {8,1}, {7,2} }, sort the vector using
    std::sort of 3 arguments which should yield { {5,0}, {7,2}, {8,1} }.

    The first way would look something like this:

    std::vector<int> orig;
    orig.push_back(5);
    orig.push_back(7);
    orig.push_back(8);
    std::vector<const int *> pointer;
    pointer.reserve(orig.size());
    const int *const start = &orig[0];
    const int *const end = start + orig.size();
    for (int * iter = start; iter != end; ++iter) pointer.push_back(iter);
    std::sort(pointer.begin(), pointer.end(), LessDereference());

    where

    struct LessDereference {
    template <class T>
    bool operator()(const T * lhs, const T * rhs) const {
    return *lhs < *rhs;
    }
    };

    To print the results, choose whatever option you want. There are many
    ways, and here is one:

    for (int i=0; i<pointer.size(); i++) {
    const int * p = pointer;
    cout << "(" << *p << "," << p-start << " ";
    }
    Siemel Naran, May 21, 2004
    #5
  6. b83503104

    Siemel Naran Guest

    (Me) wrote in message

    > template<class T> struct index_cmp {
    > index_cmp(const T arr) : arr(arr) {}
    > bool operator()(const size_t a, const size_t b) const
    > { return arr[a] < arr; }
    > const T arr;
    > };


    Maybe class index_cmp could hold a const reference rather than an
    object (ie. change const T arr to const T& arr). Saves unnecessary
    copying.

    > sort(b.begin(), b.end(), index_cmp<vector<int>&>(a));


    You can provide rename index_cmp to index_cmp_t and provide an inline
    function

    template <class Container>
    inline
    index_cmp_t<Container>
    index_cmp(const Container& c)
    {
    return index_cmp_t<Container>(c);
    }

    This prevents the need to explicitly qualify template parameters in
    the code.
    Siemel Naran, May 21, 2004
    #6
  7. b83503104

    Jeff Flinn Guest

    "b83503104" <> wrote in message
    news:...
    > In matlab, the sort function returns two things:
    >
    > [a,b]=sort([5, 8, 7])
    >
    > a = 5 7 8
    > b = 1 3 2
    >
    > where a is the sorted result, and b is the corresponding index.
    > Is there C++ code available to achieve this?
    > Better compatible with STL vector.
    > Thanks


    Try the following untested code after installing boost from www.boost.org.

    #include <map>
    #include <boost/bind.hpp>
    #include <boost/iterator/counting_iterator.hpp>

    typedef std::map<int,int> tMap; // <data,index>

    tMap Map;

    int Data[] = { 5, 8, 7 };

    std::transform( &data[0], &data[3]
    , boost::counting_iterator<int>(1)
    , std::inserter<tMap>(Map)
    , boost::bind( std::make_pair<int,int>, _1, _2 )
    );

    for( tMap::const_iterator lItr = Map.begin() ; lItr != Map.end() ; ++lItr )
    {
    std::cout << "Data Value: " << lItr->first
    << " At Index: " << lItr->second;
    }

    Jeff F
    Jeff Flinn, May 21, 2004
    #7
  8. b83503104

    Me Guest

    > Maybe class index_cmp could hold a const reference rather than an
    > object (ie. change const T arr to const T& arr). Saves unnecessary
    > copying.
    >
    > > sort(b.begin(), b.end(), index_cmp<vector<int>&>(a));


    It does hold a const reference (notice the '&' at the call to sort). I
    did it this way because doing it the way I would do in real life (add
    a reference only if T isn't a pointer or a reference) requires a lot
    more code or a dependency on boost's type_traits (which will hopefully
    be added to the next standard).
    Me, May 22, 2004
    #8
  9. b83503104

    Siemel Naran Guest

    (Me) wrote in message

    > > Maybe class index_cmp could hold a const reference rather than an
    > > object (ie. change const T arr to const T& arr). Saves unnecessary
    > > copying.
    > >
    > > > sort(b.begin(), b.end(), index_cmp<vector<int>&>(a));

    >
    > It does hold a const reference (notice the '&' at the call to sort). I
    > did it this way because doing it the way I would do in real life (add
    > a reference only if T isn't a pointer or a reference) requires a lot
    > more code or a dependency on boost's type_traits (which will hopefully
    > be added to the next standard).


    Good point, sorry missed it.
    Siemel Naran, May 22, 2004
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. karthikeyavenkat
    Replies:
    2
    Views:
    568
    Bryce
    Mar 17, 2005
  2. Angus Comber
    Replies:
    7
    Views:
    1,145
    Richard Heathfield
    Feb 5, 2004
  3. Selection sort and bubble sort

    , Oct 16, 2007, in forum: C Programming
    Replies:
    22
    Views:
    1,736
    user923005
    Oct 19, 2007
  4. Navin
    Replies:
    1
    Views:
    675
    Ken Schaefer
    Sep 9, 2003
  5. Tomasz Chmielewski

    sorting index-15, index-9, index-110 "the human way"?

    Tomasz Chmielewski, Mar 4, 2008, in forum: Perl Misc
    Replies:
    4
    Views:
    271
    Tomasz Chmielewski
    Mar 4, 2008
Loading...

Share This Page