Posted by: sureshamrita | June 2, 2012

Sorting an array with original index information preserved

Some times it becomes necessary to sort an array with the original index information preserved. One easy solution is to create new array of pairs containing the original value and index, and sort the new array based on the values and from that the index position can be obtained. In this article, another solution using Boost.MultiIndex is provided.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using boost::multi_index_container;
using namespace boost::multi_index;

/*The following typedef says that mycontainer is a multiindex container, storing integers with 2 indices. One random access index, and the other is ordered based on integer values and non unique. The random access index provides operator[] and at() for accessing elements based on their position in the index. This method has the advantage that it can be adapted to any number indices for containers containing arbitrary (user defined )type of elements.
*/

typedef multi_index_container<int, indexed_by<random_access<>, ordered_non_unique<identity<int>>>> mycontainer;

int main() {
    vector<int> v { 1, 4, 2, 6, 6, 9, -12 };

    mycontainer mc;
    copy(v.begin(), v.end(), back_inserter(mc));

//original index

    for (auto x : mc) cout << x << " ";
    cout << endl;

//original index - another way
    const mycontainer::nth_index<0>::type& index0 = get<0>(mc);
    for (auto x : index0) cout << x << " ";
    cout << endl;

//original index yet another way
    for(int i = 0; i < mc.size(); i++) cout << mc[i] << " ";
    cout << endl;

//sorted index. note that the type of index1 cannot be replaced by auto
    const mycontainer::nth_index<1>::type& index1 = get<1>(mc);
    for (auto x : index1) cout << x << " ";
    cout << endl;

//obtaining the original index using project.

    for (auto x = index1.begin(); x != index1.end(); x++) {
        mycontainer::iterator i2 = mc.project<0>(x); // this line provides the iterator position before sorting, corresponding to the sorted iterator
        cout << distance(mc.begin(), i2) << " "; //distance gives the difference between two iterators
    }
    cout << endl;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: