In "Creating an Index Table in STL," ("C/C++ Tips #1," August 2000) Craig Hicks points out that an index table is a useful tool with no direct support in the Standard C++ library. However, there is a simple and flexible way to indirectly create one.
An index table is simply a specialized version of a common STL entity — a sequence of pointers. As everyone who has tried to sort a vector of pointers knows, by default, they will be sorted according to the order of the pointers — the ordering of the addresses in memory. Most of the time you'd rather sort them according to the ordering of the objects pointed to. The simplest way to do this is to define an operator< for the pointers:
bool operator < (Widget const *a, Widget const *b)
{ return *a < *b; }
This solution won't work for an index table, because you can't redefine operator< on built-in integer types, and you wouldn't want to if you could. Luckily, the STL authors anticipated the need to sort using other criteria. You are allowed to pass a comparison function or function object to the sort routines.
In this case, the comparison function needs to know the index value and the sequence that is being indexed. This solution requires a function object to store the information pertaining to what is being sorted. Though my solution uses only the begin iterator, I also store the end iterator. That feels more natural to me, and the end iterator could be used for error-checking, so it's a good idea to have it available. Note that the iterators must be random-access iterators for this to work.
#include <vector>
#include <algorithm>
#include <iostream>
template <class random_iterator>
class IndexedComparison
{
public:
IndexedComparison (random_iterator begin,
random_iterator end)
: p_begin (begin), p_end (end) {}
bool operator () (unsigned int a, unsigned int b) const
{ return *(p_begin + a) < *(p_begin + b); }
private:
random_iterator const p_begin;
random_iterator const p_end;
};
// Setup and reporting code below by Craig Hicks
int main()
{
unsigned int i;
int ai[10] = { 15,12,13,14,18,11,10,17,16,19 };
std::cout << "#################" << std::endl;
std::vector<int> vecai(ai, ai+10);
std::vector<unsigned int> indices(vecai.size ());
for (i = 0; i < indices.size (); i++)
indices [i] = i;
std::sort (indices.begin (), indices.end (),
IndexedComparison<std::vector<int>::const_iterator>
(vecai.begin (), vecai.end ()));
for (i=0; i<10; i++)
std::cout << "i=" << i
<< ", aidxtbl[i]=" << indices[i]
<< ", ai[aidxtbl[i]]=" << ai[indices[i]]
<< std::endl;
std::cout << "#################" << std::endl;
return 0;
}
The sort call becomes a bit long-winded, but it does the job admirably. It creates a temporary IndexedComparison object, keyed to the const_iterator of the sequence being indexed, and initialized with its begin and end iterators. That function object then ensures that the index sequence is sorted properly.
Any kind of STL sort can be used this way. The IndexedComparison object can also be extended to allow you to pass in a comparison function for the objects being indexed, which would make this solution every bit as flexible as the STL sorts themselves.
Herb Sutter pointed out a disadvantage of this approach: "it pushes logic out into the calling code, which now has to loop to build the array and then call sort with the correctly typed predicate — and this has to be repeated everywhere this is going to be used. The original was better encapsulated, with just a single function call that included the setup."
Herb adds, "However, exposing sort does give a benefit, to wit, the ability to replace the sorting function to be used, which was a question left for readers on the original."
Several other readers have contributed interesting solutions in response to Tip #1, which we may explore in future Tips. Some of those solutions, like Craig Hicks' solution, require creation of a temporary table of iterators — potentially costly in terms of space and performance. I like the solution above because it doesn't require creation of any intermediate tables. — mb
还有三个比较好的版本：
#include <vector>
#include <map>
#include <algorithm>
// Solution 1 does some basic cleanup but still preserves the general structure
// of the original's approach. We're down to 17 lines (even if you count "public:"
// and "private:" as lines), where the original had 23.
//
namespace Solution1 {
template<class Iter>
class sort_idxtbl_pair {
public:
void set(const Iter& it, int i) { it_ = it; i_ = i; }
bool operator<(const sort_idxtbl_pair& other) const
{ return *it_ < *other.it_; }
operator int() const { return i_; }
private:
Iter it_;
int i_;
};
// This function is where most of the clarity savings came from; it has 5 lines,
// where the original had 13. After each code line, I'll show the corresponding
// original code for comparison. Prefer to write code that is clear and concise,
// not unnecessarily complex or obscure!
//
template<class IterIn, class IterOut>
void sort_idxtbl(IterIn first, IterIn last, IterOut out) {
std::vector<sort_idxtbl_pair<IterIn> > v(last-first);
// int iDst = last-first;
// typedef std::vector< sort_idxtbl_pair<RAIter> > V;
// V v(iDst);
for(int i=0; i < last-first; ++i)
v[i].set(first+i, i);
// 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());
// std::sort(v.begin(), v.end());
std::copy(v.begin(), v.end(), out);
// int *pi = pidxtbl;
// vit = v.begin();
// for (; vit<v.end(); pi++, vit++)
// *pi = (*vit).i;
}
}
// Solution 2 uses a pair instead of reinventing a pair-like helper class. Now we're
// down to 13 lines, from the original 23. Of the 14 lines, 9 are purpose-specific,
// and 5 are directly reusable in other contexts.
//
namespace Solution2 {
template<class T, class U>
struct ComparePair1stDeref {
bool operator()(const std::pair<T,U>& a, const std::pair<T,U>& b) const
{ return *a.first < *b.first; }
};
template<class IterIn, class IterOut>
void sort_idxtbl(IterIn first, IterIn last, IterOut out) {
std::vector< std::pair<IterIn,int> > s(last-first);
for(int i=0; i < s.size(); ++i)
s[i] = std::make_pair(first+i, i);
std::sort(s.begin(), s.end(), ComparePair1stDeref<IterIn,int>());
for(int i=0; i < s.size(); ++i, ++out)
*out = s[i].second;
}
}
// Solution 3 just shows a couple of alternative details?it uses a map to avoid a
// separate sorting step, and it uses std::transform() instead of a handcrafted loop.
// Here we still have 15 lines, but more are reusable. This version uses more space
// overhead and probably more time overhead too, so I prefer Solution 2, but this
// is an example of finding alternative approaches to a problem.
//
namespace Solution3 {
template<class T>
struct CompareDeref {
bool operator()(const T& a, const T& b) const
{ return *a < *b; }
};
template<class T, class U>
struct Pair2nd {
const U& operator()(const std::pair<T,U>& a) const { return a.second; }
};
template<class IterIn, class IterOut>
void sort_idxtbl(IterIn first, IterIn last, IterOut out) {
std::multimap<IterIn, int, CompareDeref<IterIn> > v;
for(int i=0; first != last; ++i, ++first)
v.insert(std::make_pair(first, i));
std::transform(v.begin(), v.end(), out, Pair2nd<IterIn const,int>());
}
}
// I left the test harness essentially unchanged, except to demonstrate putting
// the output in an output iterator (instead of necessarily an int*) and using the
// source array directly as a container.
//
#include <iostream>
int main() {
int ai[10] = { 15,12,13,14,18,11,10,17,16,19 };
std::cout << "#################" << std::endl;
std::vector<int> aidxtbl(10);
// use another namespace name to test a different solution
Solution3::sort_idxtbl(ai, ai+10, aidxtbl.begin());
for(int i=0; i<10; ++i)
std::cout << "i="<< i
<< ", aidxtbl[i]="<< aidxtbl[i]
<< ", ai[aidxtbl[i]]="<< ai[aidxtbl[i]]
<< std::endl;
std::cout << "#################" << std::endl;
}