 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
wogston
Guest
|
 Posted: Sun Oct 26, 2003 7:29 pm Post subject: std::list |
 |
|
Greets. I don't quite find this from the documentation on the net, and I
don't have the ANSI documentation.
Does std::list ::assign() and ::insert() support copying from the same
object? Example:
std::list<int> v;
for ( int i=0; i<10; ++i )
v.push_back(i);
std::list
v.insert( itr, v.begin(), v.end() );
... is this defined, or undefined? I'm assuming it is defined, because online
documentation such as Dinkumware's and MSDN don't say anything about any
limitations, but want to be sure. Apologies if this is a stupid question.
-x
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
 |
wogston
Guest
|
| Posted: Sun Oct 26, 2003 11:14 pm Post subject: Re: std::list |
|
|
| Quote: | .. is this defined, or undefined? I'm assuming it is defined, because
online
documentation such as Dinkumware's and MSDN don't say anything about any
limitations, but want to be sure. Apologies if this is a stupid question.
|
Apologies for stupid question, when I realized the post didn't show up
promptly I understood this group is moderated! Anyway, why I was asking, was
because I thought the self-assignment case would be prohibitively expensive
to implement.
But after some thinking (I didn't cheat and look at Dinkumware, RogueWave,
STLPort, etc.. honest!), figured way to do it efficiently. It took about 5
minutes of my time, and already wasted too much of your time with this
silliness. Here's my solution:
First, the ::assign(iterator first, iterator last)
(apologies for slightly incorrect parameters if they are not 100% precise,
just want to present the idea)
1. erase( begin(),first )
2. attach the sequence between first and last to begin
3. erase( last,end() )
That's just pseudo, have to in the implementation ofcourse make sure the
iterators are valid through the process (so treat above only as pseudo).. so
I figured how that can be done fast.
Then the ::insert(iterator i, const_iterator first, const_iterator last)
In case of self-assignment, merely construct a temporary sequence and then
insert it before i. Implementation again has to make sure iterators are
valid through the implementation.
I detect self-assignment by storing "this" pointer for the container in the
linked-list node. (node is internal presentation of the data, iterator and
reverse_iterator are only front-ends), for instance, this is how ::begin()
looks for me:
iterator begin() {
return iterator(this,m_begin.m_next); }
And then detect the self-assignment like this:
if ( i.container() == this ) { ...
I am such an idiot, 100% apologies, I was just implementing std::list as
mental exercise and read only online MSDN and Dinkumware documentation (like
said in original post, don't have the ANSI specs :(
So apologies for wasting everyone's time with so obvious matter, should have
thought 5 minutes longer before posting. I realize now I was a total retard.
:(
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Tue Nov 04, 2003 7:26 am Post subject: Re: std::list |
|
|
In article <bngh17$hm$1 (AT) phys-news1 (DOT) kolumbus.fi>,
[email]someone (AT) microsoft (DOT) com[/email] ("wogston") wrote:
| Quote: | Greets. I don't quite find this from the documentation on the net, and I
don't have the ANSI documentation.
Does std::list ::assign() and ::insert() support copying from the same
object? Example:
std::list<int> v;
for ( int i=0; i<10; ++i )
v.push_back(i);
std::list
v.insert( itr, v.begin(), v.end() );
.. is this defined, or undefined? I'm assuming it is defined, because online
documentation such as Dinkumware's and MSDN don't say anything about any
limitations, but want to be sure. Apologies if this is a stupid question.
|
No, this pattern is not supported by the standard. A precondition on
these functions is that the iterators do not reference values in the
object being modified (reference 23.1.1/4).
-Howard
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
wogston
Guest
|
| Posted: Tue Nov 04, 2003 6:38 pm Post subject: Re: std::list |
|
|
| Quote: | No, this pattern is not supported by the standard. A precondition on
these functions is that the iterators do not reference values in the
object being modified (reference 23.1.1/4).
|
Oh, okay, so it is OK to assert for self-assignment? Actually, I have two
options:
- drop the "list*" member variable for self-assignment detection in iterator
- keep it, and assert
The first choise would be less overhead, just let undefined behaviour fall
at no runtime cost, to client's head if he invokes it.. I did manage to
write *very* efficient ::assign() and ::insert() when the controlled
sequence between "first" and "last" was within the container.
1)
::assign()
erase() elements before, and after the sequence.
2)
::insert()
Create a new sequence while iterating the input one, then glue it between
"it" and "--it", for the implementation I practised on this was trivial. I
had it in "traditional" implementation with next and prev pointer in the
internal node struct, which implemented the linked list (used iterators
merely as front-end). I recently wrote alternative implementation with node
storing only prev^next, in this implementation I haven't yet "optimized" the
::append() and ::insert(), but glad to hear that don't have to. ;-)
(I shall drop the container member, and the asserts.. unless I misunderstood
what you wrote above, in which case I will be glad to be corrected)
Here's what I've got so far:
http://www.liimatta.org/misc/list.hpp
http://www.liimatta.org/misc/list.jpg
The later is "screenshot" with testcode and results side-by-side. Tested
against Dinkumware's implementation. The STLPort 4.5.1020 (?) was twice as
fast as the Dinkumware, but still slower than the list.hpp implementation.
I'm perfectly aware that I am not yet throwing exceptions where should, and
not doing write to temporaries before assignment where appropriate for
thread safety, etc.. so my implementation isn't exception or threading safe.
Currently I am not using the allocator object, since it's redundant for this
implementation, but I'm still keeping it as template argument for
compatibility's sake.
I know the code is horrible mess, but my goal is to improve it to learn
better: I'm finally going to drop the custom containers from Open Source
library I have been maintaining the last decade (the library has been OS
only for the past two years).
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Powered by phpBB © 2001, 2006 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
