about STL sort

[Magcialking]

I wanna sort a pointer vector with the algorithm "sort" in STL like
this:

"
int compare(vector< string*>::itera tor a,vector<string *>::iterator b){
return (**a)<(**b);
}

sort(iter,iter_ end,compare);
"


but this dosen't work,and I really don't know why.
Could anyone show me how to use this correctly?

[red floyd]

Re: about STL sort

Magcialking wrote:

I wanna sort a pointer vector with the algorithm "sort" in STL like
this:
>
"
int compare(vector< string*>::itera tor a,vector<string *>::iterator b){
return (**a)<(**b);
}

should be:

int compare(const string *a, const string *b)
{
return *a < *b;
}

sort(iter,iter_ end,compare);
"
>
>
but this dosen't work,and I really don't know why.
Could anyone show me how to use this correctly?
>

[Nate Barney]

Re: about STL sort

Magcialking wrote:

I wanna sort a pointer vector with the algorithm "sort" in STL like
this:
>
"
int compare(vector< string*>::itera tor a,vector<string *>::iterator b){
return (**a)<(**b);
}
>
sort(iter,iter_ end,compare);
"

You don't specify the type of iter and iter_end, but I am going to
assume that they're of type vector<string*> ::iterator.

>
but this dosen't work,and I really don't know why.
Could anyone show me how to use this correctly?

The problem is that your comparison function takes iterators as
parameters, when it should take values. Additionally, it should return
a bool. For example:

bool compare(string *a,string *b) {
return (*a) < (*b);
}

Another thing you might consider is writing a generic dereferencing
binary predicate adapter:

#include <functional>

template <typename It,typename Pred>
class deref_pred : public std::binary_fun ction<It,It,boo l>
{
public:

deref_pred() {}
deref_pred(cons t Pred &pred) : pred(pred) {}

bool operator()(cons t It &a,const It &b) const
{ return pred(*a,*b); }

private:

Pred pred;
};

Then you would call sort like:

std::sort(iter, iter_end,
deref_pred<std: :string*,std::l ess<std::string ());

This is a bit more work on the front end, but it's much easier to reuse.

Hope this helps,
Nate

[Magcialking]

Re: about STL sort

Another thing you might consider is writing a generic dereferencing

binary predicate adapter:
>
#include <functional>
>
template <typename It,typename Pred>
class deref_pred : public std::binary_fun ction<It,It,boo l>
{
public:
>
deref_pred() {}
deref_pred(cons t Pred &pred) : pred(pred) {}
>
bool operator()(cons t It &a,const It &b) const
{ return pred(*a,*b); }
>
private:
>
Pred pred;
};
>
Then you would call sort like:
>
std::sort(iter, iter_end,
deref_pred<std: :string*,std::l ess<std::string ());

it seems that deref_pred is just a wrapping paper,the real compare
function need to be pass to it when used?so, what's deref_pred doing
here?

and I am also confuse about the inheritance here:public
std::binary_fun ction<It,It,boo l>,
what's it for?

[Nate Barney]

Re: about STL sort

Magcialking wrote:

>#include <functional>
>>
>template <typename It,typename Pred>
>class deref_pred : public std::binary_fun ction<It,It,boo l>
>{
>public:
>>
> deref_pred() {}
> deref_pred(cons t Pred &pred) : pred(pred) {}
>>
> bool operator()(cons t It &a,const It &b) const
> { return pred(*a,*b); }
>>
>private:
>>
> Pred pred;
>};
>>
>Then you would call sort like:
>>
>std::sort(iter ,iter_end,
> deref_pred<std: :string*,std::l ess<std::string ());

>
it seems that deref_pred is just a wrapping paper,the real compare
function need to be pass to it when used?so, what's deref_pred doing
here?

It dereferences the pointers/iterators passed as arguments, which allows
it to work on containers of pointers/iterators, like the
std::vector<std ::string*contai ner you have. The reason for the Pred
parameter is that you can change the predicate to, say, std::greater, if
you wish to reverse the sort.

and I am also confuse about the inheritance here:public
std::binary_fun ction<It,It,boo l>,
what's it for?

This base class does nothing other than define a few typedefs that allow
it to be used more easily with other parts of the STL.

See http://www.sgi.com/tech/stl/functors.html, specifically the third
paragraph of the Description section.

Nate

[Magcialking]

Re: about STL sort


Nate Barney 写道：

Magcialking wrote:

#include <functional>
>
template <typename It,typename Pred>
class deref_pred : public std::binary_fun ction<It,It,boo l>
{
public:
>
deref_pred() {}
deref_pred(cons t Pred &pred) : pred(pred) {}
>
bool operator()(cons t It &a,const It &b) const
{ return pred(*a,*b); }
>
private:
>
Pred pred;
};
>
Then you would call sort like:
>
std::sort(iter, iter_end,
deref_pred<std: :string*,std::l ess<std::string ());

it seems that deref_pred is just a wrapping paper,the real compare
function need to be pass to it when used?so, what's deref_pred doing
here?

>
It dereferences the pointers/iterators passed as arguments, which allows
it to work on containers of pointers/iterators, like the
std::vector<std ::string*contai ner you have. The reason for the Pred
parameter is that you can change the predicate to, say, std::greater, if
you wish to reverse the sort.
>

and I am also confuse about the inheritance here:public
std::binary_fun ction<It,It,boo l>,
what's it for?

>
This base class does nothing other than define a few typedefs that allow
it to be used more easily with other parts of the STL.
>
See http://www.sgi.com/tech/stl/functors.html, specifically the third
paragraph of the Description section.

Nate

OK, I got it. Thanks a lot!

[Gernot Frisch]

Re: about STL sort


"Magcialkin g" <magic_king@163 .comschrieb im Newsbeitrag
news:1158028118 .434362.117250@ m73g2000cwd.goo glegroups.com.. .

>I wanna sort a pointer vector with the algorithm "sort" in STL like
this:
>
"
int compare(vector< string*>::itera tor a,vector<string *>::iterator
b){
return (**a)<(**b);
}
>
sort(iter,iter_ end,compare);

struct MySort
{
bool operator() (const string*& p1, const string*& p2)
{
return *p1 < *p2;
}
};

int main()
{
std::vector<std ::string*vec;
// fill vector
std::sort(vec.b egin(), vec.end(), MySort() );
}

Question: Why are you holding a string* instead of a string in your
vector?

[Magcialking]

Re: about STL sort


Gernot Frisch 写道：

"Magcialkin g" <magic_king@163 .comschrieb im Newsbeitrag
news:1158028118 .434362.117250@ m73g2000cwd.goo glegroups.com.. .

I wanna sort a pointer vector with the algorithm "sort" in STL like
this:

"
int compare(vector< string*>::itera tor a,vector<string *>::iterator
b){
return (**a)<(**b);
}

sort(iter,iter_ end,compare);

>
>
struct MySort
{
bool operator() (const string*& p1, const string*& p2)
{
return *p1 < *p2;
}
};
>
int main()
{
std::vector<std ::string*vec;
// fill vector
std::sort(vec.b egin(), vec.end(), MySort() );
}
>
Question: Why are you holding a string* instead of a string in your
vector?

Cause I think this will save time than to push string itself into a
vector.

[Jerry Coffin]

Re: about STL sort

In article <1158112240.076 791.99940@i3g20 00cwc.googlegro ups.com>,
magic_king@163. com says...

[ ... ]

Question: Why are you holding a string* instead of a string in your
vector?

>
Cause I think this will save time than to push string itself into a
vector.

A string object isn't usually a _whole_ lot more than a wrapper around a
pointer and a couple of size_t's. Depending on implementation, it may
also include a _small_ array of elements, but it's still usually pretty
fast to copy around and such.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Gernot Frisch]

Re: about STL sort

Question: Why are you holding a string* instead of a string in your
vector?

Cause I think this will save time than to push string itself into a
vector.


And you know you have to delete the strings themselfes some day?? The
string you forgot, because you put it's pointer in the vector?
It's OK if you do, but are you aware if it?

[persenaama]

Re: about STL sort

A string object isn't usually a _whole_ lot more than a wrapper around a

pointer and a couple of size_t's. Depending on implementation, it may
also include a _small_ array of elements, but it's still usually pretty
fast to copy around and such.

Doesn't mean that it isn't (in the context) expensive to construct, I
believe a copy means the contents are also copied?

[Jerry Coffin]

Re: about STL sort

In article <1158166252.422 781.75440@e3g20 00cwe.googlegro ups.com>,
jukka@liimatta. org says...

A string object isn't usually a _whole_ lot more than a wrapper around a
pointer and a couple of size_t's. Depending on implementation, it may
also include a _small_ array of elements, but it's still usually pretty
fast to copy around and such.

>
Doesn't mean that it isn't (in the context) expensive to construct, I
believe a copy means the contents are also copied?

You clearly have one copy that takes place when you put the string into
the vector. From there it depends: when the vector expands, it can copy
construct all the strings into the newly expanded area, then destroy the
old ones -- which (as you suggest) would result in a (relatively slow
deep copy of each of the existing strings -- not to mention temporarily
using a lot of extra memory.

For nearly anything that uses remote ownership (i.e. anything with a
difference between shallow and deep copy), however, that's not usually
the best way. Instead, you can create your new, expanded memory full of
empty items (strings in this case), and then use swap to put the real
ones into the new memory and the empty ones into the old memory, without
copying the actual data.

Of course, on a platform where it get away with it (i.e. most) the
library can just do a shallow copy from the old space to the new, and be
done with it. It's not portable, but the library doesn't need to be
portable internally -- it just has to provide a portable interface. This
is the sort of thing for which template specialization was invented...

--
Later,
Jerry.

The universe is a figment of its own imagination.