 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Peter Simons
Guest
|
 Posted: Mon Feb 20, 2006 9:06 am Post subject: How to determine the "index" of an element in std::map<>? |
 |
|
Hi,
I need to maintain a set of records in two containers; one being
std::map<>, the other being a plain C array:
struct foo
{
int id;
void * data;
};
struct bar
{
void * data;
void * more_data_that_is_not_in_foo;
};
std::map<int,bar> set_of_extended_foos;
foo * array_of_plain_foos;
Naturally, those two container must be kept in-synch. When I have to
change, say item 4, I perform a std::map<>::find(4) to locate the
record in the map. So far so good. Now I have to change the
corresponding entry in the array too, but the question is how to find
it as fast as possible?
The id space is sparse. I might have ids 1, 3, 4, and 8, so I can't
map the integer directly into an array index. I know, however, that
the entry in array_of_plain_foos has the same position that it has in
the map because the two have the same order. I could perform
std::distance(set_of_extended_foos.begin(), iter); to determine the
index, but I reckon that this operation might be more expensive than
simply doing a binary search for "4" on the array itself.
Is anyone aware of a brilliantly obvious solution that is more
efficient than two separate searches? Does std::map<> offer a way to
search for an element, and to retrieve an iterator to it plus the
information "this is the 'n'th entry" at the same time?
Peter
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
 |
eden
Guest
|
| Posted: Mon Feb 20, 2006 5:06 pm Post subject: Re: How to determine the "index" of an element in std::map<> |
|
|
Peter Simons wrote:
| Quote: | Hi,
I need to maintain a set of records in two containers; one being
std::map<>, the other being a plain C array:
struct foo
{
int id;
void * data;
};
struct bar
{
void * data;
void * more_data_that_is_not_in_foo;
};
...
...
Is anyone aware of a brilliantly obvious solution that is more
efficient than two separate searches? Does std::map<> offer a way to
search for an element, and to retrieve an iterator to it plus the
information "this is the 'n'th entry" at the same time?
Peter
|
Not so briliant, but first that came to mind. Why don't you keep an
index to the foo array in bar?
struct bar
{
int pos;
void * data;
void * more_data_that_is_not_in_foo;
};
goran
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Tue Feb 21, 2006 12:06 am Post subject: Re: How to determine the "index" of an element in std::map<> |
|
|
Peter Simons <simons (AT) cryp (DOT) to> writes:
| Quote: | Hi,
I need to maintain a set of records in two containers; one being
std::map<>, the other being a plain C array:
struct foo
{
int id;
void * data;
};
struct bar
{
void * data;
void * more_data_that_is_not_in_foo;
};
std::map<int,bar> set_of_extended_foos;
foo * array_of_plain_foos;
Naturally, those two container must be kept in-synch.
|
Maybe http://www.boost.org/libs/multi_index could be of some help?
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Dietmar Kuehl
Guest
|
| Posted: Tue Feb 21, 2006 10:06 pm Post subject: Re: How to determine the "index" of an element in std::map<> |
|
|
Peter Simons wrote:
| Quote: | I need to maintain a set of records in two containers; one being
std::map<>, the other being a plain C array:
|
Why would you want to do this in the first place? Just use a plain,
sorted array or a 'std::vector' and use 'std::lower_bound' to
efficiently locate the sought object. If you need a node-base variation
of this approach (i.e. you can't afford moving your objects for
whatever reason), you could just store [smart] pointers to the objects.
Maintaining synchronous containers is likely to be less efficient.
--
<mailto:dietmar_kuehl (AT) yahoo (DOT) com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Guest
|
| Posted: Wed Feb 22, 2006 12:06 pm Post subject: Re: How to determine the "index" of an element in std::map<> |
|
|
Peter Simons wrote:
| Quote: | Hi,
I need to maintain a set of records in two containers; one being
std::map<>, the other being a plain C array:
....
Is anyone aware of a brilliantly obvious solution that is more
efficient than two separate searches? Does std::map<> offer a way to
search for an element, and to retrieve an iterator to it plus the
information "this is the 'n'th entry" at the same time?
|
Note that lower_bound on a sorted array may be slightly faster than
map::find (or map::operator[]).
Consider getting rid of the map, and wrapping your array with as much
of the map interface as you need.
If you really need both containers:
Turning around another suggestion, do the first search in the array.
Have the array elements hold a pointer or iterator to the map elements.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
