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

sashoalm wrote:

This problem might be because 256-color/16-color bitmaps don't use RGB values. May be they use palettes somehow.

Richard MacCutchan wrote:

You are correct, obviously you cannot put RGB(R, G, B) into 4 or 8 bits. The early bitmap types could select a subset of the RGB spectrum and did so by first selecting a palette of colours and then using the color value as an index into the palette set. So the bottom line is that you cannot use all the new functionality with the old 16/256-colour bitmaps.