c++ Sorting a vector based on values of other vector, or what's faster?

Question

Hi,

There are a couple of other posts about sorting a vector A based on values in another vector B. Most of the other answers tell to create a struct or a class to combine the values into one object and use std::sort.

Though I'm curious about the performance of such solutions as I need to optimize code which implements bubble sort to sort these two vectors. I'm thinking to use a vector<pair<int,int>> and sort that.

I'm working on a blob-tracking application (image analysis) where I try to match previously tracked blobs against newly detected blobs in video frames where I check each of the frames against a couple of previously tracked frames and of course the blobs I found in previous frames. I'm doing this at 60 times per second (speed of my webcam).

Any advice on optimizing this is appreciated. The code I'm trying to optimize can be shown here:

http://code.google.com/p/projectknave/source/browse/trunk/knaveAddons/ofxBlobTracker/ofCvBlobTracker.cpp?spec=svn313&r=313

important: I forgot to mention that the size of the vectors will never be bigger than 5, and mostly have only 3 items in it and will be unsorted (maybe I could even hardcode it for 3 items?)

Thanks

Answer 1

C++ provides lots of options for sorting, from the std::sort algorithm to sorted containers like std::map and std::set. You should always try to use these as your first solution, and only try things like "optimised bubble sorts" as a last resort.

Answer 2

I implemented this a while ago. Also, I think you mean ordering a vector B in the same way as the sorted values of A.

Index contains the sorting order of data.

/** Sorts a vector and returns index of the sorted values
 * \param Index Contains the index of sorted values in the original vector
 * \param data The vector to be sorted
 */
template<class T>
void paired_sort(vector<unsigned int> & Index, const vector<T> & data)
{
    // A vector of a pair which will contain the sorted value and its index in the original array
    vector<pair<T,unsigned int>> IndexedPair;
    IndexedPair.resize(data.size());
    for(unsigned int i=0;i<IndexedPair.size();++i)
    {
        IndexedPair[i].first = data[i];
        IndexedPair[i].second = i;
    }
    sort(IndexedPair.begin(),IndexedPair.end());
    Index.resize(data.size());
    for(size_t i = 0; i < Index.size(); ++i) Index[i] = IndexedPair[i].second;
}