vector and sort problem

[Johan]

Hi,

Why does my vector not sort. What I understand is you have to overload
the < operator, but that does not work.

see code below

Thanks

Johan

class Demo
{
public :
Demo(string filename) : filename(filename)
{
}

bool operator<(const Demo& d)
{
return filename < d.filename;
}

string getFilename()
{
return filename;
}

private :
string filename;
};

int main(int argc, char** argv[])
{
vector<Demo*> v;

v.push_back(new Demo("z"));
v.push_back(new Demo("c"));
v.push_back(new Demo("a"));
v.push_back(new Demo("v"));
v.push_back(new Demo("t"));
v.push_back(new Demo("g"));

sort(v.begin(), v.end());
typedef vector<Demo*>::const_iterator iter;
for(iter i = v.begin(); i != v.end(); i++)
{
cout << (*i)->getFilename() << endl;
}

return 0;
}

output

z
c
a
v
g
t

Johan

 

[Rolf Magnus]

Hi,

Why does my vector not sort. What I understand is you have to overload
the < operator, but that does not work.

Overloading < is one way to do it.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::cout;
using std::endl;
using std::sort;
using std::vector;

class Demo
{
public :
Demo(string filename) : filename(filename)
{
}

bool operator<(const Demo& d)

bool operator<(const Demo& d) const

{
return filename < d.filename;
}

string getFilename()

string getFilename() const

{
return filename;
}

private :
string filename;
};

int main(int argc, char** argv[])
{
vector<Demo*> v;

Your element type is not Demo, but pointer to Demo. So the vector will be
sorted by pointer values.

v.push_back(new Demo("z"));
v.push_back(new Demo("c"));
v.push_back(new Demo("a"));
v.push_back(new Demo("v"));
v.push_back(new Demo("t"));
v.push_back(new Demo("g"));

sort(v.begin(), v.end());

If you want to store pointers, you have to provide as a third parameter to
sort a comparison function/functor, since you cannot overload operator< for
pointers. Add before main:

struct cmp
{
bool operator()(const Demo* lhs, const Demo* rhs) const
{
return *lhs < *rhs;
}
};

And then replace your sort with:

sort(v.begin(), v.end(), cmp());

typedef vector<Demo*>::const_iterator iter;
for(iter i = v.begin(); i != v.end(); i++)
{
cout << (*i)->getFilename() << endl;
}

return 0;
}

You don't delete the elements. In this case, it won't make much of a
difference, but it's good to get used to cleaning up after yourself.

 

[Ivan Vecerina]

Why does my vector not sort. What I understand is you have to overload
the < operator, but that does not work.

As a complement to Rolf's accurate comment, I would just
like to point out that using a vector of values (instead
of pointers) might be a better solution:

int main(int argc, char** argv[])
{
vector<Demo> v;

v.push_back(Demo("z"));
v.push_back(Demo("c"));
v.push_back(Demo("a"));
v.push_back(Demo("v"));
v.push_back(Demo("t"));
v.push_back(Demo("g"));

sort(v.begin(), v.end());
typedef vector<Demo>::const_iterator iter;
for(iter i = v.begin(); i != v.end(); i++)
{
cout << i->getFilename() << endl;
}
return 0;
}

Fewer memory allocations, and no memory leaks.


Cheers,
Ivan

 

[Jerry Coffin]

Hi,

Why does my vector not sort. What I understand is you have to overload
the < operator, but that does not work.

It works just fine -- but you've defined your collection in a way that
prevents it from ever being used.

[ ... ]

bool operator<(const Demo& d)
{
return filename < d.filename;
}

This is fine -- it compares one Demo to another just like it should.

string getFilename()
{
return filename;
}

It's only minimally related to the problem at hand, but this is not
nearly so fine -- it exposes the class' internals to the outside world.

[ ... ]

vector<Demo*> v;

Here's your real problem: up above, you've defined how to compare one
Demo to another, but here you're not storing Demo's -- you're storing
pointers to Demo's instead.

There are two ways to deal with this. If it's really crucial that you
store pointers (e.g. you really have a polymorphic hierarchy with Demo
as the base class) then you need to define a function/functor to do the
comparison:

bool cmp(Demo const &a, Demo const &b) {
return a.getFileName() < b.GetFileName();
}

and then when you sort the vector, tell sort to use that to do the
comparisons:

std::sort(v.begin(), v.end(), cmp);

It's usually better, however, to simply store objects instead of
pointers, which will allow your operator< to do the job:

vector<Demo> v;

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

As it stands right now, std::sort is comparing the _pointers_ rather
than the Demo's themselves -- in practical terms, this means it's
sorting them into the order in which they're stored in memory, though
from a technical viewpoint, it's simply undefined behavior.

sort(v.begin(), v.end());
typedef vector<Demo*>::const_iterator iter;
for(iter i = v.begin(); i != v.end(); i++)
{
cout << (*i)->getFilename() << endl;
}

Here's why having a (public) getFilename is really a bad idea: now the
rest of your code knows about, and makes use of the internals of a Demo
instead of treating it as an object in its own right. I'd prefer to do
something like:

class Demo {
// your "stuff" but with getFilename private or removed.
public:
friend ostream &operator<<(ostream &os, Demo const &d);
};

ostream &operator<<(ostream &os, Demo const &d) {
return os << d.getFilename();
}

and then when you want to print out your sorted vector of demos, you
can write code that actually writes out the Demos:

for(iter i = v.begin(); i != v.end(); i++)
{
cout << *i << endl;
}

or better yet, use an algorithm and write even less yourself:

std::copy(v.begin(), v.end(), ostream_iterator<Demo>(cout, "\n"));

 

[Dave Moore]

[snip]

It's only minimally related to the problem at hand, but this is not
nearly so fine -- it exposes the class' internals to the outside world.

Hmm .. I am not sure I agree. All the getFilename function does is
provide a way to obtain a string (by value), from the object. This does not
say anything about the internals of the Demo class, and it seems quite
reasonable, given that filenames are commonly represented as strings. For
all we know, the string returned by getFilename could be generated at random
(although that would not be very useful).
If you are actually talking about the "in place" definition of the
function, then ok, point taken. But the OP may well have presented it that
way for the sake of simplicity. Certainly if the class is handled in the
canonical way (declarations in .hpp, definitions in .cpp), then there is no
reason that the internal representation of the class can't be changed, given
the definition of getFilename above. As long as getFilename returns a
string, nothing will need to be changed in applications using Demo objects.

[snip]

Here's why having a (public) getFilename is really a bad idea: now the
rest of your code knows about, and makes use of the internals of a Demo
instead of treating it as an object in its own right. I'd prefer to do
something like:

Again, I don't agree that getFilename exposes the representation of the
class(see above). However, I *do* agree that your suggested method below
for handling this particular example is generally a better approach.

class Demo {
// your "stuff" but with getFilename private or removed.
public:
friend ostream &operator<<(ostream &os, Demo const &d);
};

ostream &operator<<(ostream &os, Demo const &d) {
return os << d.getFilename();
}

and then when you want to print out your sorted vector of demos, you
can write code that actually writes out the Demos:

for(iter i = v.begin(); i != v.end(); i++)
{
cout << *i << endl;
}

or better yet, use an algorithm and write even less yourself:

std::copy(v.begin(), v.end(), ostream_iterator<Demo>(cout, "\n"));

Dave Moore