[Boost-users] Re: map with minimal memory footprint

From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2005-03-22 12:47:54

>   6. Re: map with minimal memory footprint (David Abrahams)
> Date: Wed, 16 Mar 2005 09:45:34 -0500
> From: David Abrahams <dave_at_[hidden]>
> Subject: [Boost-users] Re: map with minimal memory footprint
> To: boost-users_at_[hidden]
> Message-ID: <uoedjd4z5.fsf_at_[hidden]>
> Content-Type: text/plain; charset=us-ascii
>
> Toon Knapen <toon.knapen_at_[hidden]> writes:
>
> > Hi all,
> >
> > I'm using a rather big std::map which gives good performance but the
> > memory footprint is a bit too big. So I figured to implement an std::map
> > as an std::vector<std::pair<T1,T2>> but thus with the interface of an
> > std::map on top of it.
>
> Can't be done.  It has the wrong iterator invalidation properties.
> You may be able to implement a useful associative container, but it
> will never be std::map.
>
> --
> Dave Abrahams
> Boost Consulting
> www.boost-consulting.com
>

I believe you, but can you explain what you mean by "iterator
invalidation properties".  I wrote a vector_map once, and it was as
"map-ish" as needed at the time, so I suspect it was just a "useful
associative container", but I'm just curious as to what I was
missing...