Re: finding an index in an STL vector<>

From: David Hilsee (davidhilseenews_at_yahoo.com)
Date: 08/31/04 

Date: Mon, 30 Aug 2004 22:30:54 -0400

"Joe Harris" <NO_SPAMjoe.harris@KILL_ALL_SPAMMERSgmail.com> wrote in message
news:XmQYc.54042$_h.36385@bignews3.bellsouth.net...
<snip>
> Hi, this I'm the original poster 'Joe' just using a different new
client...
>
> Thanks for your quick response!
>
> Why do I want an index when I already have an iterator?
>
> Well, I had a class like this:
>
> class foo {
> [other class members]
> string _bar;
> public:
> string bar() { return _bar; } // my reader function
> bar([other parameters], bar) _bar(bar) {} // my constructor
> }
>
> The problem is that I have ten's of millions of objects instantiated
> from this class, and I don't have enough RAM (and my machine can't hold
> anymore than the 1GB it has).
>
> So, since I know that there are only about 10 or 20 unique types of
> 'bar' I would just store them all in a static vector and store an index
> (which only needs to be a char because there are only 10 or 20 unique
> strings) to that vector in each object. So, I ended up with this:
>
> class foo_new {
> [ other class members]
> static vector<string> mystrings;
> char _bar_index; // this is just an index to the mystrings element
> public:
> string bar() { return mystrings[bar_index]; } // my reader function
> foo_new([other parameters], string bar) { // constructor
> int index = distance(strings.begin(), find(strings.begin(),
> strings.end(), bar));
> if(index != strings.end()) {
> _bar_index = index;
> } else {
> _bar_index = strings.size();
> strings.push_back(bar);
> }
> }
> }
>
> So, foo_new objects now have 'char bar_index' instead of 'string bar'
> which will save me hundreds of megabytes.
>
> If you can propose a better way of getting a similar result, I will be
> both grateful and impressed.

Well, I can't think of a better way to do what you're doing. It looks like
a flyweight. However, given that there are tens of millions of these
objects, I would probably verify a few things, if I were you. First, make
sure that there isn't a way you can reduce the number of elements. Can
these objects, or certain member of these objects, be computed on the fly?
Second, make sure that there aren't more members that can benefit from using
that static table. Third, make sure that you are realizing the benefits of
using a char instead of a std::vector<std::string>::size_type and that your
code doesn't accidentally go beyond the range of a char. Other than that,
without knowing anything else, I'd say that the implementation looks pretty
solid.

If the call to distance still looks odd to you, you can use subtraction
instead, or separate it out into two different lines. 

-- 
David Hilsee

Relevant Pages

  • Re: Re: if youll induce Toms locality with landscapes, itll alike invade the sugar
    ... Tomorrow Jay will store the choice, and if Hamza merrily advances it too, the ... fossil will promote beside the welcome bar. ...
    (sci.crypt)
  • accessor/mutator - design flaw
    ... consider the class BAR which has a member data in_use that FOO ... Similarily FOO has member data 'idx' that BAR ... int in_use; ...
    (comp.lang.cpp)
  • Re: Advice Needed on Designing a database
    ... just the amount pledged to give - and *not* the amount actually given each ... what if more than one member lives at ... store only one of each, for each member - what about home phones, work ... before creating a database. ...
    (microsoft.public.access.tablesdbdesign)
  • Re: Library bug or my fault?
    ... The compiler is allowed to assume that p2 (which can only correctly ... point to an actual instance of a "struct Bar") is 4-byte aligned, ... store two bytes to first two bytes of "bar" ... load third byte from address given by p2+2 ...
    (comp.lang.c)
  • Re: A little bit more Humor
    ... happened to notice a female member of his congregation sitting in the ... town bar, drinking beer. ... The reverend thought this was sinful and not something a member of his ... "Mrs Fitzgerald," the reverend said sternly. ...
    (rec.motorcycles)