Best reorderable list structure?

A

alan

Hello all, would just like to ask what would be the best reorderable
list structure.

Basically, I have to keep track of the order of some objects. The
most recently referred object would be in the top of the list. If an
object is referred to, and it isn't at the top of the list, it is put
to the top of the list and the other objects moved down:

1 omega
2 alpha
3 beta <- referred to
4 gamma

then:
1 beta
2 omega
3 alpha
4 gamma

At periodic times, I would then promote an object to the second-
topmost of the list (but not the first, since only the most recently
referred object must be at the top). This will usually be the
bottommost element of the list, but *not* always.
For example:
1 beta
2 omega
3 alpha
4 gamma <- I choose this for promotion

then:
1 beta
2 gamma
3 omega
4 alpha

Basically I need a list structure where I can rearrange particular
list members to the top or second position, with everyone moving
downwards correspondingly.

I've looked at std::slist, which provides splice_after which will work
with my second requirement (I think) but it doesn't seem to be able to
do the first requirement. Or should I look at std::list instead? Or
another container class?

---
In case you're curious about the application, I have a set of 3
affinities (and would like to keep open the possibility of future
affinities). The player may exercise an affinity to eventually
increase it, but if an affinity is increased by exercise, another
affinity must decrease.

Whenever an affinity is exercised, it is put to the top of the list.
The least recently exercised affinity then drifts to the bottom. When
the affinity being exercised is finally increased, the least recently
exercised nonzero affinity is decremented and put at the second
position on the list. By putting it on the second position when it is
decremented, if the player concentrates on one affinity only, each of
the other affinities are penalized equally until it becomes zero, at
which point the remaining affinities are the only ones affected.
 
V

Victor Bazarov

alan said:
Hello all, would just like to ask what would be the best reorderable
list structure.

Basically, I have to keep track of the order of some objects. The
most recently referred object would be in the top of the list. If an
object is referred to, and it isn't at the top of the list, it is put
to the top of the list and the other objects moved down:

1 omega
2 alpha
3 beta <- referred to
4 gamma

then:
1 beta
2 omega
3 alpha
4 gamma

At periodic times, I would then promote an object to the second-
topmost of the list (but not the first, since only the most recently
referred object must be at the top). This will usually be the
bottommost element of the list, but *not* always.
[..]

std::priority_queue? Besides, you can always swap values in a map,
or a list, or even a vector, with a great ease. All you need is to
determine (design) the correct algorithm to find what to swap with
what.

V
 
A

alan

alan said:
Hello all, would just like to ask what would be the best reorderable
list structure.
Basically, I have to keep track of the order of some objects. The
most recently referred object would be in the top of the list. If an
object is referred to, and it isn't at the top of the list, it is put
to the top of the list and the other objects moved down:
1 omega
2 alpha
3 beta <- referred to
4 gamma
then:
1 beta
2 omega
3 alpha
4 gamma
At periodic times, I would then promote an object to the second-
topmost of the list (but not the first, since only the most recently
referred object must be at the top). This will usually be the
bottommost element of the list, but *not* always.
[..]

std::priority_queue? Besides, you can always swap values in a map,
or a list, or even a vector, with a great ease. All you need is to
determine (design) the correct algorithm to find what to swap with
what.
Well, it's not exactly a straight swap, which means I have to swap
everything from the point of source backwards to the point of
destination.

Possibly slist or list's splice()? I glossed over splice() when I saw
that the two-argument form did not allow copying from the same list,
but I reread it a bit and saw that the 3- and 4-argument forms allow
using the same list.
So I suppose the first operation would be something like:

exercise_order.splice(exercise_order.begin() , exercise_order,
selected_point);

the second operation:
exercise_order.splice(exercise_order.begin()+1 /*is this correct?*/,
exercise_order, selected_point);
 
V

Victor Bazarov

alan said:
alan said:
Hello all, would just like to ask what would be the best reorderable
list structure.
Basically, I have to keep track of the order of some objects. The
most recently referred object would be in the top of the list. If
an object is referred to, and it isn't at the top of the list, it
is put to the top of the list and the other objects moved down:
1 omega
2 alpha
3 beta <- referred to
4 gamma
then:
1 beta
2 omega
3 alpha
4 gamma
At periodic times, I would then promote an object to the second-
topmost of the list (but not the first, since only the most recently
referred object must be at the top). This will usually be the
bottommost element of the list, but *not* always.
[..]

std::priority_queue? Besides, you can always swap values in a map,
or a list, or even a vector, with a great ease. All you need is to
determine (design) the correct algorithm to find what to swap with
what.
Well, it's not exactly a straight swap, which means I have to swap
everything from the point of source backwards to the point of
destination.
[..]

Right. Sorry. Extract and re-insert is more like it. The list is
very good at that.

V
 
J

Jim Langston

Victor Bazarov said:
alan said:
alan wrote:
Hello all, would just like to ask what would be the best reorderable
list structure.

Basically, I have to keep track of the order of some objects. The
most recently referred object would be in the top of the list. If
an object is referred to, and it isn't at the top of the list, it
is put to the top of the list and the other objects moved down:

1 omega
2 alpha
3 beta <- referred to
4 gamma

then:
1 beta
2 omega
3 alpha
4 gamma

At periodic times, I would then promote an object to the second-
topmost of the list (but not the first, since only the most recently
referred object must be at the top). This will usually be the
bottommost element of the list, but *not* always.
[..]

std::priority_queue? Besides, you can always swap values in a map,
or a list, or even a vector, with a great ease. All you need is to
determine (design) the correct algorithm to find what to swap with
what.
Well, it's not exactly a straight swap, which means I have to swap
everything from the point of source backwards to the point of
destination.
[..]

Right. Sorry. Extract and re-insert is more like it. The list is
very good at that.

V

I was toying around with this to see how I would code it, and I think I
would use a std::vector isntead of a list just because list does not have
operator[] defined and so you have to keep track of which item in the list
your at other than a numberical iterator. list or vector would both work
though, but each has it's drawbacks. vector doesn't have push_front, list
doesn't have operator[]. Would be nice if they both had both but they don't
*shrug*
 
J

James Kanze

Jim said:
Victor Bazarov said:
alan said:
alan wrote:
Hello all, would just like to ask what would be the best reorderable
list structure.
Basically, I have to keep track of the order of some objects. The
most recently referred object would be in the top of the list. If
an object is referred to, and it isn't at the top of the list, it
is put to the top of the list and the other objects moved down:
1 omega
2 alpha
3 beta <- referred to
4 gamma
then:
1 beta
2 omega
3 alpha
4 gamma
At periodic times, I would then promote an object to the second-
topmost of the list (but not the first, since only the most recently
referred object must be at the top). This will usually be the
bottommost element of the list, but *not* always.
[..]
std::priority_queue? Besides, you can always swap values in a map,
or a list, or even a vector, with a great ease. All you need is to
determine (design) the correct algorithm to find what to swap with
what.
Well, it's not exactly a straight swap, which means I have to swap
everything from the point of source backwards to the point of
destination.
[..]
Right. Sorry. Extract and re-insert is more like it. The list is
very good at that.
I was toying around with this to see how I would code it, and
I think I would use a std::vector isntead of a list just
because list does not have operator[] defined and so you have
to keep track of which item in the list your at other than a
numberical iterator. list or vector would both work though,
but each has it's drawbacks. vector doesn't have push_front,
list doesn't have operator[]. Would be nice if they both had
both but they don't *shrug*

I'm not sure I understand. He doesn't say how the object is
referred to, or how he finds which object he wants to move to
the front. If he's using std::find or std::find_if, he's got
the iterator.

I think, in fact, that this is the sort of thing that
list<>::splice was designed for. Something like

List::iterator targetPos
= std::find( myList.begin(), myList.end(), "beta" ) ;
if ( targetPos != myList.end() ) {
myList.splice( myList.begin(), myList, targetPos ) ;
}
 
J

James Kanze

On Nov 20, 9:46 pm, "Victor Bazarov" <[email protected]> wrote:

[...]
Possibly slist or list's splice()? I glossed over splice() when I saw
that the two-argument form did not allow copying from the same list,
but I reread it a bit and saw that the 3- and 4-argument forms allow
using the same list.
So I suppose the first operation would be something like:
exercise_order.splice(exercise_order.begin() , exercise_order,
selected_point);

That's what I'd do.
the second operation:
exercise_order.splice(exercise_order.begin()+1 /*is this correct?*/,
exercise_order, selected_point);

You can't use addition on the iterator of a list; you'd have to
do something like:

List::iterator it = exercise_order.begin() ;
++ it ;
exercise_order.splice( it, exercise_order, selected_point ) ;

Plus, of course, add some tests as to whether the list was
empty, etc. in both cases.
 
A

alan

You can't use addition on the iterator of a list; you'd have to
do something like:

List::iterator it = exercise_order.begin() ;
++ it ;
exercise_order.splice( it, exercise_order, selected_point ) ;
I found that too - ended up doing this:
exercise_order.splice(++(exercise_order.begin()), exercise_order,
selected_point);
Thanks anyway.
Plus, of course, add some tests as to whether the list was
empty, etc. in both cases.
Since I find the selected_point via find(), and never do the operation
if I don't find the selected_point, then the list can't have been
empty. Also, I never delete items from the list during normal
execution.
 
J

James Kanze

I found that too - ended up doing this:
exercise_order.splice(++(exercise_order.begin()), exercise_order,
selected_point);

That may or may not work, depending on the implementation. In
most implementations, operator++ is a member function of
std::list<>::iterator, and it will work. An implementation may
make it a non-member free function, however, in which case, your
version shouldn't compile.
 
A

alan

That may or may not work, depending on the implementation. In
most implementations, operator++ is a member function of
std::list<>::iterator, and it will work. An implementation may
make it a non-member free function, however, in which case, your
version shouldn't compile.
Thanks for the heads up! I'll modify the code to use an iterator
variable then.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top