Artifact 8e84d319ff86cb61de52f2b3b463b3e242ab6b7d

• 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]

//
// 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;

	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
	void normalize()
	{
		sort(kv.begin(), kv.end());
		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());
		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());
		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);
	}
*/
};