i have to search a process table which is populated by the names of processes running on a given set of ip adresses. currently i am using multimaps in C++ with process name as key and ip address as the value. is there any other efficient data structure which can do the same task. also can i gain any sort of parallelism by using pthreads ? if so can anyone point me into a right direction
views:
82answers:
3
+1
A:
You do not need parallelism to access a data structure in RAM of several thousand entries. You can just lock over it (making sure only one process/thread accesses it at the time), and ensure the access is sufficient enough. Multimap is okay. A hashmap would be better though.
Pavel Radzivilovsky
2010-02-07 04:46:28
+1
A:
What is typical query to your table?
Try to use hashmap, it can be faster for big tables.
How do you store names and IP? UTF, string, char*? Ip as uint32 or string?
For readonly structure with a lot of read queries you can benefit from several threads.
upd: use std::unordered_multimap from #include <tr1/unordered_map>
osgx
2010-02-07 04:48:47
names are stored as string
gunjit
2010-02-07 04:50:14
and a typical query is finding is a certain process is running or not .. if running report ip addresses
gunjit
2010-02-07 04:50:51
Use ext/hash_map file and class __gnu_cxx::hash_multimap in gcc 4.1 and earlier
osgx
2010-02-07 05:11:04
In new Gcc (e.g. 4.4) use std::unordered_multimap from tr1_impl/unordered_map file
osgx
2010-02-07 05:12:44
`tr1/unordered_map` not tr1_impl, sorry
osgx
2010-02-07 22:19:38
A:
Depending on the size of the table, you may find a hash table more efficient than the multimap container (which is implemented with a balanced binary tree).
The hash_multimap data structure implements a hash table STL container, and could be of use to you.
Eli Bendersky
2010-02-07 04:48:51
Its the C++ stdlib, meaning that it is available wherever the standard C++ libraries are. That means practically with all standards compliant compilers for C++.
batbrat
2010-02-07 05:17:03
hash maps are not standard for c++ (in revisions of 1998 and 2003). They will be included in next c++ standard C++0x.GCC have a implementation of pre-standard tr1 in its libstdc++, class name `unordered_multimap`. There was also non-standard ext variand: `hash_multimap`
osgx
2010-02-07 05:32:02
yeah it gives a lot of warning messages ... i also checked the replacement header file in backward_warning.h but its still giving warnings on compiling. the problem is i cannot submit code that is generating warning is there a way to get rid of the warnings
gunjit
2010-02-07 05:57:36
What gcc do you have?Use std::unordered_multimap from tr1_impl/unordered_map
osgx
2010-02-07 06:07:36
`#include <tr1/unordered_map>` and `std::unordered_multimap` must work for gcc 4.3
osgx
2010-02-07 06:19:41