Re: suitable data structure

In article <1189154863.983749.279180@o80g2000hse.googlegroups.com>,
sam_cit@yahoo.co.in says...


I'd probably set up the categories as a vector of strings, and elsewhere
just store the index into that vector. Given a maximum of 200 items, the
data structure you use probably won't make a big difference -- almost
anything you do will be fairly fast.

OTOH, it won't hurt to use something like std::map (or multimap, if a
name can fall into more than one category). If you need to do lookups in
both directions fairly frequently, I'd consider building it as a two-way
mapping: the map holds names and for each an index into the vector of
categories. Each category would hold a string for the category name, and
a vector of iterators to names that fall into that category:

struct reverse_mapping;

typedef std::map<std::string, std::vector<reverse_mapping>::iterator>
name_map;

struct reverse_mapping {
    std::string category;
    std::vector<name_map::iterator> people;

    reverse_mapping(std::string n) : category(n) {}
    bool operator==(reverse_mapping const &other) {
        return category == other.category;
    }
};

name_map f_map;
std::vector<reverse_mapping> r_map;

I'd guess the 10 categories are pre-set and remain constant, while
people can be added and deleted dynamically (though this doesn't make a
huge difference). Initializing the vector of category names is just a
matter of reading in the names (e.g. from a disk file or array) and
pushing each onto the back of r_map. From there, adding a new person
looks something like this:

    std::vector<reverse_mapping>::iterator f =
        std::find(r_map.begin(), r_map.end(), category);

    // first update forward map
    std::pair<name_map::iterator, bool> pos =
        f_map.insert(std::make_pair(name, f));

    // then update reverse map with value returned by insert above
    f->people.push_back(pos.first);

The category associated with a person is found at:

        f_map.find(name)->second->category

The people in a category are found at:

    std::vector<reverse_mapping>::iterator r =
        std::find(r_map.begin(), r_map.end(), category);

    // the names are in r->people->first

Note that since 'people' is a vector, this is a list of names you'd need
to iterate through to see them all.

--
    Later,
    Jerry.

The universe is a figment of its own imagination.