C/C++ Tips

C/C++ Tip #1: Creating an Index Table in STL

Craig Hicks

Often when sorting an array it is not desirable to actually rearrange the elements of the array; what is needed is an index table describing which number element is the first, which is second, etc. There are two good reasons for creating such tables:

1) The elements may be large and expensive to copy — and elements will be copied if the array itself is sorted.

2) There are other distinct arrays in one-to-one correspondence with the array whose order is being queried.

Note that rearranging the target instead of obtaining an index table destroys the correspondence described in 2). Thus, obtaining an index table is not just an efficiency measure; it is sometimes required for proper functionality.

Unfortunately, I can find no function in the STL library to make an index table. The code below implements a template function sort_idxtbl, which calls std::sort and makes an index table.

// program sort_idxtbl(...) to make a permuted array of indices
#include <vector>
#include <algorith>

template <class RAIter>
struct sort_idxtbl_pair
   {
       RAIter it;
       int i;
       bool operator < (const sort_idxtbl_pair& s)
       { return (*it) < (*(s.it)); }
       void set(const RAIter& _it, int _i) { it=_it; i=_i; }
       sort_idxtbl_pair() {}
   } ;

template <class RAIter>
void sort_idxtbl(RAIter first, RAIter last, int* pidxtbl)
{
    int iDst = last-first;
    typedef std::vector< sort_idxtbl_pair<RAIter> > V;
    V v(iDst);

    int i=0;
    RAIter it = first;
    V::iterator vit = v.begin();
    for (i=0; it<last; it++, vit++, i++)
       (*vit).set(it,i);

    std::sort(v.begin(), v.end());

    int *pi = pidxtbl;
    vit = v.begin();
    for (; vit<v.end(); pi++, vit++)
        *pi = (*vit).i;
}

main()
{
   int ai[10] = { 15,12,13,14,18,11,10,17,16,19 };

   cout << "#################" << endl;
   std::vector<int> vecai(ai, ai+10);
   int aidxtbl[10];
   sort_idxtbl(vecai.begin(), vecai.end(), aidxtbl);

   for (int i=0; i<10; i++)
      cout << "i=" << i
           << ", aidxtbl[i]=" << aidxtbl[i]
           << ", ai[aidxtbl[i]]=" << ai[aidxtbl[i]]
           << endl;
   cout << "#################" << endl;

}

Note that function sort_idxtbl is specialized to use the STL template function sort, which is usually based on the Quicksort algorithm. Applying sort_heap, stable_sort, or any other sort of sort would seem to require repetitive cutting and pasting — at least I see no obvious way to include them as a template parameter, since the sort functions are not classes. I welcome other readers to show how this might be done.

[There is at least one way to specify the sort algorithm as a template parameter — by wrapping the algorithm in a functor. But you wind up doing about the same amount of typing. I too would like to see a better way to handle this problem. — mb]

Thanks to Craig Hicks (hicks@kgk.co.jp) for this tip. If you have a C/C++ programming tip and can write it up in 400 words or less, send it to mbriand@cmp.com. If we print your tip, we'll send you a nice CUJ sweater and a copy of the CUJ CD-ROM.