Differences From Artifact [8e84d319ff86cb61]:
- File
_lib/typical/amap.cpp
- 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
- File
lib/typical/amap.cpp
- 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]
To Artifact [7a3d2ba79608ced5]:
- File
lib/typical/amap.cpp
- 2012-02-24 12:44:38 - part of checkin [db58c713f6] on branch trunk - 534 (user: kinaba) [annotate]
5 // overflows, it eliminates duplication 5 // overflows, it eliminates duplication
6 // 6 //
7 7
8 template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)> 8 template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)>
9 struct amap 9 struct amap
10 { 10 {
11 typedef typename vector< pair<K,V> >::iterator iterator; 11 typedef typename vector< pair<K,V> >::iterator iterator;
> 12 struct ByKey { bool operator()(const pair<K,V>& a, const pair<K,V>& b) c
12 13
13 vector< pair<K,V> > kv; 14 vector< pair<K,V> > kv;
14 amap() { kv.reserve(LIMIT); } 15 amap() { kv.reserve(LIMIT); }
15 16
16 void add(const K& k, const V& v) 17 void add(const K& k, const V& v)
17 { 18 {
18 kv.push_back( make_pair(k,v) ); 19 kv.push_back( make_pair(k,v) );
................................................................................................................................................................................
20 normalize(); 21 normalize();
21 } 22 }
22 23
23 iterator begin() { return kv.begin(); } 24 iterator begin() { return kv.begin(); }
24 iterator end() { return kv.end(); } 25 iterator end() { return kv.end(); }
25 void swap( amap& rhs ) { kv.swap(rhs.kv); } 26 void swap( amap& rhs ) { kv.swap(rhs.kv); }
26 27
27 // Tested: SRM 469 Lv3 | 28 // Tested: SRM 469 Lv3 (Accumulate)
28 void normalize() 29 void normalize()
29 { 30 {
30 sort(kv.begin(), kv.end()); | 31 sort(kv.begin(), kv.end(), ByKey());
31 int i=0; 32 int i=0;
32 for(int j=0; j<kv.size(); ++i) 33 for(int j=0; j<kv.size(); ++i)
33 { 34 {
34 int k = j; 35 int k = j;
35 kv[i] = kv[k]; 36 kv[i] = kv[k];
36 while( ++j<kv.size() && kv[k].first==kv[j].first ) 37 while( ++j<kv.size() && kv[k].first==kv[j].first )
37 kv[i].second += kv[j].second; 38 kv[i].second += kv[j].second;
................................................................................................................................................................................
38 } 39 }
39 kv.resize(i); 40 kv.resize(i);
40 } 41 }
41 /* 42 /*
42 // Not Tested (Prefer First) 43 // Not Tested (Prefer First)
43 void normalize() 44 void normalize()
44 { 45 {
45 sort(kv.begin(), kv.end()); | 46 sort(kv.begin(), kv.end(), ByKey());
46 int i=0; 47 int i=0;
47 for(int j=0; j<kv.size(); ++i) 48 for(int j=0; j<kv.size(); ++i)
48 { 49 {
49 int k = j; 50 int k = j;
50 kv[i] = kv[k]; 51 kv[i] = kv[k];
51 while( ++j<kv.size() && kv[k].first==kv[j].first ) 52 while( ++j<kv.size() && kv[k].first==kv[j].first )
52 {} 53 {}
................................................................................................................................................................................
53 } 54 }
54 kv.resize(i); 55 kv.resize(i);
55 } 56 }
56 57
57 // Not Tested (Prefer Last) 58 // Not Tested (Prefer Last)
58 void normalize() 59 void normalize()
59 { 60 {
60 sort(kv.begin(), kv.end()); | 61 sort(kv.begin(), kv.end(), ByKey());
61 int i=0; 62 int i=0;
62 for(int j=0; j<kv.size(); ++i) 63 for(int j=0; j<kv.size(); ++i)
63 { 64 {
64 int k = j; 65 int k = j;
65 while( ++j<kv.size() && kv[k].first==kv[j].first ) 66 while( ++j<kv.size() && kv[k].first==kv[j].first )
66 {} 67 {}
67 kv[i] = kv[j-1]; 68 kv[i] = kv[j-1];
68 } 69 }
69 kv.resize(i); 70 kv.resize(i);
70 } 71 }
71 */ 72 */
72 }; 73 };