Re: about new and delete
Sam wrote:
Juha Nieminen writes:
And what is the complexity of removing an element from the middle of the
list, versus the middle of a vector?
O(n) for both.
Hahahahahaha.
std::list<obj> theList;
// ???
std::list<obj>::iterator p;
// ???
theList.erase(p); // Warning, O(n)!!!!!
Very funny.
That's not O(n) or O(1). That's Undefined Behavior because you haven't
initialized p to anything.
You conveniently left out the initialization of p. Please show me how
you initialize p to point to the exact middle of theList.
Of course you will not show me this. You will try to wiggle out of
that little problem with some incoherent ranting.
If you want to prove me wrong, write a function which
takes a std::list as parameter and removes the element at the exact
middle faster than O(n).
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. Your UB code
above did not have an iterator pointing to the middle of the list. It
had an uninitialized pointer. The program would crash or misbehave. It
would not remove the element in the middle of the list.
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.
But of course you won't do that, because you can't.
Thank you for playing.
Oh, I'm ready to play, but clearly you aren't. When you are required
to show some actual working code, you won't provide it. An incomplete
piece of code with undefined behavior is not going to suffice.
I can provide any code you want to back up my claim.
And if you don't specify that the *order* of the elements must be
maintained (as you never did), then removing the middle element from a
vector becomes O(1) (by assigning the last element to it and then
shrinking the vector by one). Removing it from a std::list is still O(n).
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.
That's exactly what you claimed to be able to do in constant time. How
is that contrived? Now show me.
I also think it's not very contrived that, if we remove the
requirement for the elements to keep their ordering within the
container, doing that in O(1) with std::vector is trivial, while with
std::list it's still O(n). There are many practical situations where
this is a good technique to know. (One practical example is picking
elements in random order, without any element being picked twice.)
This is
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).
If you really think that, that casts a serious doubt on your
programming expertise.
additional memory requirements of std::vector?
Unlike you, I have actually *measured* in practice the memory usage of
std::vector vs. std::list.
??? only in a cherry-picked case.
Look who's talking. *You* choose to cherry-pick only the cases where
std::list happens to consume less memory, and claim that these cases
demonstrate the clear superiority of std::list over std::vector.
But as long as anyone makes the absurd, blanket statement that using a
vector is always the right solution
Could you please quote me from the post where I said that using a
vector is *always* the right solution? Or anyone else, for that matter.
Well, how about the "Unlike you, I have actually *measured* in practice
the memory usage of std::vector vs. std::list" part, referring to your
argument that std::vector always wins?
There you go again with the "always wins". You failed to quote me
saying "always wins" because I have not written that. That's entirely in
your imagination.
Your claim seems to be that std::list is superior to std::vector
because std::list consumes less memory. It's easy to demonstrate that
this is a false statement in many, if not even most cases. That's
exactly what I did. I never said that "std::vector always wins".
std::deque is a practical demonstration of why std::list is not the
best choice.
Sorry to confuse you with facts, but std::deque suffers the same
limitations as std::vector, in terms of the complexity of insertion or
deletion in the middle of the container, as well as the same memory
usage issue.
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.
Is that *really* your best argument? It's just ridiculous.
"std::list is the best solution in this case. It's the fastest."
"No it isn't. std::deque is way faster."
"Don't change the topic."
Ooh, you got me. You are right. std::list is indeed the best solution.
Your argument is flawless. std::deque is clearly a poor choice because
it "changes the topic". You clearly win this argument. Now we will all
have to praise your programming expertise and argumentation skills.
(Just be honest and confess that it didn't even cross your mind that
std::deque might, in fact, be faster than std::list, and that's why you
didn't even think of suggesting it in the first place. Of course at this
point expecting any honesty from you is rather unrealistic.)
Your original argument was that
std::list is the fastest (if you suffer from dementia, please refer back
to your own posts). Clearly that's not true.
Clearly it was true, /in OP's original use case/. Nothing you've said
disputes it.
I proved with an actual program how std::deque is faster than
std::list in the the original use case. You haven't disproved that. Your
*only* (meta-)argument has been that it "changes topic".
"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.
Besides, as I said, inserting and deleting from the middle of a list
is O(n).
No, it's not. See 23.2.2.3:
Complexity: Insertion of a single element into a list takes constant
time and exactly one call to the copy constructor of T.
???
Complexity: Erasing a single element is a constant time operation with
a single call to the destructor of T.
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.
std::list changes the place where the O(n) behavior happens. With
std::vector getting an iterator to the mid element is O(1) but removing
it (while preserving the ordering of the other elements) is O(n). In
std::list getting the mid element is O(n) and removing it is O(1).
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
latter part of the operation, ignoring the first part. That's why you
can't write the function I requested, so that its execution time will be
O(1).
There are even more practical situations where O(n) random access of
lists becomes an issue. For example if you would want to write a
function which splits a list into two equal parts: You have to get to
the middle before you can splice it. The splicing itself being O(1) is
of little help here.
Being able to remove any element in constant time (assuming you
*already* have an iterator pointing to it) is actually less useful in
practice because of the lack of constant-time random access. There
aren't that many situations where you can truely benefit from the
feature in practice.
No qualification about inserting into/deleting from the beginning, the
end, or into the middle. It's always constant. Sorry to confuse you with
facts.
Please show me some actual code. Write the function I asked. That will
convince me.
But of course you won't do that.
If you want to prove me wrong, give the function which takes a
std::list and removes the mid element faster than O(n).
list.erase(q);
Sorry, that doesn't compile.