Alf P. Steinbach
9/21/2009 1:49:00 AM
* Patricia Shanahan:
> Ramon F Herrera wrote:
>> On Sep 20, 12:37 am, Richard Heathfield <r...@see.sig.invalid> wrote:
>>> [I'm reading this in comp.programming]
>>>
>>> In <c10b023a-bf7b-4067-8fd9-39751fed6...@v2g2000vbb.googlegroups.com>,
>>> Ramon F Herrera wrote:
>>>> Is there a type of map which preserves the order of insertion?
>>> Why not just wrap up a vector and a map in your own class? Vector of
>>> keys (indexed on insertion order), and perhaps keep a note of the
>>> insertion order in the payload for the map, so that you can shift
>>> back to the vector when required?
>>
>> That was exactly my idea (the first of your two suggestions), but
>> wanted to check first, before trying to roll my own.
>
> If deletion speed matters, consider using a doubly linked list, where
> either the linked list element is the map payload or the map payload
> contains a pointer to it.
I think the problem is underspecified, thus any particular implementation choice
perhaps a bit premature.
For example, what should
MySequentialMap<int, char const*> map;
map[1] = "One";
map[2] = "Two";
map[3] = "Three";
map[1] = "Uno";
for( Iter it = map.begin(); it != map.end(); ++it )
{
cout << it->second << endl;
}
produce?
How about if, between the last two assignments, the original [1] entry is
deleted? Does it even make sense to talk about deletion here?
Cheers,
- Alf