Index: ps/trunk/source/simulation2/components/CCmpRangeManager.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpRangeManager.cpp
+++ ps/trunk/source/simulation2/components/CCmpRangeManager.cpp
@@ -1,4 +1,4 @@
-/* Copyright (C) 2018 Wildfire Games.
+/* Copyright (C) 2019 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -539,7 +539,7 @@
 				entdata.size = cmpObstruction->GetSize().ToInt_RoundToInfinity();
 
 			// Remember this entity
-			m_EntityData.insert(ent, entdata);
+			m_EntityData.insert_or_assign(ent, entdata);
 			break;
 		}
 		case MT_PositionChanged:
Index: ps/trunk/source/simulation2/system/EntityMap.h
===================================================================
--- ps/trunk/source/simulation2/system/EntityMap.h
+++ ps/trunk/source/simulation2/system/EntityMap.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2013 Wildfire Games.
+/* Copyright (C) 2019 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -19,226 +19,171 @@
 
 #include "Entity.h"
 
+#include <utility>
+
+static const size_t ENTITYMAP_DEFAULT_SIZE = 4096;
 /**
  * A fast replacement for map<entity_id_t, T>.
- * We make the following assumptions:
- *  - entity id's (keys) are unique
- *  - modifications (add / delete) are far less frequent then look-ups
- *  - preformance for iteration is important
+ * Behaves like a much faster std:map.
+ * The drawback is memory usage, as this uses sparse storage.
+ * So creating/deleting entities will lead to inefficiency.
  */
-template<class T> class EntityMap
+
+template<class V, entity_id_t FIRST_VALID_ENTITY_ID = 1, size_t initialSize = ENTITYMAP_DEFAULT_SIZE>
+class EntityMap
 {
+	static_assert(FIRST_VALID_ENTITY_ID > INVALID_ENTITY, "Entity IDs start at INVALID_ENTITY");
 private:
-	EntityMap(const EntityMap&);			// non-copyable
-	EntityMap& operator=(const EntityMap&); // non-copyable
+	friend class TestEntityMap;
+	
+	EntityMap(const EntityMap&) = delete;
+	EntityMap& operator=(const EntityMap&) = delete;
 
 public:
 	typedef entity_id_t key_type;
-	typedef T mapped_type;
-	template<class K, class V> struct key_val {
-		typedef K first_type;
-		typedef V second_type;
-		K first;
-		V second;
-	};
-	typedef key_val<entity_id_t, T> value_type;
+	typedef V mapped_type;
+	typedef std::pair<entity_id_t, V> value_type;
 
 private:
-	size_t m_BufferSize;		// number of elements in the buffer
-	size_t m_BufferCapacity;	// capacity of the buffer
-	value_type* m_Buffer;		// vector with all the mapped key-value pairs
+	std::vector<value_type> m_Data;
 
-	size_t m_Count;				// number of 'valid' entity id's
+	// number of 'valid' entity id's
+	size_t m_Count;
 
+	// EntityMap keeps a valid entity ID at the end() so _iter<>::operator++ knows when to stop the loop
+	// Use FIRST_VALID_ENTITY_ID since we are sure that that is indeed a valid ID.
+#define ITERATOR_FENCE {FIRST_VALID_ENTITY_ID, V()}
 public:
 
-	inline EntityMap() : m_BufferSize(1), m_BufferCapacity(4096), m_Count(0)
+	EntityMap()
+		: m_Count(0)
 	{
-		// for entitymap we allocate the buffer right away
-		// with first element in buffer being the Invalid Entity
-		m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1));
-
-		// create the first element:
-		m_Buffer[0].first = INVALID_ENTITY;
-		m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
-	}
-	inline ~EntityMap()
-	{
-		free(m_Buffer);
+		m_Data.reserve(initialSize);
+		m_Data.push_back(ITERATOR_FENCE);
 	}
 
-	// Iterators
 	template<class U> struct _iter : public std::iterator<std::forward_iterator_tag, U>
 	{
 		U* val;
-		inline _iter(U* init) : val(init) {}
-		inline U& operator*() { return *val; }
-		inline U* operator->() { return val; }
-		inline _iter& operator++() // ++it
-		{
-			++val;
-			while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
+		_iter(U* init) : val(init) {}
+		template<class T>
+		_iter(const _iter<T>& it) : val(it.val) {}
+
+		U& operator*() { return *val; }
+		U* operator->() { return val; }
+
+		_iter& operator++() // ++it
+		{
+			do
+				++val;
+			while (val->first == INVALID_ENTITY);
 			return *this;
 		}
-		inline _iter& operator++(int) // it++
+		_iter operator++(int) // it++
 		{
-			U* ptr = val;
-			++val;
-			while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities
-			return ptr;
+			_iter orig = *this;
+			++(*this);
+			return orig;
 		}
-		inline bool operator==(_iter other) { return val == other.val; }
-		inline bool operator!=(_iter other) { return val != other.val; }
-		inline operator _iter<U const>() const { return _iter<U const>(val); }
+		bool operator==(_iter other) { return val == other.val; }
+		bool operator!=(_iter other) { return val != other.val; }
 	};
 
 	typedef _iter<value_type> iterator;
-	typedef _iter<value_type const> const_iterator;
+	typedef _iter<const value_type> const_iterator;
 
-	inline iterator begin()
+	iterator begin()
 	{
-		value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
-		while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
-		return ptr;
+		iterator it = &m_Data.front();
+		if (it->first == INVALID_ENTITY)
+			++it; // skip all invalid entities
+		return it;
 	}
-	inline iterator end()
+
+	const_iterator begin() const
 	{
-		return iterator(m_Buffer + m_BufferSize);
+		const_iterator it = &m_Data.front();
+		if (it->first == INVALID_ENTITY)
+			++it;
+		return it;
 	}
-	inline const_iterator begin() const
+
+	iterator end()
 	{
-		value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY
-		while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities
-		return ptr;
+		return iterator(&m_Data.back()); // return the ITERATOR_FENCE, see above
 	}
-	inline const_iterator end() const
+
+	const_iterator end() const
 	{
-		return const_iterator(m_Buffer + m_BufferSize);
+		return const_iterator(&m_Data.back()); // return the ITERATOR_FENCE, see above
 	}
 
-	// Size
-	inline bool empty() const { return m_Count == 0; }
-	inline size_t size() const { return m_Count; }
+	bool empty() const { return m_Count == 0; }
+	size_t size() const { return m_Count; }
 
-	// Modification
-	void insert(const key_type key, const mapped_type& value)
+	std::pair<iterator, bool> insert_or_assign(const key_type& key, const mapped_type& value)
 	{
-		if (key >= m_BufferCapacity) // do we need to resize buffer?
-		{
-			size_t newCapacity = m_BufferCapacity + 4096;
-			while (key >= newCapacity) newCapacity += 4096;
-			// always allocate +1 behind the scenes, because end() must have a 0xFFFFFFFF key
-			value_type* mem = (value_type*)realloc(m_Buffer, sizeof(value_type) * (newCapacity + 1));
-			if (!mem)
-			{
-				debug_warn("EntityMap::insert() realloc failed! Out of memory.");
-				throw std::bad_alloc(); // fail to expand and insert
-			}
-			m_BufferCapacity = newCapacity;
-			m_Buffer = mem;
-			goto fill_gaps;
-		}
-		else if (key > m_BufferSize) // weird insert far beyond the end
-		{
-fill_gaps:
-			// set all entity id's to INVALID_ENTITY inside the new range
-			for (size_t i = m_BufferSize; i <= key; ++i)
-				m_Buffer[i].first = INVALID_ENTITY;
-			m_BufferSize = key; // extend the new size
-		}
+		ENSURE(key >= FIRST_VALID_ENTITY_ID);
 
-		value_type& item = m_Buffer[key];
-		key_type oldKey = item.first;
-		item.first = key;
-		if (key == m_BufferSize) // push_back
+		if (key-FIRST_VALID_ENTITY_ID+1 >= m_Data.size())
 		{
-			++m_BufferSize; // expand
-			++m_Count;
-			new (&item.second) mapped_type(value); // copy ctor to init
-			m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF
+			// Fill [end(),…,key[ invalid entities, our new key, and then add a new iterator gate at the end;
+			// resize, make sure to keep a valid entity ID at the end by adding a new ITERATOR_FENCE
+			m_Data.back().first = INVALID_ENTITY; // reset current iterator gate
+			m_Data.resize(key-FIRST_VALID_ENTITY_ID+2, {INVALID_ENTITY, V()});
+			m_Data.back() = ITERATOR_FENCE;
 		}
-		else if(!item.first) // insert new to middle
+		bool inserted = false;
+		if (m_Data[key-FIRST_VALID_ENTITY_ID].first == INVALID_ENTITY)
 		{
+			inserted = true;
 			++m_Count;
-			new (&item.second) mapped_type(value); // copy ctor to init
-		}
-		else // set existing value
-		{
-			if (oldKey == INVALID_ENTITY)
-				m_Count++;
-			item.second = value; // overwrite existing
 		}
+
+		m_Data[key-FIRST_VALID_ENTITY_ID] = {key, value};
+		return {iterator(&m_Data[key-FIRST_VALID_ENTITY_ID]), inserted};
 	}
 
-	void erase(iterator it)
+	size_t erase(iterator it)
 	{
-		value_type* ptr = it.val;
-		if (ptr->first != INVALID_ENTITY)
+		if (it->first != INVALID_ENTITY && it != end())
 		{
-			ptr->first = INVALID_ENTITY;
-			ptr->second.~T(); // call dtor
+			it->first = INVALID_ENTITY;
+			it->second.~V(); // call dtor
 			--m_Count;
+			return 1;
 		}
+		return 0;
 	}
-	void erase(const entity_id_t key)
-	{
-		if (key < m_BufferSize)
-		{
-			value_type* ptr = m_Buffer + key;
-			if (ptr->first != INVALID_ENTITY)
-			{
-				ptr->first = INVALID_ENTITY;
-				ptr->second.~T(); // call dtor
-				--m_Count;
-			}
-		}
-	}
-	inline void clear()
+
+	size_t erase(const key_type& key)
 	{
-		// orphan whole range
-		value_type* ptr = m_Buffer;
-		value_type* end = m_Buffer + m_BufferSize;
-		for (; ptr != end; ++ptr)
-		{
-			if (ptr->first != INVALID_ENTITY)
-			{
-				ptr->first = INVALID_ENTITY;
-				ptr->second.~T(); // call dtor
-			}
-		}
-		m_Count = 0; // no more valid entities
+		if (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size())
+			return erase(&m_Data.front() + key - FIRST_VALID_ENTITY_ID);
+		return 0;
 	}
 
-	// Operations
-	inline iterator find(const entity_id_t key)
+	void clear()
 	{
-		if (key < m_BufferSize) // is this key in the range of existing entitites?
-		{
-			value_type* ptr = m_Buffer + key;
-			if (ptr->first != INVALID_ENTITY)
-				return ptr;
-		}
-		return m_Buffer + m_BufferSize; // return iterator end()
+		m_Data.clear();
+		m_Count = 0;
+		m_Data.push_back(ITERATOR_FENCE);
 	}
-	inline const_iterator find(const entity_id_t key) const
+
+	iterator find(const key_type& key)
 	{
-		if (key < m_BufferSize) // is this key in the range of existing entitites?
-		{
-			const value_type* ptr = m_Buffer + key;
-			if (ptr->first != INVALID_ENTITY)
-				return ptr;
-		}
-		return m_Buffer + m_BufferSize; // return iterator end()
+		if (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size() && m_Data[key-FIRST_VALID_ENTITY_ID].first != INVALID_ENTITY)
+			return &m_Data.front() + (key - FIRST_VALID_ENTITY_ID);
+		return end();
 	}
-	inline size_t count(const entity_id_t key) const
+
+	const_iterator find(const key_type& key) const
 	{
-		if (key < m_BufferSize)
-		{
-			if (m_Buffer[key].first != INVALID_ENTITY)
-				return 1;
-		}
-		return 0;
+		if (key-FIRST_VALID_ENTITY_ID+1 < m_Data.size() && m_Data[key-FIRST_VALID_ENTITY_ID].first != INVALID_ENTITY)
+			return &m_Data.front() + (key - FIRST_VALID_ENTITY_ID);
+		return end();
 	}
+#undef ITERATOR_FENCE
 };
 
 template<class VSerializer>
@@ -273,7 +218,7 @@
 			V v;
 			deserialize.NumberU32_Unbounded("key", k);
 			VSerializer()(deserialize, "value", v);
-			value.insert(k, v);
+			value.insert_or_assign(k, v);
 		}
 	}
 };
Index: ps/trunk/source/simulation2/tests/test_EntityMap.h
===================================================================
--- ps/trunk/source/simulation2/tests/test_EntityMap.h
+++ ps/trunk/source/simulation2/tests/test_EntityMap.h
@@ -34,28 +34,28 @@
 	{
 	}
 
-	void test_insert()
+	void test_insert_or_assign()
 	{
-		EntityMap<int> test;
+		EntityMap<int, 1> test;
 
 		TS_ASSERT(test.empty());
 
-		test.insert(1,1);
-		test.insert(2,2);
-		test.insert(3,3);
-		test.insert(4,4);
-		test.insert(4,5);
-		test.insert(4,6);
+		test.insert_or_assign(1,1);
+		test.insert_or_assign(2,2);
+		test.insert_or_assign(3,3);
+		test.insert_or_assign(4,4);
+		test.insert_or_assign(4,5);
+		test.insert_or_assign(4,6);
 
-//		TS_ASSERT(test.m_Data.size() == 5);
-//		TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
+		TS_ASSERT(test.m_Data.size() == 5);
+		TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
 		TS_ASSERT(test.size() == 4);
 		TS_ASSERT(test.find(3)->second == 3);
 		TS_ASSERT(test.find(4)->second == 6);
 
-		test.insert(10,7);
-//		TS_ASSERT(test.m_Data.size() == 11);
-//		TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
+		test.insert_or_assign(10,7);
+		TS_ASSERT(test.m_Data.size() == 11);
+		TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
 		TS_ASSERT(test.size() == 5);
 		TS_ASSERT(test.find(4)->second == 6);
 		TS_ASSERT(test.find(5) == test.end());
@@ -65,39 +65,39 @@
 		TS_ASSERT(test.find(9) == test.end());
 		TS_ASSERT(test.find(10)->second == 7);
 
-//		EntityMap<int, 5> test2;
+		EntityMap<int, 5> test2;
 
-//		test2.insert(8,5);
-//		TS_ASSERT(test2.find(8)->second == 5);
-//		TS_ASSERT(test2.m_Data.size() == 5);
-//		TS_ASSERT(test2.size() == 1);
+		test2.insert_or_assign(8,5);
+		TS_ASSERT(test2.find(8)->second == 5);
+		TS_ASSERT(test2.m_Data.size() == 5);
+		TS_ASSERT(test2.size() == 1);
 
 	}
 	void test_iterators()
 	{
-		EntityMap<int> test;
+		EntityMap<int, 1> test;
 
-		test.insert(1,1);
-		test.insert(2,2);
-		test.insert(3,3);
-		test.insert(4,4);
+		test.insert_or_assign(1,1);
+		test.insert_or_assign(2,2);
+		test.insert_or_assign(3,3);
+		test.insert_or_assign(4,4);
 
-		EntityMap<int>::iterator it = test.begin();
+		EntityMap<int, 1>::iterator it = test.begin();
 		TS_ASSERT(it->first == 1);
-		++it;
+		it++;
 		TS_ASSERT(it->first == 2);
-		++it; // it++ incorrectly returns a pointer in svn
+		++it;
 		TS_ASSERT(it->first == 3);
 		it = test.end();
-//		TS_ASSERT(it->first == test.m_Data.back().first);
+		TS_ASSERT(it->first == test.m_Data.back().first);
 
-		EntityMap<int>::const_iterator cit = test.begin();
+		EntityMap<int, 1>::const_iterator cit = test.begin();
 		TS_ASSERT(cit->first == 1);
 		cit = test.end();
-//		TS_ASSERT(cit->first == test.m_Data.back().first);
+		TS_ASSERT(cit->first == test.m_Data.back().first);
 
 		size_t iter = 0;
-		for (EntityMap<int>::value_type& v : test)
+		for (EntityMap<int, 1>::value_type& v : test)
 		{
 			++iter;
 			TS_ASSERT(test.find(iter)->second == (int)iter);
@@ -107,80 +107,80 @@
 
 		test.clear();
 
-		test.insert(10,1);
-		test.insert(20,2);
-		test.insert(30,3);
-		test.insert(40,4);
+		test.insert_or_assign(10,1);
+		test.insert_or_assign(20,2);
+		test.insert_or_assign(30,3);
+		test.insert_or_assign(40,4);
 
 		it = test.begin();
 		TS_ASSERT(it->second == 1);
-		++it; // it++ incorrectly returns a pointer in svn
+		it++;
 		TS_ASSERT(it->second == 2);
 		++it;
 		TS_ASSERT(it->second == 3);
 		it = test.end();
-//		TS_ASSERT(it->first == test.m_Data.back().first);
+		TS_ASSERT(it->first == test.m_Data.back().first);
 
 	}
 
 	void test_erase()
 	{
 		EntityMap<int> test;
-		test.insert(1,1);
-		test.insert(2,2);
-		test.insert(3,3);
-		test.insert(4,4);
+		test.insert_or_assign(1,1);
+		test.insert_or_assign(2,2);
+		test.insert_or_assign(3,3);
+		test.insert_or_assign(4,4);
 
 		test.erase(2);
 
-//		TS_ASSERT(test.m_Data.size() == 5);
+		TS_ASSERT(test.m_Data.size() == 5);
 		TS_ASSERT(test.size() == 3);
 		TS_ASSERT(test.find(2) == test.end());
 
 		test.erase(1);
 		test.erase(3);
-		test.erase(4);//		TS_ASSERT(test.erase(4) == 1);
+		TS_ASSERT(test.erase(4) == 1);
 
-//		TS_ASSERT(test.m_Data.size() == 5);
+		TS_ASSERT(test.m_Data.size() == 5);
 		TS_ASSERT(test.size() == 0);
 
-		test.erase(5);//		TS_ASSERT(test.erase(5) == 0);
+		TS_ASSERT(test.erase(5) == 0);
 
-		test.insert(1,1);
-		test.insert(2,2);
-		test.insert(3,3);
-		test.insert(4,4);
+		test.insert_or_assign(1,1);
+		test.insert_or_assign(2,2);
+		test.insert_or_assign(3,3);
+		test.insert_or_assign(4,4);
 
 		test.erase(test.begin());
-//		TS_ASSERT(test.m_Data.size() == 5);
+		TS_ASSERT(test.m_Data.size() == 5);
 		TS_ASSERT(test.size() == 3);
 		TS_ASSERT(test.find(1) == test.end());
 
-//		TS_ASSERT(test.erase(test.end()) == 0);
-//		TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
+		TS_ASSERT(test.erase(test.end()) == 0);
+		TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY);
 	}
 
 	void test_clear()
 	{
 		EntityMap<int> test;
-		test.insert(1,1);
-		test.insert(2,2);
-		test.insert(3,3);
-		test.insert(4,4);
+		test.insert_or_assign(1,1);
+		test.insert_or_assign(2,2);
+		test.insert_or_assign(3,3);
+		test.insert_or_assign(4,4);
 
 		test.clear();
 
-//		TS_ASSERT(test.m_Data.size() == 1);
+		TS_ASSERT(test.m_Data.size() == 1);
 		TS_ASSERT(test.size() == 0);
 	}
 
 	void test_find()
 	{
 		EntityMap<int> test;
-		test.insert(1,1);
-		test.insert(2,2);
-		test.insert(3,3);
-		test.insert(40,4);
+		test.insert_or_assign(1,1);
+		test.insert_or_assign(2,2);
+		test.insert_or_assign(3,3);
+		test.insert_or_assign(40,4);
 
 		TS_ASSERT(test.find(1)->second == 1);
 		TS_ASSERT(test.find(40)->second == 4);
@@ -194,9 +194,9 @@
 
 		double t = timer_Time();
 		for (int i = 1; i <= 200000; ++i)
-			test.insert(i,i);
+			test.insert_or_assign(i,i);
 		double tt = timer_Time() - t;
-		printf("inserting 200K elements in order: %lfs\n", tt);
+		printf("insert_or_assigning 200K elements in order: %lfs\n", tt);
 
 		t = timer_Time();
 		for (int i = 1; i <= 200000; ++i)
@@ -206,9 +206,9 @@
 
 		t = timer_Time();
 		for (int i = 200000; i >= 1; --i)
-			test.insert(i,i);
+			test.insert_or_assign(i,i);
 		tt = timer_Time() - t;
-		printf("inserting 200K elements in reverse order: %lfs\n", tt);
+		printf("insert_or_assigning 200K elements in reverse order: %lfs\n", tt);
 
 		t = timer_Time();
 		for (auto i = test.begin(); i != test.end(); ++i)
@@ -229,7 +229,7 @@
 		std::random_shuffle(vec.begin(), vec.end());
 
 		for (int i = 1; i <= 200000; ++i)
-			test.insert(i,i);
+			test.insert_or_assign(i,i);
 
 		t = timer_Time();
 		for (int i = 1; i <= 200000; ++i)
@@ -246,7 +246,7 @@
 		test.clear();
 
 		for (int i = 1; i <= 200000; ++i)
-			test.insert(i*5,i);
+			test.insert_or_assign(i*5,i);
 
 		t = timer_Time();
 		for (EntityMap<int>::value_type& p : test)
@@ -257,7 +257,7 @@
 		test.clear();
 
 		for (int i = 1; i <= 4000; ++i)
-			test.insert(i*50,i);
+			test.insert_or_assign(i*50,i);
 
 		t = timer_Time();
 		for (EntityMap<int>::value_type& p : test)
@@ -268,7 +268,7 @@
 		test.clear();
 
 		for (int i = 1; i <= 200000; ++i)
-			test.insert(i*50,i);
+			test.insert_or_assign(i*50,i);
 
 		t = timer_Time();
 		for (EntityMap<int>::value_type& p : test)
@@ -279,7 +279,7 @@
 		test.clear();
 
 		for (int i = 1; i <= 2000000; ++i)
-			test.insert(i*50,i);
+			test.insert_or_assign(i*50,i);
 
 		t = timer_Time();
 		for (EntityMap<int>::iterator i = test.begin(); i != test.end(); ++i)
@@ -288,7 +288,7 @@
 		printf("manual ++iteration on 2000K sparse (holes of 50) (warmup 1): %lfs\n", tt);
 
 		t = timer_Time();
-		for (EntityMap<int>::iterator i = test.begin(); i != test.end(); ++i)
+		for (EntityMap<int>::iterator i = test.begin(); i != test.end(); i++)
 			i->second = 3;
 		tt = timer_Time() - t;
 		printf("manual ++iteration on 2000K sparse (holes of 50) (warmup 2): %lfs\n", tt);
@@ -300,7 +300,7 @@
 		printf("manual ++iteration on 2000K sparse (holes of 50): %lfs\n", tt);
 
 		t = timer_Time();
-		for (EntityMap<int>::iterator i = test.begin(); i != test.end(); ++i)
+		for (EntityMap<int>::iterator i = test.begin(); i != test.end(); i++)
 			i->second = 3;
 		tt = timer_Time() - t;
 		printf("manual iteration++ on 2000K sparse (holes of 50): %lfs\n", tt);