C / C++ / MFC

doug25 wrote:

what i'm trying to do is optimize my program
so that that i can very quickly access a value
in an array by it's key. i'm only interested in
using integer values as key's.

doug25 wrote:

it might be faster to make a custom implementation

#include "hr_time.h"
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

struct Object
{
	int value;

	Object()
	{
		value = 1;
	};

	~Object(){};
};

map<int, Object> m;
vector<int> ids;
vector<Object> v;

int main()
{
	CStopWatch s;
	double time;
	int i, value;

	// time taken to get the values of
	// 10000 elements with id's using a map

	for(i = 0; i < 10000; i++)
		m.insert(make_pair(i,Object()));

	s.startTimer();

	for(i = 0; i < 10000; i++)
		value = m[i].value;

	s.stopTimer();

	time = s.getElapsedTime();

	// time = 0.061847 seconds

	// time taken to get the values of
	// 10000 elements with id's using a vector

	for(i = 0; i < 9999; i++)
	{
		ids.push_back(i);
		v.push_back(Object());
	}

	ids.push_back(20000); // id of the 10000th element = 20000
	v.push_back(Object());

	sort(ids.begin(), ids.end());

	int pos;

	s.startTimer();

	for(i = 0; i < 9999; i++)
	{
		pos = (int)(lower_bound(ids.begin(), ids.end(), i) - ids.begin());
		value = v[pos].value;
	}

	pos = (int)(lower_bound(ids.begin(), ids.end(), 20000) - ids.begin());
	value = v[pos].value;

	s.stopTimer();

	time = s.getElapsedTime();

	// time = 0.850772 seconds

	return 0;
}

#include <vector>
#include <algorithm>
#include <iostream>

template <class Key, class Value>
bool CompareKeys(std::pair<Key, Value> const& left,
                 std::pair<Key, Value> const& right)
{
   return left.first < right.first;
}

template <class Key, class Value>
typename std::vector<std::pair<Key, Value> >::const_iterator 
Find(std::vector<std::pair<Key, Value> > const& vec, Key const& key)
{
   typename std::vector<std::pair<Key, Value> >::const_iterator
      found = std::lower_bound(vec.begin(), vec.end(),
                               std::make_pair(key, Value()), // int value doesn't matter
                               &CompareKeys<Key, Value>);

   if (found != vec.end() && found->first != key) return vec.end();
   return found;
}


int main (int argc, char const *argv[])
{
   typedef std::pair<std::string, int> MyPair;
   
   std::vector<MyPair> associativeVector;
   
   associativeVector.push_back(std::make_pair("Value", 40));
   associativeVector.push_back(std::make_pair("Hello", 10));
   associativeVector.push_back(std::make_pair("Test", 30));
   associativeVector.push_back(std::make_pair("Goodbye", 20));
   std::sort(associativeVector.begin(), associativeVector.end(),
             &CompareKeys<std::string, int>);
   
   std::vector<MyPair>::const_iterator found = Find(associativeVector, std::string("Test"));

   if (found != associativeVector.end())
   {
      std::cout << found->first << " = " << found->second << std::endl;
   }
   else std::cout << "Test not found \n";

   found = Find(associativeVector, std::string("NotThere"));

   if (found != associativeVector.end())
   {
      std::cout << found->first << std::endl;
      std::cout << found->second << std::endl;
   }
   else std::cout << "NotThere not found \n";

   return 0;
}

vector          map

0.00141          0.00093
0.00139          0.00085
0.00156          0.00085

seconds