Artifact 7a3d2ba79608ced5b9c0509c333c9183c04a939f
//
// accumulative map
// basically a map<K,V>, but it eliminates duplication lazily
// first keep all inserted elements in a vector. only when the buffer
// overflows, it eliminates duplication
//
template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)>
struct amap
{
typedef typename vector< pair<K,V> >::iterator iterator;
struct ByKey { bool operator()(const pair<K,V>& a, const pair<K,V>& b) const { return a.first<b.first; } };
vector< pair<K,V> > kv;
amap() { kv.reserve(LIMIT); }
void add(const K& k, const V& v)
{
kv.push_back( make_pair(k,v) );
if( kv.size() == LIMIT )
normalize();
}
iterator begin() { return kv.begin(); }
iterator end() { return kv.end(); }
void swap( amap& rhs ) { kv.swap(rhs.kv); }
// Tested: SRM 469 Lv3 (Accumulate)
void normalize()
{
sort(kv.begin(), kv.end(), ByKey());
int i=0;
for(int j=0; j<kv.size(); ++i)
{
int k = j;
kv[i] = kv[k];
while( ++j<kv.size() && kv[k].first==kv[j].first )
kv[i].second += kv[j].second;
}
kv.resize(i);
}
/*
// Not Tested (Prefer First)
void normalize()
{
sort(kv.begin(), kv.end(), ByKey());
int i=0;
for(int j=0; j<kv.size(); ++i)
{
int k = j;
kv[i] = kv[k];
while( ++j<kv.size() && kv[k].first==kv[j].first )
{}
}
kv.resize(i);
}
// Not Tested (Prefer Last)
void normalize()
{
sort(kv.begin(), kv.end(), ByKey());
int i=0;
for(int j=0; j<kv.size(); ++i)
{
int k = j;
while( ++j<kv.size() && kv[k].first==kv[j].first )
{}
kv[i] = kv[j-1];
}
kv.resize(i);
}
*/
};