Is your point that programmers in other languages automatically make good choices about data structures and memory usage? Because that seems, respectfully, to be a dumb point. They do not.
I agree its a problem with C++, but IMO it is an inevitable consequence of its strengths: namely that it is regularly used across a very wide range of domains than other languages. I've sen it used on 16-bit microcontrollers, where templates and exceptions were considered harmful, and in large applications, where those features were considered essential.
Perhaps I'm being dumb, but doesn't std::list<T> already do exactly this?
From SGI's STL docs:
"A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle"
As others have said - yes, as long as you keep the iterator not the object itself. e.g. from T itself you cannot find where it was stored, so with std::list<something>, and then only from something you can't find where it is (you can have to look for it in the list).
The idiomatic way to access and manipulate STL data structures is through iterators. In this case, an iterator for a std::list is basically a pointer/reference to the person container in the article, so if you're referring to the list objects via their iterators there's no need for O(n) list traversal.
It's also not a problem in C++ if you don't care. Just because C++ gives you the means to enforce encapsulation doesn't mean you have to. And, as I said below, when your goal is performance and you need to break abstractions, it makes sense not to enforce encapsulation.
He never mentioned other languages, so no, I don't think that was his point. I think his point was that C++ makes it hard to make good choices about C++.
I'm saying Java programmers make inappropriate data structure choices about Java programs, and boy do Ruby programmers ever make bad decisions in Ruby.
I got that. Not very nice to say his point was dumb because you wanted to make a different one, though. I think we can all agree that C++ is annoying and leave it at that.
To an extent, they're forced to - when all you have are dynamic arrays and hashtables (I'm thinking of python here), it's hard to go very far wrong. (Isn't it? Am I being naive?)
Naive? I do not know, but your logic surely is :-)
Consider the similar "if you have only one kind of string, it's hard to go wrong". If you need Unicode, but your only type of string is ISO-8859-1, or if you need to cramp many strings in memory, but your only string class uses UTF-32 internally, it's almost unavoidable that you go wrong.
The advantage of having only few data structures is that the developers of the system have only few places where they have to spend effort on optimization. So if, like Python, your platform is popular, chances are that those few basic structures have been optimized to death.
That does not necessarily make them optimal for every use case, though. The big advantage of C++ is that, if the need arises, you can (see below) make a special-case data structure that beats even the most optimized general-purpose one.
Of course, that 'can' is relative. It is really hard to make a robust special-case data structure.
From yesterday's bug hunting session: sets (okay, not exactly hash tables) are not ordered data types, so do not use a set for intermediate values when order matters. (My fault - I'm just pointing out that it's not that hard to get Python wrong either.)
It is rather hard (though I believe not impossible) to find a use case where dynamic arrays and hashtables are not within a constant factor of the best possible data structure.
