C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

question on sorting a vector
Goto page 1, 2  Next
 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated)
View previous topic :: View next topic  
Author Message
tcl
Guest
PostPosted: Wed Nov 09, 2005 6:32 pm    Post subject: question on sorting a vector Reply with quote


I want to be able to sort objects in a vector based on
how long the objects have been in idle.
Currently my code looks like the followings:

-------------------------------------------
class X
{
public:
....
....
long getIdleTime(){ return time(NULL) - lastTimeStamp; }
private:
time_t lastTimeStamp;
}


In the class that uses class X, I have something like:

inline
bool sortByIdleTime( X* a, X* b )
{
return a->getIdleTime() > b->getIdleTime();
};


typedef std::vector<X*> XType;
XType XItems;
....
....
// sort the vector based on idle time
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);
----------------------------------------------

However, I want the idle time to be computed based on
the same reference time, instead of the time at which
the function is called (because there may be delays
in between calls to the getIdelTime() on diffrent X
instances in the vector).

So I would modify the class X to:

class X
{
public:
....
....
lone getIdleTime(time_t refTime) // *** add refTime input
{ return refTime - lastTimeStamp; }
private:
time_t lastTimeStamp;
}

My sort function would look like:

inline // *** add refTime input
bool sortByIdleTime( X* a, X* b, time_t refTime )
{
return a->getIdleTime(refTime) < b->getIdleTime(refTime);
};


My problem is, how to do the sort?? or how to pass the refTime
to the sort?

time_t refTime = time(NULL);
// how to pass refTime to sortByIdelTime below ???
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Falk Tannhäuser
Guest
PostPosted: Thu Nov 10, 2005 11:55 am    Post subject: Re: question on sorting a vector Reply with quote


tcl wrote:
Quote:
I want to be able to sort objects in a vector based on
how long the objects have been in idle.
Currently my code looks like the followings:

-------------------------------------------
class X
{
public:
...
...
long getIdleTime(){ return time(NULL) - lastTimeStamp; }

This member function should most probably be qualified 'const'.

Quote:
private:
time_t lastTimeStamp;
}


In the class that uses class X, I have something like:

inline
bool sortByIdleTime( X* a, X* b )

Same here:
inline bool sortByIdleTime(X const* a, X const* b)
Quote:
{
return a->getIdleTime() > b->getIdleTime();
};


typedef std::vector<X*> XType;
XType XItems;
...
...
// sort the vector based on idle time
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);
----------------------------------------------

However, I want the idle time to be computed based on
the same reference time, instead of the time at which
the function is called (because there may be delays
in between calls to the getIdelTime() on diffrent X
instances in the vector).
[...]
My problem is, how to do the sort?? or how to pass the refTime
to the sort?

Rather than passing just a function pointer, you need to pass
a function object, which can contain all the state you want:

class CmpIdleTimes
{
std::time_t refTime;
public:
CmpIdleTimes(std::time_t tm) : refTime(tm) {}

bool operator()(X const* a, X const* b) const
{ return a->getIdleTime(refTime) < b->getIdleTime(refTime); }
};

....

std::sort(XItems.begin(), XItems.end(), CmpIdleTimes(std::time(NULL)));


Falk

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Owen
Guest
PostPosted: Thu Nov 10, 2005 1:24 pm    Post subject: Re: question on sorting a vector Reply with quote


<...>
Quote:
My problem is, how to do the sort?? or how to pass the refTime
to the sort?

time_t refTime = time(NULL);
// how to pass refTime to sortByIdelTime below ???
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);


I think boost::bind can do what you need. Just like that:

std::sort( XItems.begin(), XItems.end(),
boost::bind(sortByIdleTime, _1, _2, refTime));

For the detail, go http://www.boost.org/libs/bind/bind.html


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
bachlipp@gmail.com
Guest
PostPosted: Thu Nov 10, 2005 1:29 pm    Post subject: Re: question on sorting a vector Reply with quote

tcl wrote:
Quote:
I want to be able to sort objects in a vector based on
how long the objects have been in idle.
Currently my code looks like the followings:

-------------------------------------------
class X
{
public:
...
...
long getIdleTime(){ return time(NULL) - lastTimeStamp; }
private:
time_t lastTimeStamp;
}


In the class that uses class X, I have something like:

inline
bool sortByIdleTime( X* a, X* b )
{
return a->getIdleTime() > b->getIdleTime();
};


typedef std::vector<X*> XType;
XType XItems;
...
...
// sort the vector based on idle time
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);
----------------------------------------------

However, I want the idle time to be computed based on
the same reference time, instead of the time at which
the function is called (because there may be delays
in between calls to the getIdelTime() on diffrent X
instances in the vector).

Oh - stupid me. My last response was too much of a good thing. I
interpret your wish as follows:

You want to compare
idleTimeOfA > idleTimeOfB, i.e.
now - lastUsageOfA > now - lastUsageOfB,
which mathematically is the same as
lastUsageOfB > lastUsageOfA.

This means, that you don't need the current time in your calculation at
all.

My thoughts on "difftime()" still apply.

Cheers,
Philipp.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Edwin Castro
Guest
PostPosted: Thu Nov 10, 2005 1:32 pm    Post subject: Re: question on sorting a vector Reply with quote
tcl wrote:
Quote:
My sort function would look like:

inline // *** add refTime input
bool sortByIdleTime( X* a, X* b, time_t refTime )
{
return a->getIdleTime(refTime) < b->getIdleTime(refTime);
};


My problem is, how to do the sort?? or how to pass the refTime
to the sort?

time_t refTime = time(NULL);
// how to pass refTime to sortByIdelTime below ???
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);


I would recommend you use a functor. You should create class with
operator() defined. You can create an instance of that class, passing it
the reference time in the constructor, and passing the instance to
std::sort.

class IdleTimeSort {
public:
IdleTimeSort(time_t refTime) : refTime_(refTime) { }
bool operator()(const X& a, const X& b)
{
return a.getIdleTime(refTime_) < b.getIdleTime(refTime_);
}
private:
time_t refTime_;
}

IdleTimeSort sortByIdleTime(time(0));
std::sort(XItems.begin(), XItems.end(), sortByIdleTime);

--
Edwin

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
albrecht.fritzsche
Guest
PostPosted: Thu Nov 10, 2005 1:33 pm    Post subject: Re: question on sorting a vector Reply with quote
tcl wrote:
Quote:
My sort function would look like:

inline // *** add refTime input
bool sortByIdleTime( X* a, X* b, time_t refTime )
{
return a->getIdleTime(refTime) < b->getIdleTime(refTime);
};

My problem is, how to do the sort?? or how to pass the refTime
to the sort?

Use a /functor/ instead of your plain function - even in your first
version (ie without passing refTime) this might improve the run
time since functors can be inlined better then plain function
pointers.

struct SortByIdleTime {
SortByIdleTime(time_t refTime) : refTime_(refTime) {}
bool operator()(const X* a, const X* b) {
return a->getIdleTime(refTime) < b->getIdleTime(refTime);
}
time_t refTime_;
};
...
time_t refTime = time(NULL);
std::sort(XItems.begin(), XItems.end(), SortByIdleTime(refTime));

Ali

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Daniel Krügler
Guest
PostPosted: Thu Nov 10, 2005 1:36 pm    Post subject: Re: question on sorting a vector Reply with quote
tcl wrote:
Quote:
I want to be able to sort objects in a vector based on
how long the objects have been in idle.
Currently my code looks like the followings:

-------------------------------------------
class X
{
public:
...
...
long getIdleTime(){ return time(NULL) - lastTimeStamp; }
private:
time_t lastTimeStamp;
}

Two proposals:

1) getIdleTime() should be const.

2) Directly computing the time difference of time_t is not guaranteed
to give any result, which makes sense for you. Therefore you should use
difftime, see C99 standard 7.23.1:

"[..] and time_t which are arithmetic types capable of representing times;"
"[..] The range and precision of times representable in clock_t and
time_t are implementation-defined."

The documentation of time says:

"The time function determines the current calendar time. The encoding of
the value is unspecified."


Quote:
In the class that uses class X, I have something like:

inline
bool sortByIdleTime( X* a, X* b )
{
return a->getIdleTime() > b->getIdleTime();
};

I strongly suggest:

inline
bool sortByIdleTime(const X* a, const X* b )
{
return a->getIdleTime() > b->getIdleTime();
};


Quote:
typedef std::vector<X*> XType;
XType XItems;
...
...
// sort the vector based on idle time
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);
----------------------------------------------

However, I want the idle time to be computed based on
the same reference time, instead of the time at which
the function is called (because there may be delays
in between calls to the getIdelTime() on diffrent X
instances in the vector).

So I would modify the class X to:

class X
{
public:
...
...
lone getIdleTime(time_t refTime) // *** add refTime input

long getIdleTime(time_t refTime) const

Quote:
{ return refTime - lastTimeStamp; }
private:
time_t lastTimeStamp;
}

My sort function would look like:

inline // *** add refTime input
bool sortByIdleTime( X* a, X* b, time_t refTime )
{
return a->getIdleTime(refTime) < b->getIdleTime(refTime);
};


bool sortByIdleTime( const X* a, const X* b, time_t refTime )

Quote:

My problem is, how to do the sort?? or how to pass the refTime
to the sort?

time_t refTime = time(NULL);
// how to pass refTime to sortByIdelTime below ???
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);

One approach is to provide your functor like this:

struct LessItems {
explicit LessItems(time_t refTime) : refTime_(refTime) {}

bool operator()(const X* a, const X* b) const
{
return a->getIdleTime(refTime_) < b->getIdleTime(refTime_);
}

private:
time_t refTime_;
};

This does not reuse existing components, but its simple to understand.

time_t refTime = time(NULL);
std::sort( XItems.begin(), XItems.end(), LessItems(refTime));

If you use boost::bind, you don't need this helper class and you can
simply write:

time_t refTime = time(NULL);
std::sort( XItems.begin(), XItems.end(), boost::bind(sortByIdleTime, _1,
_2, refTime));

Greetings from Bremen,

Daniel Krügler

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
bachlipp@gmail.com
Guest
PostPosted: Thu Nov 10, 2005 1:36 pm    Post subject: Re: question on sorting a vector Reply with quote
tcl schrieb:

Quote:
I want to be able to sort objects in a vector based on
how long the objects have been in idle.
Currently my code looks like the followings:

-------------------------------------------
class X
{
public:
...
...
long getIdleTime(){ return time(NULL) - lastTimeStamp; }
private:
time_t lastTimeStamp;
}


In the class that uses class X, I have something like:

inline
bool sortByIdleTime( X* a, X* b )
{
return a->getIdleTime() > b->getIdleTime();
};


typedef std::vector<X*> XType;
XType XItems;
...
...
// sort the vector based on idle time
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);
----------------------------------------------

However, I want the idle time to be computed based on
the same reference time, instead of the time at which
the function is called (because there may be delays
in between calls to the getIdelTime() on diffrent X
instances in the vector).

You could make your sortByIdleTime() function a functor, i.e. a class
with operator()(X* a, X* b). Then your fixed time could be implemented
as a (potentially const) member, which at least will be initialized
upon construction of the functor. If you add a member function which
resets the time member to the current time or any time supplied as an
argument, you could reuse the functor, but this might be too much of a
good thing - I'd go for the simple solution to make the time member
"const" and only initialize it within the constructor...

By the way: I'm not that convinced how portable your sort function is -
instead of the implicit difference you use (a->getIdleTime() -
b->getIdleTime() > 0) I'd use the "difftime()" standard function.

Cheers,
Philipp.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Greg Herlihy
Guest
PostPosted: Sun Nov 13, 2005 3:35 pm    Post subject: Re: question on sorting a vector Reply with quote
tcl wrote:
Quote:
I want to be able to sort objects in a vector based on
how long the objects have been in idle.
Currently my code looks like the followings:

-------------------------------------------
class X
{
public:
...
...
long getIdleTime(){ return time(NULL) - lastTimeStamp; }
private:
time_t lastTimeStamp;
}


In the class that uses class X, I have something like:

inline
bool sortByIdleTime( X* a, X* b )
{
return a->getIdleTime() > b->getIdleTime();
};


typedef std::vector<X*> XType;
XType XItems;
...
...
// sort the vector based on idle time
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);
----------------------------------------------

However, I want the idle time to be computed based on
the same reference time, instead of the time at which
the function is called (because there may be delays
in between calls to the getIdelTime() on diffrent X
instances in the vector).

So I would modify the class X to:

class X
{
public:
...
...
lone getIdleTime(time_t refTime) // *** add refTime input
{ return refTime - lastTimeStamp; }
private:
time_t lastTimeStamp;
}

My sort function would look like:

inline // *** add refTime input
bool sortByIdleTime( X* a, X* b, time_t refTime )
{
return a->getIdleTime(refTime) < b->getIdleTime(refTime);
};


My problem is, how to do the sort?? or how to pass the refTime
to the sort?

time_t refTime = time(NULL);
// how to pass refTime to sortByIdelTime below ???
std::sort( XItems.begin(), XItems.end(), sortByIdleTime);

I think you probably should review whether the sortByIdelTime
comparison routine really needs a reference time. I don't see how
uniformly adding a constant value to each idle time being compared
could having any affect at all on the the final sorted order.

Even though the idle times being compared are not constant, they are
all aging at the same rate. More importantly, the result of any
comparison between any two idle times will always return a consistent
and correct result. And since the result of each comparison used to
sort the items is correct, then the sorted order it produces must also
be correct even if the values used throughout the sort have not been
constant. The result may seem paradoxical, but to sort correctly
requires only consistent comparisons - and not constant values - for
the items being sorted.

Alternately, a more simple strategy would be to store the "time of last
activity". Those times would be constant and easily sorted. Those items
with the lowest-value time stamps would have been idle the longest.

I would also recommend ensuring that no item is changed in such a way
that it changes its order relative to any other item while the sort is
being conducted. Inconsistent comparisons during a sort will lead to
the wrong sort order and may even cause undefined behavior on the part
of the sorting implementation.

Greg


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Allan W
Guest
PostPosted: Tue Nov 15, 2005 7:58 am    Post subject: Re: question on sorting a vector Reply with quote
[email]allan_w (AT) my-dejanews (DOT) com[/email]

Quote:
tcl wrote:
I want to be able to sort objects in a vector based on
how long the objects have been in idle.

Greg Herlihy wrote:
Quote:
I think you probably should review whether the sortByIdelTime
comparison routine really needs a reference time. I don't see how
uniformly adding a constant value to each idle time being compared
could having any affect at all on the the final sorted order.

I completely agree.

Just sort by lastTimeStamp. Same order, fewer computations.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Jeffrey Schwab
Guest
PostPosted: Wed Nov 16, 2005 12:30 pm    Post subject: Re: question on sorting a vector Reply with quote
Allan W wrote:
Quote:
allan_w (AT) my-dejanews (DOT) com


tcl wrote:

I want to be able to sort objects in a vector based on
how long the objects have been in idle.


Greg Herlihy wrote:

I think you probably should review whether the sortByIdelTime
comparison routine really needs a reference time. I don't see how
uniformly adding a constant value to each idle time being compared
could having any affect at all on the the final sorted order.


I completely agree.

Just sort by lastTimeStamp. Same order, fewer computations.

Would it be worth saving the initial time stamp, so that subsequent
time_t values can be checked for overflow?

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Allan W
Guest
PostPosted: Thu Nov 17, 2005 8:03 am    Post subject: Re: question on sorting a vector Reply with quote
Quote:
Allan W wrote:
Just sort by lastTimeStamp. Same order, fewer computations.

Jeffrey Schwab wrote:
Quote:
Would it be worth saving the initial time stamp, so that subsequent
time_t values can be checked for overflow?

I don't understand the question.

We're talking about sorting a container that already has saved time_t
values.
If they're going to overflow, it will happen before they're stored.
When we get to sorting, all we need to do is compare them -- which
time_t value is later. What can overflow?


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Carl Barron
Guest
PostPosted: Fri Nov 18, 2005 12:05 am    Post subject: Re: question on sorting a vector Reply with quote
In article <1132182149.952047.101710 (AT) o13g2000cwo (DOT) googlegroups.com>,
Allan W <allan_w (AT) my-dejanews (DOT) com> wrote:

Quote:
Allan W wrote:
Just sort by lastTimeStamp. Same order, fewer computations.

Jeffrey Schwab wrote:
Would it be worth saving the initial time stamp, so that subsequent
time_t values can be checked for overflow?

I don't understand the question.

We're talking about sorting a container that already has saved time_t
values.
If they're going to overflow, it will happen before they're stored.
When we get to sorting, all we need to do is compare them -- which
time_t value is later. What can overflow?

a 32 bit time_t range is 136.099300834 years and using a user time_t

as a base can extend the valid compare range by 136+ years,

a 64 bit time_t range is 1.08806874423e+23 years and I'd say the
question is mute:)

the fact that the time_t stored has already overflowed, does not
mean that if we know it overflowed that we can not still obtain a valid
compare despite the overflow!

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Jeffrey Schwab
Guest
PostPosted: Fri Nov 18, 2005 12:06 am    Post subject: Re: question on sorting a vector Reply with quote
Allan W wrote:
Quote:
Allan W wrote:

Just sort by lastTimeStamp. Same order, fewer computations.


Jeffrey Schwab wrote:

Would it be worth saving the initial time stamp, so that subsequent
time_t values can be checked for overflow?


I don't understand the question.

We're talking about sorting a container that already has saved time_t
values.
If they're going to overflow, it will happen before they're stored.
When we get to sorting, all we need to do is compare them -- which
time_t value is later. What can overflow?

In practice, std::time() usually returns the number of seconds since
January 1, 1970, and time_t is usually a typedef for "long int" --
plenty big enough to hold the current time.

Of course, time_t does not actually store absolute time values; it
stores time modulus some large integer, e.g. 2**31. Eventually, the
maximum possible value of time_t will be reached, and the next value
returned by time() will be appear to be less than the previous value.
This could lead to an incorrect sort. If a reference time is first
subtracted from each value, the problem goes away, assuming no two times
differ by more than numeric_limits<time_t>::max() -
numeric_limits<time_t>::min().

Comparison of time_t values should give an accurate ordering of time
stamps, as long as the recorded times are all between 1969 and 2038,
exclusive. This is probably fine for object idle times, but it is an
assumption that I would feel the need to comment.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Francis Glassborow
Guest
PostPosted: Fri Nov 18, 2005 4:40 pm    Post subject: Re: question on sorting a vector Reply with quote
In article <171120051657398409%cbarron413 (AT) adelphia (DOT) net>, Carl Barron
<cbarron413 (AT) adelphia (DOT) net> writes
Quote:
a 32 bit time_t range is 136.099300834 years and using a user time_t
as a base can extend the valid compare range by 136+ years,

32-bit integer or floating point type? Signed or unsigned? With the unit
of measurement being a second? The Standard is remarkably silent on
these issues. And exactly how do you propose that we have a user time_t?
Users are not permitted (in conforming code) to provide their own.

Quote:

a 64 bit time_t range is 1.08806874423e+23 years and I'd say the
question is mute:)

That figure does not appear to be compatible with your previous one
(2^64 = 2^32 * 2^32. 2^32 = (approx) 10^11. I think the figure you give
for 64-bit is in units of measurement, not years.
Quote:

the fact that the time_t stored has already overflowed, does not
mean that if we know it overflowed that we can not still obtain a valid
compare despite the overflow!

If time_t has overflowed we are in undefined behaviour land unless
time_t is a typedef for an unsigned integer type. That means that we
might no longer have a working computer:-)

--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.