Hi Everyone,
I have the following set of data and currently i'm using an array of
structures to represent the same, i would like to know if any other
data structure would be suitable.
name category
sam friend
rahul family
alex office
selina friend
yukiko family
keith office
meet office
I can have a maximum of 200 records, and a maximum category of 10. My
search would be based on both name and category and i was wondering if
any other data structure could be used to reduce my search time on the
list of data.
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:
air<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.
