struct test {
struct test {
int id;
int worth;
};
vector<test> sort(0);
for(int i = 1; i < CREATURES; i++) {
// testing goes here
}
Need help with sorting algoritm
Author
Im trying to write a basic AI application, just to try it out. Now Im trying to code the function that will calculate which of the creatures that should make offsprings and which will be killed. I planned to do it with a vector. The function starts in one end and tests if the value is higher or lower, if its lower it proceeds and when its higher it stops and insert the current test value there.
The tricky part is that I need two values in the vector. One value acts as the ID for the creatures we test and the other one is the value itself. Something like this:
Can I do a vector with a cusom variable type like that? Im getting a bunch of wierd error messages from my compiler so I guess not.
Anyone that can figure out what it is I want to do? :P I need a kick in the right direction...
Yes, you can make a vector of any nonabstract class (as far as I know). You've got other problems in your code, though. You have repeated "struct test {" twice. If that's intentional, they need to have different names.
Also, what are you trying to accomplish with this line?
vector<test> sort(0);
Also, what are you trying to accomplish with this line?
vector<test> sort(0);
Author
Oh sorry... I did write the code directly here and didnt copy it from the compiler, must have confused myself. Correction:
In this line
vector<test> sort(0);
I want to make a vector of that new type I just decleared. I want it to have no elemtes (yet), but is that possible?
The sorting algorithm (I try to explain again :P) goes something like this:
start-> look at the worth of the next element, is my worth higher? yes -> go on... next element, higher? yes -> next? nope... ok Ill stay here then.
So each creature that is tested starts from the beginning of the vector and walks along until it finds an element with a higher worth than itself, then this creature should be here.
Thats why I have no elements there initially. Or I suppose I need to put in the first manually so the sorting algorithm have something to calculate on.
struct test { int id; int worth; }; vector<test> sort(0); for(int i = 1; i < CREATURES; i++) { // testing goes here }In this line
vector<test> sort(0);
I want to make a vector of that new type I just decleared. I want it to have no elemtes (yet), but is that possible?
The sorting algorithm (I try to explain again :P) goes something like this:
start-> look at the worth of the next element, is my worth higher? yes -> go on... next element, higher? yes -> next? nope... ok Ill stay here then.
So each creature that is tested starts from the beginning of the vector and walks along until it finds an element with a higher worth than itself, then this creature should be here.
Thats why I have no elements there initially. Or I suppose I need to put in the first manually so the sorting algorithm have something to calculate on.
Yes, you can use any type for a vector, provided it's not abstract (in which case you can still use a pointer).
But you'll need to provide some more code (I'm assuming what you showed is pseudocode), and the compiler output, if you want more help [smile]
<edit>
There's no need to place the (0) after the instance of the vector. Vectors are empty upon creation by default.
I'm not sure what you mean by your sort algorithm, but the standard library does provide a sorting algorithm for the standard container types (like vector).
You can just do this (is the name of your vector 'sort'?)
std::sort( sort.begin(), sort.end() );
Or you can provide a comparison functor and pass it as a third argument:
struct Compare {
bool operator()( test Data1, test Data2 ) { /* do custom compare here */ }
};
std::sort( sort.begin(), sort.end(), Compare() );
</edit>
But you'll need to provide some more code (I'm assuming what you showed is pseudocode), and the compiler output, if you want more help [smile]
<edit>
There's no need to place the (0) after the instance of the vector. Vectors are empty upon creation by default.
I'm not sure what you mean by your sort algorithm, but the standard library does provide a sorting algorithm for the standard container types (like vector).
You can just do this (is the name of your vector 'sort'?)
std::sort( sort.begin(), sort.end() );
Or you can provide a comparison functor and pass it as a third argument:
struct Compare {
bool operator()( test Data1, test Data2 ) { /* do custom compare here */ }
};
std::sort( sort.begin(), sort.end(), Compare() );
</edit>
[Edit: nilkn beat me to it. :)]
Right, that's not exactly how vectors work. To declare one, you'd simply say:
vector< test > myvector;
Now the vector contains no elements. Now, say if you wanted to add one named 'element' to the back, you would say:
myvector.push_back( element );
If you want to insert something at the front:
myvector.insert( myvector.begin(), element );
Generally vectors are optimal in situations where you are only adding and removing elements from the end; since they are internally represented by a dynamic array, inserting things at the beginning or middle requires moving a lot of data around. Your sorting algorithm (sounds like an insertion sort, btw) would be more efficient with a list container.
There's a great book on all this called "The C++ Standard Library: A Tutorial and Reference" by Nicolai M. Josuttis. Highly recommended if you have the money to spare. :)
Right, that's not exactly how vectors work. To declare one, you'd simply say:
vector< test > myvector;
Now the vector contains no elements. Now, say if you wanted to add one named 'element' to the back, you would say:
myvector.push_back( element );
If you want to insert something at the front:
myvector.insert( myvector.begin(), element );
Generally vectors are optimal in situations where you are only adding and removing elements from the end; since they are internally represented by a dynamic array, inserting things at the beginning or middle requires moving a lot of data around. Your sorting algorithm (sounds like an insertion sort, btw) would be more efficient with a list container.
There's a great book on all this called "The C++ Standard Library: A Tutorial and Reference" by Nicolai M. Josuttis. Highly recommended if you have the money to spare. :)
Author
Yes... that i pseudo. But thats mainly because I dont know how to work with structures inside vectors. :S Once I figure that out I will be able to construct the sorting loop.
[edit] seems like I got two answers while I was typing. :P I'll look up that sort routine and see what I can dig up.
[edit] seems like I got two answers while I was typing. :P I'll look up that sort routine and see what I can dig up.
If there must always be an ordering of elements (in other words always sorted container) then perhaps consider using a different container like std::set instead.
Quote:Original post by snk_kid
If there must always be an ordering of elements (in other words always sorted container) then perhaps consider using a different container like std::set instead.
Although it's worth noting that set (and map) have completely different performance characteristics from vector. :)
To access a member of a struct within a vector, you can just use array notation if you know the index, for example:
myvector[2].id = 42;
Note that the above ONLY works for vectors (and arrays of course).
If you only have an iterator, you can use:
(*myiterator).id = 42;
or
myiterator->id = 42;
...and that works for *all* Standard Library containers.
[Edit: Also, you can see how an iterator is syntactically like a pointer in both cases.]
Quote:Original post by lancektQuote:Original post by snk_kid
If there must always be an ordering of elements (in other words always sorted container) then perhaps consider using a different container like std::set instead.
Although it's worth noting that set (and map) have completely different performance characteristics from vector. :)
To access a member of a struct within a vector, you can just use array notation if you know the index, for example:
myvector[2].id = 42;
Note that the above ONLY works for vectors (and arrays of course).
If you only have an iterator, you can use:
(*myiterator).id = 42;
or
myiterator->id = 42;
...and that works for *all* Standard Library containers.
[Edit: Also, you can see how an iterator is syntactically like a pointer in both cases.]
[headshake] You don't think I am aware of that? random accessibility and/or contiguousness of elements may have no significance what so ever, it depends on the context and he did not mention enough details to know for sure. That is why I said perhaps, "choose the wright tool for the job" as they say.
[Edited by - snk_kid on May 28, 2005 1:58:33 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
