5 5 // overflows, it eliminates duplication 6 6 // 7 7 8 8 template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)> 9 9 struct amap 10 10 { 11 11 typedef typename vector< pair<K,V> >::iterator iterator; 12 + struct ByKey { bool operator()(const pair<K,V>& a, const pair<K,V>& b) const { return a.first<b.first; } }; 12 13 13 14 vector< pair<K,V> > kv; 14 15 amap() { kv.reserve(LIMIT); } 15 16 16 17 void add(const K& k, const V& v) 17 18 { 18 19 kv.push_back( make_pair(k,v) ); ................................................................................ 20 21 normalize(); 21 22 } 22 23 23 24 iterator begin() { return kv.begin(); } 24 25 iterator end() { return kv.end(); } 25 26 void swap( amap& rhs ) { kv.swap(rhs.kv); } 26 27 27 - // Tested: SRM 469 Lv3 28 + // Tested: SRM 469 Lv3 (Accumulate) 28 29 void normalize() 29 30 { 30 - sort(kv.begin(), kv.end()); 31 + sort(kv.begin(), kv.end(), ByKey()); 31 32 int i=0; 32 33 for(int j=0; j<kv.size(); ++i) 33 34 { 34 35 int k = j; 35 36 kv[i] = kv[k]; 36 37 while( ++j<kv.size() && kv[k].first==kv[j].first ) 37 38 kv[i].second += kv[j].second; ................................................................................ 38 39 } 39 40 kv.resize(i); 40 41 } 41 42 /* 42 43 // Not Tested (Prefer First) 43 44 void normalize() 44 45 { 45 - sort(kv.begin(), kv.end()); 46 + sort(kv.begin(), kv.end(), ByKey()); 46 47 int i=0; 47 48 for(int j=0; j<kv.size(); ++i) 48 49 { 49 50 int k = j; 50 51 kv[i] = kv[k]; 51 52 while( ++j<kv.size() && kv[k].first==kv[j].first ) 52 53 {} ................................................................................ 53 54 } 54 55 kv.resize(i); 55 56 } 56 57 57 58 // Not Tested (Prefer Last) 58 59 void normalize() 59 60 { 60 - sort(kv.begin(), kv.end()); 61 + sort(kv.begin(), kv.end(), ByKey()); 61 62 int i=0; 62 63 for(int j=0; j<kv.size(); ++i) 63 64 { 64 65 int k = j; 65 66 while( ++j<kv.size() && kv[k].first==kv[j].first ) 66 67 {} 67 68 kv[i] = kv[j-1]; 68 69 } 69 70 kv.resize(i); 70 71 } 71 72 */ 72 73 };