Sign in to follow this  

searching and sorting an array or std::vector of objects of a polymorphic class [C++]

This topic is 3727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

A generalization of my problem: suppose I have a class Base(an abstract class) and some others Derived1, Derived2 and Derived3(not abstract) which are derived from Base. I also have in another class a std::vector<Base*> where I store Derived1, Derived2 and Derived3 objects, in any order like this:
std::vector<Base*> derivedVector;
.
.
.
derivedVector.push_back(new Derived1(someParameter);
derivedVector.push_back(new Derived2(someParameter);
derivedVector.push_back(new Derived3(someParameter);
//note: I delete all these dinamically allocated Deriveds in the destructor of this class
Just that. How would I search or sort this vector using a specific comparison function?? And if instead of a std::vector it was an array?! The basic qsort() and bsearch() doesn't work because the array pointer will be incremented wrongly. Thanks :)

Share this post


Link to post
Share on other sites
[quote]Original post by xissburg
A generalization of my problem: suppose I have a class Base(an abstract class) and some others Derived1, Derived2 and Derived3(not abstract) which are derived from Base. I also have in another class a std::vector<Base*> where I store Derived1, Derived2 and Derived3 objects[.quote]
Stop. You don't have a container of objects. You have a container of pointers to objects. It's a fundamental and extrememly important difference, and has been the cause of much misunderstanding. Make sure you understande the difference.
Quote:
How would I search or sort this vector using a specific comparison function?? And if instead of a std::vector it was an array?! The basic qsort() and bsearch() doesn't work because the array pointer will be incremented wrongly.


The C standard library algorithms are inadequate for most C++ applications.

Use the C++ standard library algorithms. They're faster, easier, and better able to cope with the twenty-first century.

I would recommend using std::sort and supplying your own comparison predicate function. The simplest way to do that would be to have a member function of you Base class that provides the comparison and bind that using one of the std::mem_fun variants, but I could understand if you find those confusing and hard to read. In that case, create a namespace-level function that take two const Base* objects as parameters and returns bool true.

bool BaseComparator(const Base* lhs, const Base* rhs)
{
return lhs->value() < rhs.value();
}

// ...

std::sort(derivedVector.begin(), derivedVector.end(), BaseComparator);

And hey presto! this exact same code will work for C-style arrays.

--smw

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma

std::sort(derivedVector.begin(), derivedVector.end(), BaseComparator);

And hey presto! this exact same code will work for C-style arrays.

--smw


To be explicit: with arrays, specify the bounds for the sort like:


Base* things[SIZE];
// ...
std::sort(things, things + SIZE, BaseComparator);

Share this post


Link to post
Share on other sites
thanks for all the replies. I got it working. But and about std::binary_search()? it returns a bool =/ how to get a pointer to the object that was found?!? Have no idea . ..

____________________________________ ________ _____ ____ __ _
And another thing :) A very stupid one. How do I correctly mount a string and return it from a function?! Not sure if this is correct or good:


string GetInfo()
{
char buf[512];
//think of GetWeight() as a pure virtual function which is defined at some derived class
//it does some specific computation for that kind of object and returns a float
//and GetNotes() is also a pure virtual function which returns a class specific string with some info
sprintf_s(buf, "Name: %s\nWeight: %.2f\nNotes: %s\n", name, GetWeight(), GetNotes().c_str());//I was getting some runtime errors with this

return string(buf); // !!! what about this ^^?!
}

//GetNotes() is something like this
string GetNotes()
{
return string("Some Thing");//hm?! =/
}


I'm asking this because here I'm in the need to return a local variable, and it doesn't looks good and also because there are many programming freaks here who can help me :)


Thanks :)

Share this post


Link to post
Share on other sites
Quote:
Original post by xissburg
thanks for all the replies. I got it working. But and about std::binary_search()? it returns a bool =/ how to get a pointer to the object that was found?!? Have no idea

You want std::upper_bound and/or std::lower_bound.

Share this post


Link to post
Share on other sites
Quote:
Original post by xissburg
thanks for all the replies. I got it working. But and about std::binary_search()? it returns a bool =/ how to get a pointer to the object that was found?!? Have no idea . ..
Take a look at std::lower_bound() and std::upper_bound(). [Edit: as noted above.]
Quote:
And another thing :) A very stupid one. How do I correctly mount a string and return it from a function?! Not sure if this is correct or good:


string GetInfo()
{
char buf[512];
//think of GetWeight() as a pure virtual function which is defined at some derived class
//it does some specific computation for that kind of object and returns a float
//and GetNotes() is also a pure virtual function which returns a class specific string with some info
sprintf_s(buf, "Name: %s\nWeight: %.2f\nNotes: %s\n", name, GetWeight(), GetNotes().c_str());

return string(buf); // !!! what about this ^^?!
}

//GetNotes() is something like this
string GetNotes()
{
return string("Some Thing");//hm?! =/
}


I'm asking this because here I'm in the need to return a local variable, and it doesn't looks good and also because there are many programming freaks here who can help me :)


Thanks :)
You're not returning a local variable; you're returning a string by value, which is perfectly acceptable (it's not terribly efficient, but whether that matters depends on the context).

I would however recommend against mixing of C- and C++-style string manipulation as in your first example. I didn't bother looking up sprintf_s() to see if you're using it correctly, but in any case, take a look at std::stringstream; it will allow you to construct the same string using C++-style 'stream insertion' syntax. (Other options you might look into are boost::lexical_cast and boost::format.)

Share this post


Link to post
Share on other sites
Thanks again :) you're awesome.

I think I'm on the need of some general std:: tutorial/reference thing(and, boost:: . . ?! what is boost::?! maybe I need it too). Any suggestions??

Thanks again.

Share this post


Link to post
Share on other sites
Quote:
Original post by xissburg
I think I'm on the need of some general std:: tutorial/reference thing


The C++ Standard Library: A Tutorial and Reference

Quote:
Original post by xissburg
(and, boost:: . . ?! what is boost::?! maybe I need it too).


The Boost C++ Libraries are a collection of peer-reviewed, open source libraries that extend the functionality of C++. Most of the libraries are licensed under the Boost Software License, designed to allow Boost to be used with both open and closed source projects. - Wikipedia

http://www.boost.org/

Share this post


Link to post
Share on other sites

This topic is 3727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this