Re: about new and delete
theList.erase(p); // Warning, O(n)!!!!!
That's not O(n) or O(1).
Not according to you, it is.
No. According to me it's undefined behavior.
That's Undefined Behavior because you haven't
initialized p to anything.
Free honking clue: the "// ???" parts specifies bits of code left out of
the example, for brevity.
"For brevity" is an excuse for "I can't give you actual code which you
can compile and which would demonstrate removal in constant time".
You conveniently left out the initialization of p. Please show me how
you initialize p to point to the exact middle of theList.
Well, just for shits and giggles:
// ??? (for a smaller value of ???)
theList.erase(p); // Warning, O(n), according to Juha!!!!!
p doesn't point to the middle of the container. You claimed that an
element can be removed from the middle in O(1). Your code doesn't
If you are now changing your argument to "you can remove from the
beginning in O(1)" then your whole dismissal of std::deque crumbles
because you can remove from the beginning of a std::deque in O(1) as well.
You won't give an actual example of removing from the *middle* of a
std::list in O(1) because it's not possible. You have to get to the
middle somehow, you can't get the iterator pointing there by magic. You
have to obtain it somehow, and that somehow is an O(n) operation.
That's why you refuse to give me the function which takes a std::list
and removes the middle element. Because IT'S NOT POSSIBLE to do that in
O(1), and your whole argument would crumble.
What you fail to grok, is that when you have a member of containe that
you want removed, you already have its iterator, you don't need to
search for it.
What do you mean I already have its iterator? No I don't.
That's why nobody will let you write production code :-)
You are still refusing to show me the function which removes the
middle element in a std::list in constant time.
Remember, that's *exactly* what you claimed: That you can remove an
element from the middle of a std::list in constant time. Well, prove it.
How hard can it be? Just give me the function which will do exactly that.
But of course you won't do it, because IT'S NOT POSSIBLE.
Please show me how you get that iterator. You claim that removing an
object from the middle of a list is O(1). Prove it to me. You are so
smart that it shouldn't be a problem to you.
I'm very smart. If I add objects to a list, that I know that I'll want
to remove later, I'll save their iterator, someplace, so when I need to
remove it, I won't need to search for it.
By doing that you are just hiding the O(n) behavior inside the list
initialization. Your removal didn't become O(1). You simply moved part
of the removal routine from one place to another to try to hide the fact.
That's why they pay me the big bucks, Grasshopper.
They pay you big bucks even though you didn't even realize that
std::deque beats your beloved std::list hands down in speed. Then you
come here with a proud tone of voice to announce how std::list is the
best solution to the original problem because it's the fastest solution.
You're just grasping at straws here, desperately trying to create a
contrived situation that fits your preconceived notions.
I don't think it's very contrived: Write a C++ function which takes a
std::list as (a reference) parameter, and removes the element in the
exact middle of the list.
I'll write it as soon as I lose the ability to write entire applications
You will never write it because IT'S NOT POSSIBLE. A function which
does that in O(1) cannot exist. You cannot magically get an iterator to
the middle element of a std::list in O(1). Hence you cannot remove the
middle element in O(1).
something that will often occur inside ivory halls of academia, where
brownie points are awarded for completing a purely theoretical excersize
that bears no relevance to anything that will occur in practice.
Yes, in practice you will never need to, for example, pick elements
from a container in random order, without repetitions (and of course as
fast as possible).
Of course you do.
You don't even seem to understand sarcasm. And by misunderstanding my
sarcasm you disproved your own claim that removing an element from a
std::vector in O(1) without preserving the ordering would only be
theoretical rather than a useful technique in practice.
See? Look who is changing the topic.
The individual who first brought up dequeue. Hint: it wasn't me.
I find it hilarious that when std::deque beats your beloved std::list
in all possible ways, you try to shrug it off with some ridiculous
meta-argument about changing topics.
Your sense of humor is a bit bizarre, then. You've just shrugging off me
pointing out that it was you who changed the topic by bringing up deque
in the first place, yet you don't find /that/ funny. How come?
Yes, try to shrug the whole embarrassing std::deque beating your
std::list in speed (which was your *original* argument in this thread)
by keeping that ridiculous "don't change the topic" argument.
It was you who said that std::list is a "win" in the original
situation. I proved you that it isn't because there's an even more
efficient data container than std::list, namely std::deque. Now you are
so embarrassed to admit that it indeed is so, that you just keep with
your "don't change the topic" argument.
"fastest" != "always fastest". Elementary, my dear Watson, elementary.
Pushing back into a std::deque is, as far as I can see, *always*
faster than pushing back into a std::list. Please show me otherwise.
"As far as I can see" is a revealing hint that you are not necessarily
convinced of that yourself. Your homework assignment (since you're so
fond of them), is to find the cases when it's not.
Unlike you, I actually measured it and posted some code and results.
You never disproved those results, nor presented any argument whatsoever
why std::list would be faster than std::deque in *any* situation. It's
all there. You can test it yourself.
Then you accuse me of theoretical stuff.
I really find it hilarious how you are unable to disprove the results,
yet are too proud to admit anything, to give any concession. You are too
proud to say "yes, I was wrong, std::deque is indeed much faster than
std::list, making it a better choice for the original poster".
Instead, you keep repeating your "insert in the middle" and "don't
change topics" arguments.
Then please give me the function which removes the element in the
exact middle of a std::list in constant time. Show me some *practical*
code, rather than relying on *theoretical* claims.
You know perfectly well how you've been nailed to the wall on this one.
Removing elements from a list is O(1), and flapping your arms and
throwing a bunch of extra conditions and requirements is not going to
change the basic, underlying fact.
Well, if removing elements from a list is O(1), then give me a
function which removes the middle element of a list in O(1).
You won't give me the function because you *can't* give me the
function. No matter how many times you repeat "you can remove the middle
element in O(1)", that doesn't make it true. If it's true, surely you
can show me some actual code doing so. You won't because you can't.
You accuse me of imposing some requirements. Well, do you really think
that removing an element from a list in O(1) has no requirements? If you
think hard, you'll see what this special requirement is. It's pretty
simple. When you say "you can remove an element in O(1)" you are
blissfully ignoring this small requirement.
When you say "removing *from the middle* can be done in constant time"
you are conveniently skipping the part where you have to actually get an
actual iterator pointing to the middle. You are only focusing on the
And you are conveniently ignoging the part where you don't need to "get"
an iterator, since you've already "got" it, when you added the object to
the list in the first place.
"flapping your arms and throwing a bunch of extra conditions and
requirements is not going to change the basic, underlying fact."
It's funny how you accuse me of imposing extra requirements, while you
are doing the exact same thing.
Besides, by putting the retrieval of the middle element inside the
initialization of the list you are not changing the O() complexity in
any way. You are simply trying to disguise it. Getting the iterator is
still O(n). You are still doing it inside a loop which is traversing the
Even I can think of better ways of getting an iterator pointing to the
middle of a list.
I think that the disconnect here is that you're not really familiar with
std::list, you've rarely used it, so you are ignorant of how to properly
use this container in practice.
Haha. For your information, I have implemented a data container which
is (almost) completely equivalent to std::list, but uses a slightly
different technique (namely, it's a xor list). I have a pretty good idea
how std::list works. (The advantage of a xor list is that each node
consumes less memory, especially when used with a space-efficient memory
allocator. The disadvantage is that modifying the list using an iterator
also invalidates any iterator which might be pointing to the next
element (or previous, depending on how you implement it).)
Implementing your own STL-style data container (such as a linked list)
is actually pretty didactic. You get to understand quite a lot about the
design of the standard library.
For example, while trying to implement the container, you will
invariably encounter this problem: You will need to have these two
YourList::YourList(size_type n, const value_type& value);
YourList::YourList(InputIterator b, InputIterator e);
Why is that a problem? Because if you do this:
YourList<int> l(10, 20);
you will see that the compiler actually calls the constructor taking two
input iterators (because it's a better match), not the constructor
taking the integrals. Yet, somehow, the STL data containers still manage
to do the right thing, even though the wrong constructor is being
called. If you want to make your own data container fully compatible
with STL containers, you'll have to solve that problem yourself as well.
Another interesting problem is this: A std::list takes an allocator as
template parameter (and an instance of such allocator as constructor
parameter). However, the allocator specified as template parameter is
configured to allocate objects of type value_type, not objects of the
internal node type. But std::list needs to allocate interal nodes (which
is usually a struct), not objects of type value_type. How is this
problem solved with allocators?
And yet another interesting question: If you have two lists, A and B,
and you have an iterator pointing to A.end(), and then you perform a
"A.swap(B);", where will the iterator end up pointing? To the end of A
or to the end of B?
I do know a fair bit about std::list. Your move.