appropriate container?

[Howard]

I'm converting some old handle-based code, updating it to use stl
containers. I've wondering if someone can suggest the proper container type
for the following:

I've got a bunch of bitmaps (stored as resources in a Windows program), each
identified by a resource ID (a short integer, say). I'll be loading them
all into memory and creating my own object (CachedPic) to hold (and later
manipulate) each image. So what I'll have is an association between a short
and a CachedPic.

I'll only be inserting them all once, deleting once when the program ends,
and retrieving pointers (references? iterators?) to the objects often. I
need fast access via the id.

I'm thinking that maybe a map<short,CachedPic> would be the answer, but I'm
not sure. Maybe map<short,CachedPic*>?

I don't really need to sort the objects, except that that probably makes
retrieval faster, I'd assume. Which is why I'm thinking map. Usually I use
vectors instead of arrays, but I thought maybe since I need to retrieve
specific items based on an id, a map might be faster.

I think I need to get a better book on the stl, since the one I have (the
C++ Programming Lanugage, Stroustrup) is technically complete but short on
examples (at least ones I find useful, in this case). But in the meantime,
if someone could give me their opinion on what container I should use, and
whether to store the object or a pointer there, I'd appreciate it.

Many thanks,

Howard

 

[Victor Bazarov]

I'm converting some old handle-based code, updating it to use stl
containers. I've wondering if someone can suggest the proper container type
for the following:

I've got a bunch of bitmaps (stored as resources in a Windows program), each
identified by a resource ID (a short integer, say). I'll be loading them
all into memory and creating my own object (CachedPic) to hold (and later
manipulate) each image. So what I'll have is an association between a short
and a CachedPic.

I'll only be inserting them all once, deleting once when the program ends,
and retrieving pointers (references? iterators?) to the objects often. I
need fast access via the id.

I'm thinking that maybe a map<short,CachedPic> would be the answer, but I'm
not sure. Maybe map<short,CachedPic*>?

If copying of 'CachedPic' object is expensive (and probably is considering
that it holds an image), then storing pointers is better.

I don't really need to sort the objects, except that that probably makes
retrieval faster, I'd assume. Which is why I'm thinking map. Usually I use
vectors instead of arrays, but I thought maybe since I need to retrieve
specific items based on an id, a map might be faster.

Sounds about right.

I think I need to get a better book on the stl, since the one I have (the
C++ Programming Lanugage, Stroustrup) is technically complete but short on
examples (at least ones I find useful, in this case). But in the meantime,
if someone could give me their opinion on what container I should use, and
whether to store the object or a pointer there, I'd appreciate it.

Hope my short reply reaffirms some of your thoughts already.

V

 

[Howard Hinnant]

I'm converting some old handle-based code, updating it to use stl
containers. I've wondering if someone can suggest the proper container type
for the following:

I've got a bunch of bitmaps (stored as resources in a Windows program), each
identified by a resource ID (a short integer, say). I'll be loading them
all into memory and creating my own object (CachedPic) to hold (and later
manipulate) each image. So what I'll have is an association between a short
and a CachedPic.

I'll only be inserting them all once, deleting once when the program ends,
and retrieving pointers (references? iterators?) to the objects often. I
need fast access via the id.

I'm thinking that maybe a map<short,CachedPic> would be the answer, but I'm
not sure. Maybe map<short,CachedPic*>?

I don't really need to sort the objects, except that that probably makes
retrieval faster, I'd assume. Which is why I'm thinking map. Usually I use
vectors instead of arrays, but I thought maybe since I need to retrieve
specific items based on an id, a map might be faster.

I'd start with a std::map<short, CachedPic>. If you encapsulate your
container choice with typedefs or an enclosing class, then you can
always easily optimize later (choose another container).

If you go with map<short,CachedPic*>, you still have to store your
CachedPic somewhere and (copy it there), and you have the added
complication of managing that extra storage space and making sure
pointers into it are stable. That's not to say that
map<short,CachedPic*> wouldn't be better, just that it is more
complicated, and you can always change to it if profiling (or some other
constraint) suggests it. But I'd start simple.

If the one copy of the CachedPic into the map is really killing you, you
could give CachedPic a default ctor and:

CachedPic& cp = my_map[id];
infile >> cp;

That is, enter a default constructed CachedPic into the map, and then
read your data directly into the map.

Other possibilities include:

vector<pair<short, CachedPic> > // manually sort and lookup with
lower_bound
hash_map<short, CachedPic> // unsorted but fast lookup

The hash_map is likely to have the fastest lookup time, but you pay a
price in the risk of the hash_map changing out from under you (as it is
commonly supplied but non-standard). Still, easy to change if properly
encapsulated though.

If your id's are simply sequential numbers starting with 0, you can
easily create a perfect hash simply with:

vector<CachedPic>

i.e. the id is the index into the vector.

I think I need to get a better book on the stl, since the one I have (the
C++ Programming Lanugage, Stroustrup) is technically complete but short on
examples (at least ones I find useful, in this case). But in the meantime,
if someone could give me their opinion on what container I should use, and
whether to store the object or a pointer there, I'd appreciate it.

My personal favorite is http://www.josuttis.com/libbook/ but there are
several good ones out there.

-Howard

 

[Howard]

Thanks, guys... looks like map<short,CachedPic*> is working out fine.

-Howard

 

[Alf P. Steinbach]

* Howard:

Thanks, guys... looks like map<short,CachedPic*> is working out fine.

For efficiency consider a std::vector.

 

[Howard]

* Howard:

For efficiency consider a std::vector.

I did, but since my ids are not in order from 0..n-1, and may be inserted in
somewhat random order, I think map will be better. Agreed? It's mainly the
"find" time I want to reduce, and get rid of the current looping through an
array of ids to locate the index for an array of handles that was previously
in place.

-Howard

 

[Alf P. Steinbach]

* Howard:

I did, but since my ids are not in order from 0..n-1, and may be inserted in
somewhat random order, I think map will be better. Agreed?

Two ways.

Use consecutive id's.

Or use the vector indices instead of id's (you only need the id's to retrieve
the resources -- presumably you're not updating the resources).

It's mainly the
"find" time I want to reduce, and get rid of the current looping through an
array of ids to locate the index for an array of handles that was previously
in place.

"find" time is minimum when you use a direct index or pointer.