about new and delete

[Juha Nieminen]

Very funny. You're a real comedian, you should be writing for SNL.

You've got your blinders on, and can't see all the additional memory
std::vector allocates, in order to reserve room for the growth of a
vector. There are plenty of situations where std::vector uses more
memory than std::list would, with the same number of elements.

Your blanket, absolute statement is evidence that you do not fully
understand the subject matter at hand.

Unlike you, I actually *measure* things, rather than relying to
theoretical handwaving.

For example, I measured the memory usage of a program which does this:

std::vector<int> v;
for(int i = 0; i < 1000000; ++i) v.push_back(i);

The amount of memory taken by the program was 4.77 MB. Then I changed
the std::vector to std::list and ran the test again. The memory taken by
the program was 16 MB.

I am merely pointing out situations where std::list is a better choice,
in response to illogical claims about the superiority of std::vector in
all possible situations.

Exactly who claimed that std::vector is superior in all possible
situations? The only thing that I, or anyone else I have seen, have
claimed is that std::vector is superior in *this* particular situation.

I most certainly disagreed. You're in error.

Well, as I already mentioned in another post, I don't believe you
really think that traversing a vector is not simpler than traversing a
list, but you are only claiming it for the sake of argument and because
you can't retreat from your position anymore.

Using iterators might be more *generic*, but that's not the same thing
as being *simpler*. Those are two radically different things. Your only
argument pro using iterators to traverse the container is that it's more
generic.

In this particular case the original poster will benefit from
simplicity more than from genericity.

You have me confused with someone else. I am not the one who began the
argument with absolute claims of the kind that I quoted up top.

You started the argument that std::list is some kind of pure win in
this situation. I disagree. Your arguments on why std::list is better
are flawed.

When measuring all possible factors in this particular situation,
std::deque comes out as a clear winner in all counts (including speed,
which was your original argument, and std::deque wins by a huge margin).
However, you didn't even consider std::deque as an alternative. My guess
is that you don't even understand how std::deque works, which is why it
didn't occur to you to suggest using it.

Clearly std::list is *not* the best solution in this particular situation.

(Of course the point is moot anyways. If the task is to ask the user
some numbers and then do something with them, it doesn't really matter
which container you use.)

Wrong, as usual. Unlike other participants of this thread, I never made
an absolute statement that one container always has better results in
all possible situations.

And who might these "other participants" be? I don't remember seeing
anybody claiming that std::vector (or any other container) is best in
*all possible situations*. The only claim has been that std::vector is
better in *this particular situation*. Nobody has said anything about
all possible situations (on the contrary, other hypothetical situations
where std::vector might not be the best have been addresses in this
thread more than once, by other people than just yourself).

I merely pointed out that within the confines
of OP's test case, std::list comes out on top.

Which is clearly a wrong statement. std::deque beats your std::list
hands down in all possible categories ("within the confines of the OP's
test case", and far beyond).

Now, be honest and confess the true reason why you didn't suggest
using std::deque, and instead suggested using std::list. (My guess: The
possibility didn't even cross your mind.)

If the OP was trying to
do something else, such as reading the input data from a file, where the
potential number of elements might be quite large; or if the OP wanted
to sort the elements, for example, that would've called for a different
approach.

Just out of curiosity: Why wouldn't std::list be feasible for sorting
the elements? std::list does have a O(n log n) sorting function. (And if
the elements were very large and heavy to copy, then it could even beat
std::sort applied to a std::vector.)

 

[Juha Nieminen]

Oh, I see now -- the OP was entering tens of thousands of numbers on
std::cin. That explains all the hubbub.

And you refuse to acknowledge that you don't need tens of thousands of
numbers for std::vector to become faster than std::list. You just need
something like 30.

Besides, if extreme speed is of essence, std::deque would be the right
choice, not std::list (as I demonstrated), thus your solution is wrong.

Moreover, if the input is expected to have something like 10 or 20
numbers at most, std::vector would beat both if you use a proper
reserve() call. With just some "reserve(20)" I don't think std::vector
would ever become slower than std::list. (std::deque might beat it by a
small margin after more than 20 elements are pushed back.)

It becomes theoretical as soon as you leave the boundaries of the
original scenario.

Your requirement for extreme speed in the original scenario is
completely theoretical. What good do a few clock cycles do if the user
is entering numbers by hand?

… the additional overhead of reserving memory for unused elements of
std::vector, the impact from all the additional invocations of copy
constructors and destructors, as the container grows in size.

Yes, completely relevant in the original scenario.

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. 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).

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).

Because you wouldn't use a std::list when random access is required.

So you are implying that the original poster required insertion in the
middle of the container?

Are you talking about yourself, and your blissful ignorance of the
additional memory requirements of std::vector?

Unlike you, I have actually *measured* in practice the memory usage of
std::vector vs. std::list.

Because you forgot that it's the vector fan club who began adamantly
claiming that std::vector solves world hunger, brings world peace, and
is a cure for the common cold.

No, it's you who is claiming that some people here are doing that,
even though they aren't. All they did was say that std::vector is the
best choice in *this particular case*.

(Even if we start nitpicking about efficiency, like you did, then
std::list would *not* be the correct answer, as std::deque clearly beats
it. Thus your argument is incorrect even in that case.)

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.

You seem to have some kind of obsession about that subject.

Would you mind looking back through the thread and see who was the first
one to bring up std::deque?

I'll wait.

The topic was "what is the best data container for this particular
situation". Exactly how is suggesting std::deque "changing the subject"?

Hey, I could nitpick about *you* changing the topic. Who was the first
one to bring up inserting in the middle of a container? I'll wait.

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. 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.

So now that you have been proven wrong, you change the subject by
trying coming up with some argument about insertion in the middle. If
that's not a change in topic, I don't know what is.

Besides, as I said, inserting and deleting from the middle of a list
is O(n). If you want to prove me wrong, give the function which takes a
std::list and removes the mid element faster than O(n).

 

[Juha Nieminen]

To you, may be not. But in latency-sensitive environments, it most
certainly does.

And std::list would be the worst possible choice in that case.

No, not "clearly". There are a number of situations where the
contortions one must go through, in order to use a vector as the
underlying container, more than negate any inherent vector-specific
optimizations.

And what might those be? And how are they relevant to the original post?

 

[Jerry Coffin]

[ ... ]

But, by the same measuring stick you demand others abide by, if
there's /any/ doubt as to the validity of the benchmark, the
results are null and void. You stated this position yourself. This
has to be a world record for backpedaling.

Nonsense! You're trying to conflate two completely separate issues.
Issue number 1: you must know _what_ you're measuring. Without this,
your measurement is devoid of meaning.

Issue number 2: you'd _like_ what you measure to be as similar to a
real workload as possible. OTOH, it's virtually never possible to
measure a real workload without at least some modification -- so you
get as close as you reasonably can, and (by strong preference) have
at least some idea of how the two differ.

The first is necessity. The second is preference.

 

[Joshua Maurice]

To you, may be not. But in latency-sensitive environments, it most certainly
does.

But just keep thinking that it doesn't matter, don't let me discourage you
otherwise. I consider stuff like that to be excellent job security.

You are the one picking and choosing data to fit your arguments, often
in an inconsistent matter. If it's all about a user entering numbers
at a terminal, there is no latency to speak of. So, try to be
consistent: either we're discussing the OP's use case exactly, as you
sometimes claim, or we're discussing general practice, as you just
claimed.

If the program is not being used at an interactive terminal, such as
piping the output of one program to it, and the number of ints is ~30
or more, then std::vector will noticeably outperform.

I don't know of any real use cases which require std::list over
std::vector because of this "magical latency". std::list only
outperforms std::vector by a unmeasurable amount when the number of
ints is roughly < 30. No performance matters when you're doing 30
ints, not even transferring over a shitty modem. However, as soon as
the use case morphs ever so slightly, like 30 ints or more, then
std::vector wins, as repeatedly mentioned.

Only in some situations involving a large number of elements. In others, a
std::vector cannot be used for other reasons, so it's not even an option.

Again, stay consistent. Either we're addressing the user's original
use case on performance grounds, or we're talking about general
practice. Frankly, your arguments are inane. "Oh, it doesn't fit this
use case which I'm keeping in my bag, so we should just use
std::list". std::vector is better for the OP's use case. Give me
another use case, and we can talk about whether std::list or
std::vector is better.

If one places code reusability at a premium, one should be using iterators,
rather than any std::vector-specific methods, or overloads. As I showed,
doing so allows one to substitute the underlying implementation, without
changing the code.

A completely different issue.

It is inane to say "Oh, but your algorithm must be as general as
possible". There is little to nothing to be gained by templatizing the
algorithm in this case. I cannot think of a situation where I would
take his original algorithm and replace vector with list, thus there
is no value in templatizing it, but there is a cost associated with
templatizing it, so I will not.

Code reusability is not the same thing as ease of refactoring, though
related. Sometimes, one writes these things called "libraries" or
"stand alone program utilities" (aka the unix way of a bunch of stand
alone programs like cat, sed, grep, etc., and everything is a file).
His program might be one such thing. One could reuse his program
without ever having to recompile it, and if it's using list over
vector, it will be much slower for anything but the trivial small
usecases, and it will never be measurably faster.

Not just "interpretation". I showed the actual numbers.

Please consider actually reading what others post. I said "your
interpretation of his use case is a small number of inserts". Measured
numbers of execution time of programs does not come into it. Your
reply is a non sequitur.

Sorry, I measured it. Just because some may don't think twice about pissing
away a small amount of resources, that's not a valid reason to do so in my
book.

Thank you for snipping the pre-emptive reply I gave. I shall reproduce
it here.

This was, and is, the source of contention for one issue, that you
claim performance is a reason to use list, but that's only true for a
very small number of inserts, your interpretation of his use case.
However, in this use case, the performance bonus of std::list over
std::vector is not measurable. Thus your argument is "Use std::list
because it performs faster in an entirely unmeasurable way in your use
case." (Note that I said "unmeasurable in his use case". If you change
it to a micro-benchmark like you did, then yes you can measure it. You
cannot measure the difference for his program for a small input set.
You can however measure the difference for a larger input set, in
which case std::vector clearly wins.)

You did not measure the difference in his use case. For his use case,
the difference in speed between std::list and std::vector is entirely
unmeasurable for ~10 elements. The various other costs of process
spawning, program start up and death, waiting for the user to type
things, etc., will entirely dwarf the time spent in list vs vector.
You cannot accurately measure it. However, for larger inputs, the
difference is measurable, and std::vector wins. You really need to go
review Big O analysis of algorithms, and the justifications behind it.
Do not optimize to the small case, as the small case's performance
does not matter. Instead, optimize to the asymptotic case, e.g.: the
case with input roughly > 30. This is commonly accepted standard
programming procedure.

No, not "clearly". There are a number of situations where the
contortions one must go through, in order to use a vector as the underlying
container, more than negate any inherent vector-specific optimizations.

Sorry, facts disagree.

You sir are an idiot or a troll. I shall wash my hands of this thread,
and of you forever.

Good day.

 

[SG]

Hahahahahaha.

std::list<obj> theList;

// …

std::list<obj>::iterator p;

// …

theList.erase(p);  // Warning, O(n)!!!!!

Very funny.


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.

Who said something about "having a member"?

Thank you for playing.

*yawn*

You simply phrased your question badly, Sam. It's not obvious if an
iterator to the middle element is already known. I do think you're
smart enough to grok what was going on. Juha even explained how he
interpreted the question by saying "write a function which takes a
std::list as parameter and removes the element at the exact middle
faster than O(n)". But instead of saying something like

"Yes, O(n) if you don't know the iterator. But I was assuming
that it is known. In that case std::list makes a difference."

you try to make it look like you're the only sane person here.
-1 for weak communication skills.

Cheers,
SG

 

[Richard Herring]

Whatever it is, I wouldn't consider it something to be ignored.

cf. "you need a magnifying glass to see it."

Always producing the best possible code is a good habit to have.

Indeed, and "best" is about more than speed. If you subsequently
"substitute the underlying implementation, without changing the code" by
changing the container type, the hidden assumption that end() is
invariant may come back to bite you.

As I mentioned elsewhere, in certain situations, a difference of a few
milliseconds in latency of production code means whether you come out
in the black, or in the red, at the end of the day.

In that case you should also be worrying about the relative cost of
_incrementing_ different kinds of iterator. How does an increment
compare with an indirection on your target architecture? ;-)

And, as I mentioned elsewhere, you should really be much more concerned
about maximizing locality of reference. If the next element of your
sequence isn't already in the cache, all those micro-savings on iterator
manipulation are pointless.

But, I suppose, if you're not doing anything particularly important,
and you don't care, you shouldn't.

'We should forget about small efficiencies, say about 97% of the time:
premature optimization is the root of all evil.'

 

[Juha Nieminen]

Where existing iterators to container members must remain valid after an
insert (or a delete) from the container.

Duh.


That's going to be your homework assignment for today.

I don't need to do that "homework" because you yourself answered the
question above, by giving an imaginary example which is certainly not
relevant to the original post. Thus the answer is "they are *not* relevant".

 

[Juha Nieminen]

by cherry picking bits from all over place, and
discarding all other, inconvenient facts.

I'm wondering why you are doing this. You are intentionally writing
inflammatory posts and distorting what other people write, and accusing
others of doing what you yourself are doing, probably on purpose. But
why? Does this amuse you? Why are you trolling so much?

For example, *you* are the one who is conveniently cherry-picking
arguments depending on what is it that you want to oppose. When it's
most convenient, you argue that we should only take into account the
original case (a user entering a dozen values by hand on a text
console), but when that's not convenient to your argument, you switch to
a situation which does not fit the original case (eg. inserting in the
middle of a container). When someone shows you how std::vector is faster
than std::list, you dismiss the result because it's not strictly within
the (implied) original testcase. When someone shows you how std::deque
is faster than std::list in the original setting, you now dismiss it
because of a feature which is *not* relevant to the original testcase
(eg. inserting in the middle). You always choose (ie. "cherry-pick")
whatever argument will work against what someone wrote and conveniently
ignore the other one, wildly jumping between requiring the measurements
to be performed on the original testcase and not requiring it, whatever
suits the best your argument.

And then you accuse *others* of exactly the thing you are doing, ie.
cherry-picking, changing the topic and choosing only convenient features
and ignoring the inconvenient ones. I'm quite convinced that you are
doing that on purpose and with full knowledge, just for the sake of
argument and trolling.

But why? Does it amuse you so much?

 

[Juha Nieminen]

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.

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.

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.

… 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.

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".

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.)

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.

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.

list.erase(q);

Sorry, that doesn't compile.

 

[Juha Nieminen]

Very interesting. So a situation where one needs all existing iterators
to remain valid, after an element gets added to the container, are
"imaginary", and will never happen in practice. Gee, why would you
*possibly* want something like that?

Well, that's a comforting thought.

Exactly as imaginary as someone needing 10 thousand elements or random
access in constant time.

You seem to be very eager to dismiss features as "theoretical" when it
best suits your argument.

 

[Juha Nieminen]

Not according to you, it is.

No. According to me it's undefined behavior.

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".

Well, just for shits and giggles:

theList.push_front(obj());

p=theList.front();

// … (for a smaller value of …)

theList.erase(p); // Warning, O(n), according to Juha!!!!!

Happy now?

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
demonstrate that.

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.

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.

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.

I'll write it as soon as I lose the ability to write entire applications
correctly.

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).

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.

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.

"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.

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.

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
list.

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
constructors:

YourList::YourList(size_type n, const value_type& value);

template<typename InputIterator>
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.

 

[Scooser]

Ok Sam. Let me try to spell this out and see where you disagree. So,
here are my premises and deductions:

2-
In the OP's use case, Sam took it mean a small number of ints, ~10.
Sam did correctly show that inserting ~10 ints into a std::list is
faster than std::vector for whatever platform, compiler, etc., he was
using.

Seems as if Sam did some sort of benchmark optimisation here by first
using some "optimal" number of int's and by second ignoring the
additional possibilities the vector has. When addressing the OP's use
case - assuming a relative low number of int's, let's say around 10 as
Sam did - it is no cheap trick to use vectors reserve method. Btw. in
the original code the user was explicitly asked how many numbers there
are and so the size was known a priori.

Using this approach the vector approach outperforms the list version
by the factor of 9 on my system. But even without the additional
reserver there is only a small gap - 3 to 5 int's - were the list is
faster.