Hi,
I want to move an element from a std::list to the end of the same list.
To get this done, I thought I'd just do something like:
std::list <intlst;
lst.push_back (0);
lst.push_back (1);
lst.push_back (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());
This does change the list from [0, 1, 2] to [1, 2, 0]. The problem is,
that any iterators I have pointing to '0' are now invalid. Are there ways to
get this done without invalidating my iterators? Theoretically, it should be
possible (if I would reimplement a list container myself), shouldn't it?
Does the Standard provide methods to achieve this?
Now for some more background information: The application is a server
and the list holds all connected clients. Whenever some action has been
taken, the corrensponding element in the list is moved[*] to the end of the
list. This way, the first element will always be the client that has
responded (or has been served) _least_ recently. Along with the time, I can
easily timeout on any client. I just examine the first element in the
"client list", wait at most some time T (which I can calculate now) and if
nothing happened with this client during that time, I know it has timed out.
As it stands, splice would be perfect. But I also manage another list with
iterators into the "client list". That list is a "job list" and holds
iterators to clients, that have pending jobs (pending, because a request is
already being processed for that client and requests can only be satisfied
in the same order they arrive). And this is the problem. When moving a
client to the end of the "client list", the "job list" could then contain
invalid iterators.
One solution would be, to store the actual client structures somewhere
else (for example yet another list) and have both the "client list" and the
"job list" just contain iterators into that "store list". This would solve
it all, really, but I am not quite happy with this solution. It feels
somewhat clumsy. I'd appreciate any more thoughts on this!
[*] (I do not want to actually move any memory, but instead just
rearrange the next/prev node-links.. but I just realize that I am not even
sure whether splice may deep-copy or not ..)
Thanks for your help!
--
jb
(reply address in rot13, unscramble first)
6  2777 
Jakob Bieling wrote:
Hi,
I want to move an element from a std::list to the end of the same
list. To get this done, I thought I'd just do something like:
std::list <intlst;
lst.push_back (0);
lst.push_back (1);
lst.push_back (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());
This does change the list from [0, 1, 2] to [1, 2, 0]. The problem
is, that any iterators I have pointing to '0' are now invalid. Are
there ways to get this done without invalidating my iterators?
Theoretically, it should be possible (if I would reimplement a list
container myself), shouldn't it? Does the Standard provide methods to
achieve this?
I think you're looking to 'erase' the iterator and then 'insert' the
value where you need it. None of the interators (except the one which
you're manipulating) is invalidated.
[..]
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Victor Bazarov wrote:
Jakob Bieling wrote:
> I want to move an element from a std::list to the end of the same
list. To get this done, I thought I'd just do something like:
std::list <intlst;
lst.push_bac k (0);
lst.push_bac k (1);
lst.push_bac k (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());
This does change the list from [0, 1, 2] to [1, 2, 0]. The problem
is, that any iterators I have pointing to '0' are now invalid. Are
there ways to get this done without invalidating my iterators?
Theoreticall y, it should be possible (if I would reimplement a list
container myself), shouldn't it? Does the Standard provide methods to
achieve this?
I think you're looking to 'erase' the iterator and then 'insert' the
value where you need it. None of the interators (except the one which
you're manipulating) is invalidated.
Yes, but that is the problem. I may have an iterator pointing to the
element I am placing at the end. And that iterator should still be valid
after changing the list. But as I do more and more research on this, I think
the, what I called "clumsy", solution with one list of elements and two
lists of iterators is the way to go after all. Comments welcome!
Thanks!
--
jb
(reply address in rot13, unscramble first)
Jakob Bieling wrote:
Victor Bazarov wrote:
>Jakob Bieling wrote:
>> I want to move an element from a std::list to the end of the same
list. To get this done, I thought I'd just do something like:
std::list <intlst;
lst.push_ba ck (0);
lst.push_ba ck (1);
lst.push_ba ck (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());
This does change the list from [0, 1, 2] to [1, 2, 0]. The
problem is, that any iterators I have pointing to '0' are now
invalid. Are there ways to get this done without invalidating my
iterators? Theoretically, it should be possible (if I would
reimplement a list container myself), shouldn't it? Does the
Standard provide methods to achieve this?
>I think you're looking to 'erase' the iterator and then 'insert' the
value where you need it. None of the interators (except the one
which you're manipulating) is invalidated.
Yes, but that is the problem. I may have an iterator pointing to
the element I am placing at the end. And that iterator should still
be valid after changing the list.
But that's impossible.
Let me take it back. It's possible. You can move all elements before
and after the iterator instead. But that would make any iterators to
those elements invalid.
But as I do more and more research
on this, I think the, what I called "clumsy", solution with one list
of elements and two lists of iterators is the way to go after all.
Comments welcome!
If you wrap it in a function that would return a new iterator, why
couldn't you simply do
template<class C>
typename C::iterator move_element(C& c, typename C::iterator from,
typename C::iterator before)
{
typename C::value_type v = *from;
c.erase(from);
return c.insert(before , v);
}
....
myiterator = move_element(my list, myiterator, mylist.end());
Perhaps you're just too hung up on the design that you have (and it
is probably marvelous, I've no doubt), but don't dismiss other (and
probably simpler) solutions.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Victor Bazarov wrote:
Jakob Bieling wrote:
>Victor Bazarov wrote:
>>Jakob Bieling wrote:
>>> I want to move an element from a std::list to the end of the
same list. To get this done, I thought I'd just do something like:
std::list <intlst;
lst.push_bac k (0);
lst.push_bac k (1);
lst.push_bac k (2);
lst.splice (lst.end (), lst, lst.begin (), ++ lst.begin ());
>>>problem is, that any iterators I have pointing to '0' are now
invalid. [..]
>>I think you're looking to 'erase' the iterator and then 'insert' the
value where you need it. None of the interators (except the one
which you're manipulating) is invalidated.
> Yes, but that is the problem. I may have an iterator pointing to
the element I am placing at the end. And that iterator should still
be valid after changing the list.
But that's impossible.
Let me take it back. It's possible. You can move all elements before
and after the iterator instead. But that would make any iterators to
those elements invalid.
:)
Guess I am making too many assumptions about the implementation for this
to work. Or my idea is flawed. Ideally, if an iterator holds a pointer to a
node, changing the next/prev links of that node will not affect other
iterators to this element, because the node structure is still where it used
to be (ie. the memory address will not change).
>But as I do more and more research
on this, I think the, what I called "clumsy", solution with one list
of elements and two lists of iterators is the way to go after all.
Comments welcome!
If you wrap it in a function that would return a new iterator, why
couldn't you simply do
[ move function snipped]
Because then I would have traverse the "job list" to find a possible
iterator to the old element and update that. I was trying to get around
that.
Perhaps you're just too hung up on the design that you have (and it
is probably marvelous, I've no doubt), but don't dismiss other (and
probably simpler) solutions.
I guess I will just let it be for today and rethink this whole thing
tomorrow. Maybe I will find one of the simpler solutions :) Thanks for your
ideas!
regards
--
jb
(reply address in rot13, unscramble first)
Jakob Bieling wrote:
>
This does change the list from [0, 1, 2] to [1, 2, 0]. The problem is,
that any iterators I have pointing to '0' are now invalid.
Are you sure ? Anyhow, I don't know what splice says about splicing
from the same container but I would not do it. I would splice the
element into a temporary container and then splice it back into the
original. In theory, the iterator should still be valid.
... Are there ways to
get this done without invalidating my iterators? Theoretically, it should be
possible (if I would reimplement a list container myself), shouldn't it?
You can implement something to do this yourself. In fact I have and
it's open source. It is in an unofficial version of the Austria C++
library that you can pull from http://netcabletv.org/public_release...b-6126.tar.bz2
Warning - it's 100 megs. This contains a generic "activity list" type
that is used as a thread pool. It's quite simple to use. You don't
have to use it like a thread pool, you can bring in your own "thread
provider". This might be too specific.
There is also the "at::List" stuff which is as ugly as all get out but
it does also provide a way for an object to "know" which lists it's
connected to and to remove itself from any list.
The whole "self aware" object issue is something that the stl containers
make awfully difficult.
Does the Standard provide methods to achieve this?
Probably but with alot of complexity in client code. You can probably
write something simpler for client code yourself.
Now for some more background information: The application is a server
and the list holds all connected clients. Whenever some action has been
taken, the corrensponding element in the list is moved[*] to the end of the
list.
Wouldn't you want to remove it from the "active" list when somthing was
done and only place it back on the todo list once a new event occurred
that required work done on that connection ?
.... This way, the first element will always be the client that has
responded (or has been served) _least_ recently. Along with the time, I can
easily timeout on any client.
BTW, race conditions in this kind of code are very easy to create. I've
written servers like this many times (unfortunately) and it's quite
involved. In a multi threaded environment it is quite tricky to get right.
....
One solution would be, to store the actual client structures somewhere
else (for example yet another list) and have both the "client list" and the
"job list" just contain iterators into that "store list". This would solve
it all, really, but I am not quite happy with this solution. It feels
somewhat clumsy. I'd appreciate any more thoughts on this!
How do you clean up the iterators ?
>[*] (I do not want to actually move any memory, but instead just
rearrange the next/prev node-links.. but I just realize that I am not even
sure whether splice may deep-copy or not ..)
list::splice does not do a deep copy. std::list assignment or copy
construct does.
Gianni Mariani wrote:
Jakob Bieling wrote:
> This does change the list from [0, 1, 2] to [1, 2, 0]. The
problem is, that any iterators I have pointing to '0' are now
invalid.
Are you sure ? Anyhow, I don't know what splice says about splicing
from the same container but I would not do it. I would splice the
I just checked and it is guaranteed to work. But it officially
invalidates the iterators/references to spliced elements, which is the
problem.
>... Are there ways to
get this done without invalidating my iterators? Theoretically, it
should be possible (if I would reimplement a list container myself),
shouldn't it?
You can implement something to do this yourself. In fact I have and
it's open source. It is in an unofficial version of the Austria C++
library that you can pull from
http://netcabletv.org/public_release...b-6126.tar.bz2
Thanks, I will have a look into that.
> Now for some more background information: The application is a
server and the list holds all connected clients. Whenever some
action has been taken, the corrensponding element in the list is
moved[*] to the end of the list.
Wouldn't you want to remove it from the "active" list when somthing
was done and only place it back on the todo list once a new event
occurred that required work done on that connection ?
Well, the "active" list (I think this is what I called "client list"?)
contains all connected clients, no matter if they are currently waiting for
a request to be satisfied or not. I will only remove from there, when a
client disconnects. A client will only get into the "job list", when it has
sent a request while another one is for this client is still in progress.
... This way, the first element will always be the client that has
>responded (or has been served) _least_ recently. Along with the
time, I can easily timeout on any client.
BTW, race conditions in this kind of code are very easy to create. I've
written servers like this many times (unfortunately) and it's
quite involved. In a multi threaded environment it is quite tricky
to get right.
Right, but this is a smaller server and thus single threaded. Otherwise
I would probably have used a lock-free list. But multithreading is nothing
to worry about here :)
> One solution would be, to store the actual client structures
somewhere else (for example yet another list) and have both the
"client list" and the "job list" just contain iterators into that
"store list". This would solve it all, really, but I am not quite
happy with this solution. It feels somewhat clumsy. I'd appreciate
any more thoughts on this!
How do you clean up the iterators ?
Using the above solution, I would already know which iterator in the
"client list" to remove (from the close-notification). For the job-list, I
still have to traverse that list and find the iterator. Since disconnects do
not happen that frequently, this is acceptable.
regards
--
jb
(reply address in rot13, unscramble first) This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Bob Smith |
last post by:
Hi,
I have a Python list. I can't figure out how to find an element's
numeric value (0,1,2,3...) in the list. Here's an example of what I'm doing:
for bar in bars:
if 'str_1' in bar and 'str_2' in bar:
print bar
This finds the right bar, but not its list position. The reason I need
|
by: Markus Ernst |
last post by:
Hello
Reading the follwing document:
http://www.w3.org/TR/WD-positioning-970131#In-flow
it seems very clear that position:relative should be relative to the parent
element. So in the following test case element1 and element2 should be
placed side by side inside a centered white container element:
http://www.markusernst.ch/test.htm
|
by: Glen Able |
last post by:
Without further ado, here's some code:
std::list<int> things;
things.push_back(1);
things.push_back(2);
things.push_back(3);
std::list<int>::iterator it;
int test;
|
by: Vikram |
last post by:
Is it compulsory to set up web.config file for using cache invalidation in
asp.net 2.0.
Is there any way by which we can achive cache invalidation without doing any
setting in web.config.
|
by: wolverine |
last post by:
Hi
I am accessing a map from inside threads. There is a chance
that an element is inserted into the map, from inside any thread. Since
i don't know about thread safety of stl implementation i am using , i
use mutex for thread safety. Now comes the question. Please answer this
question assuming that i am not using a thread safe stl version.
I obtain an iterator to the map from inside the critical
section(protected by mutex). If i use...
| | |
by: David |
last post by:
Is there a way to find which element in an object array the keyword 'this'
is acting upon?
For example:
function doMe(){
var aTags = document.getElementById("list").getElementsByTagName("a");
for (var i=0; i<aTags.length; i++) {
aTags.onclick=function() {
this.className = "myClass";
|
by: Sunil Varma |
last post by:
Hi,
I've to write a function similar to this.
int process(const vector<int>& vct,int key)
{
// Here I've to find the position of key in the vector and do some
processing.
}
|
by: Amit Bhatia |
last post by:
Hi,
I am not sure if this belongs to this group. Anyway, my question is as
follows: I have a list (STL list) whose elements are pairs of integers (STL
pairs, say objects of class T). When I create a new object of class T, I
would like to check if this object already exists in the list: meaning one
having same integers. This can be done in linear time in a list, and
probably faster if I use STL Set instead of list. I am wondering however if...
|
by: Juha Nieminen |
last post by:
Assume we have this:
std::list<Typelist1(10, 1), list2(20, 2);
std::list<Type>::iterator iter = list1.end();
list1.swap(list2);
What happens here, according to the standard?
1) 'iter' still points to list1::end().
2) 'iter' now points to list2::end().
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| | |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |
