Style Case Studies: Index Tables - Summary
(Page 6 of 6 )
Let’s preserve the original code’s basic interface choice instead of straying far afield and proposing alternate design choices. Limiting our critique just to correcting the code for mechanical errors and basic style, then, consider the three alternative improved versions below. Each has its own benefits, drawbacks, and style preferences as explained in the accompanying comments. What all three versions have in common is that they are clearer, more understandable, and more portable code—and that ought to count for something, in your company and in mine.
// An improved version of the code originally published in [Hicks00].
//
#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;
}
 This chapter is from Exceptional C++ Style, by Herb Sutter (ISBN 0201760428, copyright 2005. All rights reserved. It is reprinted with permission from Addison-Wesley Professional). Check it out at your favorite bookstore today.
Buy this book now. |
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
