STLUtilities.h

   1 // STLUtilities.h\r
   2 \r
   3 // Derek Barnett\r
   4 // Marth Lab, Boston College\r
   5 // Last modified: 19 March 2009\r
   6 \r
   7 #ifndef STL_UTILITIES_H\r
   8 #define STL_UTILITIES_H\r
   9 \r
  10 #include <algorithm>\r
  11 using std::distance;\r
  12 using std::find;\r
  13 using std::transform;\r
  14 \r
  15 #include <functional>\r
  16 using std::unary_function;\r
  17 \r
  18 #include <iterator>\r
  19 using std::iterator_traits;\r
  20 \r
  21 #include <string>\r
  22 using std::string;\r
  23 \r
  24 #include <utility>\r
  25 using std::pair;\r
  26 \r
  27 #include <vector>\r
  28 using std::vector;\r
  29 \r
  30 // -------------------------------------------------------------------------------- //\r
  31 // This file contains a sample of STL tricks I've gathered along the way.\r
  32 //\r
  33 // Many thanks throughout to 'Effective' series by Scott Meyers.\r
  34 // Some code is lifted (almost) verbatim from his texts where applicable.\r
  35 // ------------------------------------------------------------------------------- //\r
  36 \r
  37 // --------------------------------------------------------------------------------------------------------------------------------- //\r
  38 // STL containers will delete the values they hold when the container is deleted or goes out of scope\r
  39 // *** If the container contains pointers, however, they WILL NOT delete the actual pointed-to objects ***\r
  40 // This struct allows for easy algorithm processing (instead of pesky loops and iterator-boundary issues) to delete pointed-to objects (for any C++ type) that have been allocated with 'new')\r
  41 // Usage example:    for_each( container.begin(), container.end(), DeleteObject() ) \r
  42 //\r
  43 // Unless of course, you like quirky, hard-to-spot memory leaks... then feel free to disregard this little STL lesson   =)\r
  44 // --------------------------------------------------------------------------------------------------------------------------------- //\r
  45 struct DeleteObject {\r
  46         template<typename T>\r
  47         void operator() (const T* p) const { \r
  48                 delete p; \r
  49         }\r
  50 };\r
  51 \r
  52 template<typename T>\r
  53 void ClearPointerVector(vector<T>& v) {\r
  54         if ( !v.empty() ) {\r
  55                 for_each(v.begin(), v.end(), DeleteObject());\r
  56                 v.clear();\r
  57         }\r
  58 }\r
  59 \r
  60 // --------------------------------------------------------------------------------------------------------------------------------- //\r
  61 // Query a vector (other containers? havent tried) for an element\r
  62 // Returns the index of that element\r
  63 // Returns vector::size() if not found\r
  64 // Works with reverse iterators as well... index is counted backward from last element though\r
  65 // --------------------------------------------------------------------------------------------------------------------------------- //\r
  66 template < typename InputIterator, typename EqualityComparable >\r
  67 typename iterator_traits<InputIterator>::difference_type\r
  68 Index(const InputIterator& begin, const InputIterator& end, const EqualityComparable& item) {\r
  69         return distance(begin, find(begin, end, item));\r
  70 }\r
  71 \r
  72 // ----------------------------------------------------------------------------------------------------------------------//\r
  73 // This next section is a sort of work-around for the bulky associative maps\r
  74 // The idea is to use a *SORTED* vector of pair objects as a lookup vector\r
  75 // LookupVector = vector< pair<Key, Value> > \r
  76 // ----------------------------------------------------------------------------------------------------------------------//\r
  77 \r
  78 // The following template classes allow a templatized comparison function for sorting & searching lookup vector\r
  79 \r
  80 // allows sorting by Key ( less<Key> )\r
  81 template <typename Key, typename Value>\r
  82 class LookupKeyCompare {\r
  83 \r
  84         typedef pair< Key, Value > LookupData;\r
  85         typedef typename LookupData::first_type Key_t;\r
  86         \r
  87         public:\r
  88                 bool operator() (const LookupData& lhs, const LookupData& rhs) const { return keyLess(lhs.first, rhs.first); }\r
  89                 bool operator() (const LookupData& lhs, const Key_t& k) const { return keyLess(lhs.first, k); }\r
  90                 bool operator() (const Key_t& k, const LookupData& rhs) const { return keyLess(k, rhs.first); }\r
  91         private:\r
  92                 bool keyLess(const Key_t& k1, const Key_t& k2) const { return k1 < k2; }\r
  93 };\r
  94 \r
  95 // allows sorting by Value ( less<Value> )\r
  96 template <typename Key, typename Value>\r
  97 class LookupValueCompare {\r
  98 \r
  99         typedef pair< Key, Value > LookupData;\r
 100         typedef typename LookupData::second_type Value_t;\r
 101         \r
 102         public:\r
 103                 bool operator() (const LookupData& lhs, const LookupData& rhs) const { return valueLess(lhs.second, rhs.second); }\r
 104                 bool operator() (const LookupData& lhs, const Value_t& k) const { return valueLess(lhs.second, k); }\r
 105                 bool operator() (const Value_t& k, const LookupData& rhs) const { return valueLess(k, rhs.second); }\r
 106         private:\r
 107                 bool valueLess(const Value_t& k1, const Value_t& k2) const { return k1 < k2; }\r
 108 };\r
 109 \r
 110 // The following template functions/structs allow you to pull all keys or all values from this lookup structure\r
 111 \r
 112 // pull Key from a data pair\r
 113 template<typename Key, typename Value>\r
 114 struct RipKey:\r
 115         public unary_function< pair<Key,Value>, Key> {\r
 116                 Key operator() (pair<Key,Value> dataPair) { \r
 117                         return dataPair.first; \r
 118                 }\r
 119 };\r
 120 \r
 121 // pull Value from a data pair\r
 122 template<typename Key, typename Value>\r
 123 struct RipValue:\r
 124         public unary_function< pair<Key,Value>, Value> {\r
 125                 Value operator() (pair<Key,Value> dataPair) { \r
 126                         return dataPair.second; \r
 127                 }\r
 128 };\r
 129 \r
 130 // pull all Keys from lookup, store in dest (overwrite contents of dest)\r
 131 template <typename Key, typename Value>\r
 132 void RipKeys( vector< pair<Key,Value> >& lookup, vector<Key>& dest) {\r
 133         dest.clear();\r
 134         dest.reserve(lookup.size());\r
 135         transform(lookup.begin(), lookup.end(), back_inserter(dest), RipKey<Key,Value>());\r
 136 }\r
 137 \r
 138 // pull all Values from lookup, store in dest (overwrite contents of dest)\r
 139 template <typename Key, typename Value>\r
 140 void RipValues( vector< pair<Key,Value> >& lookup, vector<Value>& dest) {\r
 141         dest.clear();\r
 142         dest.reserve(lookup.size());\r
 143         transform(lookup.begin(), lookup.end(), back_inserter(dest), RipValue<Key,Value>());\r
 144 }\r
 145 \r
 146 #endif /* STL_UTILITIES_H */\r