Sorting data and creating multiple instances of the same class.

[Daz]

Hello people!

(This post is best viewed using a monospace font).

I need to create a class, which holds 4 elements:
std::string ItemName
int Calories
int Weight
int Density

I need to be able to create about 70 instances of this class, each with
different properties, then I need to sort them three times:
First, by calories. Then do some stuff.
Then by Weight. Then do more stuff.
And finally by Density. After which, I do more stuff.

It was suggested to me yesterday that I should use std::map in order to
sort the data, but I can't see how it would work. For example:


C W D <--(Pure coincidence)
"Fries"------10---159--45-
"Berry"------50---99---65-
"Ice Cream"--90---45---87-
"Hamburger"--4----76---23-

If sorted by Weight (W) should yield:

C W D

"Ice Cream"--90---45---87-
"Berry"------50---99---65-
"Hamburger"--4----76---23-
"Fries"------10---159--45-

I need to sort it by Density and Calories at some point too, yet the
rows need to stay intact.

No, my program isn't really _that_ lame, but that is the one of it's
simplest functions.

If I really can use a std::map, How would I go about doing it? I know I
am missing something really obvious here, but I have spent more hours
than anyone should pondering over this seemingly simple question, and
have not stumbled across any answers.

My next question, is:
Is there any easy way to create 70 instances of my class dynamically,
and iterate through them?

By this I mean, do I have to do:

BBObject Obj1("Berry",50,99,65);
BBObject Obj2("Fries",10,159,45);
BBObject Obj3("Hamburger",4,76,23);

....For 70 objects?

If so, then fair enough. However, if I can do this in a better way, and
somehow make a list so that I can iterate through the object, it would
be fantastic.
The only catch is, that the list order will need to change as I do the
sorting.

N.B. I do not want the code created for me. I am desparately trying to
learn what I can and can't do, along with how to do it. Just when I
think I understand a concept, I am always proved wrong by my own code.
If anyone can offer any advice on the best way to get the results I
need, I would very much appreciate it. Also, if anyone can straighten
me out abut anything I am trying to do which cannot be done, I would
also appreciate it.

Thanks everyone.

Daz

 

[Daz]

If sorted by Weight (W) should yield:

C W D

"Ice Cream"--90---45---87-

Correction:

If sorted by Weight (W) should yield:

C W D

"Ice Cream"--90---45---87-
"Hamburger"--4----76---23-
"Berry"------50---99---65-
"Fries"------10---159--45-

 

[Rolf Magnus]

Hello people!

(This post is best viewed using a monospace font).

I need to create a class, which holds 4 elements:
std::string ItemName
int Calories
int Weight
int Density

I need to be able to create about 70 instances of this class, each with
different properties, then I need to sort them three times:
First, by calories. Then do some stuff.
Then by Weight. Then do more stuff.
And finally by Density. After which, I do more stuff.

It was suggested to me yesterday that I should use std::map in order to
sort the data, but I can't see how it would work.

std::map is mostly useful if you have to sort by only one item. For your
case, I'd suggest std::vector in combination with std::sort and one
comparison function object for each element you want to sort by.

For example:


C W D <--(Pure coincidence)
"Fries"------10---159--45-
"Berry"------50---99---65-
"Ice Cream"--90---45---87-
"Hamburger"--4----76---23-

If sorted by Weight (W) should yield:

C W D

"Ice Cream"--90---45---87-
"Berry"------50---99---65-
"Hamburger"--4----76---23-
"Fries"------10---159--45-

I need to sort it by Density and Calories at some point too, yet the
rows need to stay intact.

No, my program isn't really _that_ lame, but that is the one of it's
simplest functions.

If I really can use a std::map, How would I go about doing it? I know I
am missing something really obvious here, but I have spent more hours
than anyone should pondering over this seemingly simple question, and
have not stumbled across any answers.

My next question, is:
Is there any easy way to create 70 instances of my class dynamically,
and iterate through them?

By this I mean, do I have to do:

BBObject Obj1("Berry",50,99,65);
BBObject Obj2("Fries",10,159,45);
BBObject Obj3("Hamburger",4,76,23);

...For 70 objects?

Again, use std::vector, like:

std::vector<BBOject> objects;
objects.push_back(BBObject("Berry",50,99,65));
objects.push_back(BBObject("Fries",10,159,45));
objects.push_back(BBObject("Hamburger",4,76,23));

If so, then fair enough. However, if I can do this in a better way, and
somehow make a list so that I can iterate through the object, it would
be fantastic.

You can iterate through the vector with something like:

typedef std::vecctor<BBOject>::iterator iterator;

for (iterator it = objects.begin(), end = objects.end(); it != end; ++it)
{
std::cout << *it.ItemName;
}

The only catch is, that the list order will need to change as I do the
sorting.

Look for the std::sort function template, and especially for its third
argument. It can be used to specify a comparison function that will be used
as basis for the sorting.

N.B. I do not want the code created for me. I am desparately trying to
learn what I can and can't do, along with how to do it.

That's good. I hope I gave you neither too much nor too few information.

 

[Daz]

std::map is mostly useful if you have to sort by only one item. For your
case, I'd suggest std::vector in combination with std::sort and one
comparison function object for each element you want to sort by.


Again, use std::vector, like:

std::vector<BBOject> objects;
objects.push_back(BBObject("Berry",50,99,65));
objects.push_back(BBObject("Fries",10,159,45));
objects.push_back(BBObject("Hamburger",4,76,23));


You can iterate through the vector with something like:

typedef std::vecctor<BBOject>::iterator iterator;

for (iterator it = objects.begin(), end = objects.end(); it != end; ++it)
{
std::cout << *it.ItemName;
}


Look for the std::sort function template, and especially for its third
argument. It can be used to specify a comparison function that will be used
as basis for the sorting.


That's good. I hope I gave you neither too much nor too few information.

That's fantastic! Thanks for your help Rolf. You're a diamond!

 

[Daz]

That's fantastic! Thanks for your help Rolf. You're a diamond!

Hello again.

I can't seem to get sort to work. I know I am missing something, and
probably not using the template properly, but I don't understand how. I
have tried at least 30 different things, and each time I just get more
errors.

The code below gives a single error:

void InitializeBBObjects()
{
std::vector<BBObject> objects;
typedef std::vector<BBObject>::iterator iterator;
iterator it = objects.begin(), end = objects.end();

objects.push_back(BBObject(BERRY,50,99,65,"Berry"));
objects.push_back(BBObject(FOOD,10,159,45,"Fries"));
objects.push_back(BBObject(FOOD,4,76,23,"Hamburger"));

std::sort<iterator>(*it, *end); // <-- This is whre the error lies.
}

The above is basically a simple test script to help me try to figure
out how to do a sort. I have used sort before on a list of ints, but I
don't have any idea what I need to change in order to make it work with
a list of my objects.

Any more input would be appreciated (sorry Rolf)

Best wishes.

Daz

 

[Rolf Magnus]

Hello again.

I can't seem to get sort to work. I know I am missing something, and
probably not using the template properly, but I don't understand how. I
have tried at least 30 different things, and each time I just get more
errors.

The code below gives a single error:

void InitializeBBObjects()
{
std::vector<BBObject> objects;
typedef std::vector<BBObject>::iterator iterator;
iterator it = objects.begin(), end = objects.end();

objects.push_back(BBObject(BERRY,50,99,65,"Berry"));
objects.push_back(BBObject(FOOD,10,159,45,"Fries"));
objects.push_back(BBObject(FOOD,4,76,23,"Hamburger"));

Not a good idea. Adding objects to your vector invalidates all iterators
into that vector, so you should create the iterators after your push_back.

std::sort<iterator>(*it, *end); // <-- This is whre the error lies.

std::sort wants iterators, not the objects they point to, so don't use the
dereference operator. Just use:

std::sort(it, end);

or directly:

std::sort(objects.begin(), objects.end());

However, it still won't work that way, because sort needs a way to compare
two objects, and by default it uses operator< for that, which isn't defined
for your objects. Since you want to sort by different elements, you need to
write your own comparison function that compares two objects by the member
you want to sort by.

}

The above is basically a simple test script to help me try to figure
out how to do a sort. I have used sort before on a list of ints, but I
don't have any idea what I need to change in order to make it work with
a list of my objects.

Any more input would be appreciated (sorry Rolf)

You're welcome. A good book about C++ should explain that all. You should
consider getting one. IIRC, the FAQ to this newsgroup contains a list of
candidates.

 

[Daz]

Not a good idea. Adding objects to your vector invalidates all iterators
into that vector, so you should create the iterators after your push_back.


std::sort wants iterators, not the objects they point to, so don't use the
dereference operator. Just use:

std::sort(it, end);

or directly:

std::sort(objects.begin(), objects.end());

However, it still won't work that way, because sort needs a way to compare
two objects, and by default it uses operator< for that, which isn't defined
for your objects. Since you want to sort by different elements, you need to
write your own comparison function that compares two objects by the member
you want to sort by.


You're welcome. A good book about C++ should explain that all. You should
consider getting one. IIRC, the FAQ to this newsgroup contains a list of
candidates.

Mr. Burns mode - ON;
E-e-e-excellent!
Mr Burns mode - OFF;

Thanks again Rolf. It makes complete sense now and to tell the truth, I
already knew the answer, yet for some strange reason, I always seem to
forget the answer right when I most need to remember it.

Thanks for your patience and time. You really have helped me out a lot!

 

[Jerry Coffin]

Hello people!

(This post is best viewed using a monospace font).

I need to create a class, which holds 4 elements:
std::string ItemName
int Calories
int Weight
int Density

I need to be able to create about 70 instances of this class, each with
different properties, then I need to sort them three times:
First, by calories. Then do some stuff.
Then by Weight. Then do more stuff.
And finally by Density. After which, I do more stuff.

Just to clarify, I'm going to explicitly state a couple of
assumptions. First of all, it sounds like the data are basically
static -- i.e. you create all of them, and then after that you won't
add or delete any data; you just need to shuffle the existing data
into different arrangements.

Second, it sounds like you only need to work with one arrangement at
a time -- once you start working with the data in a different order,
you're done working with it in the previous order.

Assuming those are both correct, then a map is probably not your best
choice. You're almost certainly better off using an std::vector, and
then using std::sort to sort the data as needed.

To do that, you generally need to create some predicates (usually as
functors) to do the comparisons correctly:

struct Item {
std::string name;
int calories;
int weight;
int density;
};

struct by_calories {
bool operator<(Item const &a, Item const &b) {
return a.calories < b.calories;
}
};

struct by_weight {
bool operator<(Item const &a, Item const &b) {
return a.weight < b.weight;
}
};

Then you specify the appropriate comparison when you do your sort:

std:vector<Item> items;

// Insert data into vector of items here.

std::sort(items.begin(), items.end(), by_calories());
// simulate processing by printing out:
std::copy(items.begin(), items.end(),
std:stream_iterator<Item>(std::cout, "\n"));

// Now a different order:
std::sort(items.begin(), items.end(), by_weight());
// print out again.
std::copy(items.begin(), items.end(),
std:stream_iterator<Item>(std::cout, "\n"));

Of course, for those 'copy' calls to work, you'd need to define an
operator<< for Item, so the ostream_iterator knows how to write each
item out. That'd typically be pretty simple, just writing out the
data in order, probably with tabs between them.

Now, let's consider what happens if those assumptions are wrong. If
your data is really dynamic, then you probably _do_ want to use
std::map or std::set after all. Since you apparently want to iterate
in a particular order, but don't need to do lookups based on a single
'key' part, you probably want a set instead of a map. In this case,
you'd (again) use comparison predicates like above, but you'd specify
the correct predicate as part of the type of the set:

std::set<Item, by_calories> items_c;
std::set<Item, by_weight> items_w;

Then you'd start by putting the data into items_c, then when you're
done working with it in order by calories, you copy the data to
items_w, so it'll be sorted by weight. After you're done with that
order, you copy it to a set ordered by density, and so on. In each
case, since it's in a set you can efficiently add and/or remove items
on the fly.

If the second assumption is incorrect, and you really want to be able
to access the data in any order at any time efficiently, you need to
maintain all the orders simultaneously. In this case, you'll probably
want to store the data in one place, and then create three separate
indices by which to access the data. In this case, you get a hybrid:
typically a vector to hold the data itself, and either vectors or
sets of pointers to the data (depending on whether you need to
add/delete data on the fly).

 

[Daz]

Just to clarify, I'm going to explicitly state a couple of
assumptions. First of all, it sounds like the data are basically
static -- i.e. you create all of them, and then after that you won't
add or delete any data; you just need to shuffle the existing data
into different arrangements.
Correct!

Second, it sounds like you only need to work with one arrangement at
a time -- once you start working with the data in a different order,
you're done working with it in the previous order.

Not necessarily true, but I do have this in mind for now, yes. Ya know,
you should do this program-mind-reading for a living. You really are
rather good at it.

Assuming those are both correct, then a map is probably not your best
choice. You're almost certainly better off using an std::vector, and
then using std::sort to sort the data as needed.

Amen to that! I love vectors, even though I know next to nothing about
them, they are just so robust and versatile.

To do that, you generally need to create some predicates (usually as
functors) to do the comparisons correctly:
Ok.

struct Item {
std::string name;
int calories;
int weight;
int density;
};
Right.

struct by_calories {
bool operator<(Item const &a, Item const &b) {
return a.calories < b.calories;
}
};
Uhuh.

struct by_weight {
bool operator<(Item const &a, Item const &b) {
return a.weight < b.weight;
}
};

Then you specify the appropriate comparison when you do your sort:

std:vector<Item> items;

// Insert data into vector of items here.

std::sort(items.begin(), items.end(), by_calories());
// simulate processing by printing out:
std::copy(items.begin(), items.end(),
std:stream_iterator<Item>(std::cout, "\n"));

// Now a different order:
std::sort(items.begin(), items.end(), by_weight());
// print out again.
std::copy(items.begin(), items.end(),
std:stream_iterator<Item>(std::cout, "\n"));

Ha! Fantastic! Ingenious! You make it look so easy. I have a nack for
making things more complicated than they might need to be...

Of course, for those 'copy' calls to work, you'd need to define an
operator<< for Item, so the ostream_iterator knows how to write each
item out. That'd typically be pretty simple, just writing out the
data in order, probably with tabs between them.

Sounds simple. However... Simple + me = complicated++

Now, let's consider what happens if those assumptions are wrong. If
your data is really dynamic, then you probably _do_ want to use
std::map or std::set after all. Since you apparently want to iterate
in a particular order, but don't need to do lookups based on a single
'key' part, you probably want a set instead of a map. In this case,
you'd (again) use comparison predicates like above, but you'd specify
the correct predicate as part of the type of the set:

std::set<Item, by_calories> items_c;
std::set<Item, by_weight> items_w;

Then you'd start by putting the data into items_c, then when you're
done working with it in order by calories, you copy the data to
items_w, so it'll be sorted by weight. After you're done with that
order, you copy it to a set ordered by density, and so on. In each
case, since it's in a set you can efficiently add and/or remove items
on the fly.

If the second assumption is incorrect, and you really want to be able
to access the data in any order at any time efficiently, you need to
maintain all the orders simultaneously. In this case, you'll probably
want to store the data in one place, and then create three separate
indices by which to access the data. In this case, you get a hybrid:
typically a vector to hold the data itself, and either vectors or
sets of pointers to the data (depending on whether you need to
add/delete data on the fly).

That's all good and useful, but you really were spot-on with your
assumptions. I am most impressed!

Sorry if any of that sounded sarcastic. I seriously am impressed and
overwhelmed at the help and support some people give, and can only hope
that I too will be able to help fellow coders so efficiently.
Naturally, this also applies to everyone else who has helped me in the
past, too.

I hope I can remember most of that. If I can it would be a great help.
I think I have a memory leak, and need to get around to deploying a
debugging script in my brain.

Many, many thanks to everyone again!

 

[Jerry Coffin]

[ ... ]

Not necessarily true, but I do have this in mind for now, yes. Ya know,
you should do this program-mind-reading for a living. You really are
rather good at it.

That's called "defining requirements", or various other things on
that order -- it's probably the single most crucial part of
programming in general. It's how you minimize the standard "yes,
that's exactly what we asked for, but not at all what we want"
situation.

[ ... ]

Sounds simple. However... Simple + me = complicated++

Oh, well, it'd typically look something like this:

std:stream &operator<<(std:stream &os, Item const &i) {
return os << i.name << "\t"
<< i.calories << "\t"
<< i.weight << "\t"
<< i.density;
}