By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,537 Members | 2,172 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,537 IT Pros & Developers. It's quick & easy.

suitable data structure

P: n/a
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.

Thanks in advance!!!

Sep 7 '07 #1
Share this Question
Share on Google+
2 Replies


P: n/a
On 2007-09-07 10:47, Rahul wrote:
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.
Unless you do something wrong or run on a handheld or embedded system
you should not notice any difference in the time needed to search a record.

If you really want to speed things up use different collections (note:
arrays are bad, use std::vector instead) for each category and sort the
collections, then you should be able to find a record in O(log N) which
is about as good as it gets.

If that is not useful enough you have to provide a more detailed
description of what you want to accomplish and how your data is stored
(giving the definition of the struct would help).

--
Erik Wikström
Sep 7 '07 #2

P: n/a
In article <11**********************@o80g2000hse.googlegroups .com>,
sa*****@yahoo.co.in says...
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::iteratorpeople;

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

name_map f_map;
std::vector<reverse_mappingr_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, boolpos =
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.
Sep 8 '07 #3

This discussion thread is closed

Replies have been disabled for this discussion.