|
There is some articles about serial communication here[^].
|
|
|
|
|
hi,
i understand how to use the std::map class
and can access a value in a map by using
map[key]
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.
i was wondering how the map class is implemented to
find element value's from keys instead of zero based indices ?
is it possible to make a custom implementation of a key (integer), value array and does anyone know how to do it ?
thanks
|
|
|
|
|
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.
And why don't you want to use a std::map for the purpose?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
well, i'm not sure how a map uses the key to get a value, i thought since it's a std container it might be faster to make a custom implementation using a dynamic array. i've heard that dynamic arrays are faster than vector's for example, though i've not tested this myself. i'm also eager to know how the map uses an integer value as a key to get an element's value. hope i'm making sense
|
|
|
|
|
std::map::find will do this for you.
This will be the fastest, trust me.
|
|
|
|
|
doug25 wrote: it might be faster to make a custom implementation
You are talking in terms of pico/atto seconds. Unless you are trying to do billions of accesses per second this will not be a problem.
|
|
|
|
|
i don't think i'm doing that many accesses i'll take your word for it
thanks for helping
|
|
|
|
|
Firstly, measure the performance to see if the std::map lookups are causing a problem.
If it is, then you'll find lookup performance can be improved using a std::vector of (key, value) pairs which has been sorted by key value and then using std::lower_bound to do the lookups.
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
hi, I made a little test program, to check the performance of a map compared with a vector.
i'm not sure if the method i've used here for key value pairs using a vector is what you meant ? but using a vector for key value look-ups the way i have is much slower than using a map. Here's the test app :
If you know of a way I could improve the performance, i'd be greatful to know ?, thanks
#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;
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();
for(i = 0; i < 9999; i++)
{
ids.push_back(i);
v.push_back(Object());
}
ids.push_back(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();
return 0;
}
|
|
|
|
|
I meant use a single vector - instead of std::map<KeyType, ValueType> , use std::vector<std::pair<KeyType, ValueType> >
Yes, you need to write special comparison functions to just look at the key, but then you don't need to do any indexing - you can just use the iterators returned by lower_bound.
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
I don't understand how to use lower_bound on a vector< pair<keytype, valuetype=""> > ?
if i write lower_bound(v.begin(), v.end(), key) for example what would the key be ?
i'm a bit confused about what you mean by comparison functions to look at the key ?
just so i know we're on the same wavelength, the result i'm looking for is to be able to retrieve a value (object) in an array by using the key associated with that value. so in a pseudo sort of way i'd be able to do this : value = getValueFromVector(key). ?
|
|
|
|
|
Here's a sample program
#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()),
&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;
}
The function CompareKeys is a generic key-ordering function, while Find can be used for any sorted vector (so long as the type Value can be default constructed).
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
Thanks very much for posting this.
unfortunatly the performance isn't as fast as using a map.
for getting the values of 10000 elements using associativeVector with int keys, the time taken was in the range of 0.7 - 0.8 seconds compared with 0.06 seconds using a map.
i don't know how the implementation of a map works but it seems to be the fastest method for doing key lookups.
thanks again. Seeing the associative vector method was very useful.
|
|
|
|
|
Mmmm - that seems strange - I moved to that implementation from a std::map purely because its measured performance was better
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
i can't spot any problems with my test code. did you test the performance yourself ?
|
|
|
|
|
In the application where I used an associative vector in place of a map, yes. It gave me a significant improvement.
I'll maybe have a closer look tomorrow
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
cool, if you decide to investigate, i'd like to know what you find.
|
|
|
|
|
For this example, map is faster. But are you using Debug mode for your timings? I got a factor of 12 difference in debug mode, 3 in release mode.
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
i forgot switching to release mode might make a difference. Though the map stills performs faster with all speed optimazations enabled in release mode. I tested for a million elements and ten thousand, the speed difference of a vector and map seems more marginal when retrieving the values of a million elements but the map performs faster in both cases.
Here's what I got for ten thousand :
vector map
0.00141 0.00093
0.00139 0.00085
0.00156 0.00085
seconds
|
|
|
|
|
I suspect the other thing that can affect the performance is the key type.
All I know is that for my particular application, maps were slower
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
|
|
|
|
|
I guess it's useful to know both methods then.
i'll use a map for the project i'm doing at the moment.
thanks for your help
|
|
|
|
|
This program runs fine except when I try to delete/remove/erase an item as indicated below. No matter what I've tried with erasethe program crashes.
Could someone please help here.
Thanks
Alan Kurlansky
PS. When I cut and pasted some characters got changed. I hope I fixed alll of them.
// MultiMap.cpp : Defines the entry point for the console application.
//
#include <windows.h>
#include <stdio.h>
#include <iostream>
#include <string>
#include <map>
using namespace std;
void testmultimap();
#include <tchar.h>
struct ASK {
int ival;
string key;
};
multimap<string, ASK *> mymm2;
multimap<string, ASK *>::iterator iter;
pair<multimap<string, ASK> ::iterator,multimap<string, ASK *>::iterator> ret;
int _tmain(int argc, _TCHAR* argv[])
{
testmultimap();
return 0;
}
//----------------------------------------------------------------------------------------------------------------
void testmultimap()
{
string key;
key.clear();
key.append("a");
ASK * Iptr = new ASK;
Iptr->ival = 10;
Iptr->key.clear();
Iptr->key.append(key);
mymm2.insert(pair<string,ASK *>(key, Iptr));
key.clear();
key.append("a");
Iptr = new ASK;
Iptr->ival = 20;
Iptr->key.clear();
Iptr->key.append(key);
mymm2.insert(pair<string,ASK *>(key, Iptr));
key.clear();
key.append("b");
Iptr = new ASK;
Iptr->ival = 30;
Iptr->key.clear();
Iptr->key.append(key);
mymm2.insert(pair<string,ASK *>(key, Iptr));
key.clear();
key.append("a");
ret = mymm2.equal_range(key);
int cnt(0);
for (iter=ret.first; iter!=ret.second; ++iter) {
printf("ival:%d key:[%s]\n", (*iter).second->ival, (*iter).second->key.c_str() );
// delete this single entry
// mymm2.erase(????);
}
printf("\n");
printf("2nd pass after 'a' erase\n");
ret = mymm2.equal_range(key);
for (iter=ret.first; iter!=ret.second; ++iter) {
printf("ival:%d key:[%s]\n", (*iter).second->ival, (*iter).second->key.c_str() );
}
printf("\n");
key.clear();
key.append("b");
ret = mymm2.equal_range(key);
for (iter=ret.first; iter!=ret.second; ++iter) {
printf("ival:%d key:[%s]\n", (*iter).second->ival, (*iter).second->key.c_str() );
}
printf("\n");
}
//----------------------------------------------------------------------------------------------------------------
|
|
|
|
|
When you modify the contents of a container, the iterators become invalid.
I believe that is what is happening here.
|
|
|
|
|
Thanks! I made a change that reflects what you said and all seems to be working now.
|
|
|
|
|
Hi,
I've run into a problem with the TransparentBlt function.
When I use TransparentBlt with a 24-bit bitmap it correctly masks the specified transparent color, but when I call it for a 4-bit or 8-bit bitmap, it doesn't make that color transparent.
For example, if I have a bitmap with a large rectangle of MAGENTA color and give RGB(255,0,255) as the last parameter in the function, the magenta is still there with a 4-bit bitmap, but it's masked with the 32-bit one.
This problem might be because 256-color/16-color bitmaps don't use RGB values. May be they use palettes somehow.
Can anyone help with that.
There is sufficient light for those who desire to see, and there is sufficient darkness for those of a contrary disposition.
Blaise Pascal
|
|
|
|
|