I think this is a very big problem with C++: most of the funnel of new developers for C++ are C programmers, and transliterating C idioms to C++ (and, worse, the C++ standard library) usually produces pessimal C++ code.

The general rules I follow are roughly: If the collection only grows one way and has lots of random access (or even lots of iterating over elements... linked lists aren't exactly the most cache friendly data structures), then use a vector. If the collection needs to grow from both ends and has lots of random access, then use a deque. Only if neither of those are suitable, should a list be considered and the main reason, IMHO, to use an std::list is if inserting or removing elements in the middle of the list is a common operation. But in the case of removing, if copying is cheap and order does not matter, then a vector may still be better and removal can be done by swapping the element to remove with the last element and then removing the last element. In general, if ordering is not important, a std::vector is probably a good choice.

So really, I see the use case for std::list as a real but very rare one.

I moved from a heavy C++ role to a pure C role in 2002 and came to realize that this is something that C++ got right. It's not that C++ has crappy lists; it's that lists are usually a crappy solution. Not only that, but red-black trees, as long as you're not the person who has to implement and test them, are often a better option than hash tables.

I wrote a simple "vector.c" for our project, and (I never tire of bringing this up) ported STLport's red-black tree <map> template to C, specialized on void*. I still use them on C projects.

Any time I feel myself reaching for a dequeueuqeque, I recheck my assumptions and convince myself I'm in the wrong direction.

Why is this?

Trees have O(n*log(n)) element lookup time as opposed to O(1) for hashtable (assuming table size is allocated appropriately or grows with the data, and you have an effective hash function). If data structure accesses are on the hot path, a hash table is much faster.

Many times, when you need ordered data, you can actually get away with using either a heap or a sorted list, rather than a red-black tree. Both of these are much easier to implement than red-black trees, and have the advantage of no extra per-node storage for child pointers. Which can make a real difference in memory usage if your objects are very small, and a real time difference if it means the difference between CPU cache/main memory or main memory/swap.

Red-black trees can be good if you can easily write a comparator for your objects but not a hash, really need capabilities like quickly determining subranges, aren't on a performance-critical path, or aren't concerned about CPU efficiency because the available hardware greatly exceeds your problem's requirements.

As with most data structure questions, there are no hard-and-fast rules; the data structure you choose is going to depend on your particular situation. I personally probably use each of the four solutions I mentioned (hashtable, red-black tree, heap, sorted list) less than fifty percent of the time.

As in everything in programming, there are always going to be trade-offs. At least C++11 gives you options: <map> is generally an RB Tree, <unordered_map> is generally a hash table.

Trees have O(n log(n)) element lookup time as opposed to O(1) for hashtable

According to [1], <map> (And <set> and <multimap> and <multiset>) lookups have O(log n) complexity, while <unordered_map> lookups have O(1) amortized and O(n) worst-case complexity.

Again, lots of trade-offs to consider, which is why the C++11 stdlib, IMHO, does a great job, whereas other popular languages which provide "one true data structure" of each type are really not that great without third party libraries, as they don't give you the option to choose the right data structure for the job. Eg, in python, if you need a dict, you use a dict without thinking about if its implemented as a tree or a hash table or a heap or a... similarly, if you need a list, you use a list without worrying if its a linked list, a skip list, a dynamic array, something else entirely. Usually this is a good thing - you can just get on with your life, but sometimes you really do want to make sure that operation X will be O(1) or O(log n) or whatever, and if the built-in data structure does not guarantee this, you must use third party libraries. At least in C++11, the stdlib gives you some options (and usually makes it clear what the complexity of operations are). I really like that about C++11.

For a lot of languages, "the right data structure for the right job" means a choice between lists, vectors, dictionaries (however they are implemented), sets etc. In reality, that's only the first tier - once you decide that lists are the right tool, you still need to decide what kind of list, and a lot of languages don't give you that choice by default. (Though to be fair, a lot of people don't need that choice - premature optimization and all that)

[1] http://en.cppreference.com/w/cpp/container

Edit: I should add (and you probably know) that std::set and std::map are typically RB Tree based containers.

Though, nowadays, I sometimes find myself using tbb::concurrent_unordered_map and tbb::concurrent_hash_map, not to mention tbb::concurrent_queue.

The second point I think is just isomorphic to "breadth is good". A Ruby or Python programmer coming to C++ is going to avoid a lot of the mistakes of the C programmer, but will likewise miss a lot of the core ideas and generate equally pessimal code, just for different reasons.

It's been grueling, but very well worth the time. It helps me avoid a lot of mistakes I would have made had I just jumped in from C and C#.

Unfortunately, the 4th edition (which presumably covers C++11) doesn't come out until Feb.

What I have found, while going through the C++ primer by Stanley Lippman and Barbara Moo (and having read most of accelerated C++ earlier) is that I have not so far seen anything that I really dislike.

Maybe this is because I am not really experienced and so cannot see the obivous pitfalls, or maybe those things will come in later in the book. But so far I see a language which I can use in many places.

Also how is Stroustroup's book for someone who finishes the C++ primer (which goes over just the basics).

1: you care about ordering - often you don't care about ordering and in that case, there is no need for a linked list because you can achieve O(1) insertion & removal then too: insertion can always be at the end, removal can be a "swap with end element, remove end element" operation.

2: inserting and/or removing from the middle of the list is a common operation, if it is not a common operation, then the added cost of doing so with a vector may still be outweighed by a vectors other advantages

3: you do not require random access - lists do not provide random access and lookup is O(n). At the expense of additional complexity in implementation and more memory overhead, you could reduce lookup to, OTOH, O(log n) by using a skip-list

4: you do not iterate through the list often - if you do, you are likely going to blow the cache and mess up prefetching due to poor cache locality. Iterating through an array-based data structure can be much faster in this case.

I would say that for a list to make sense, you MUST have 1 and 2 and probably should have 3. 4 is optional, but if true, should make you consider if there might not be a more suitable data structure. In my own personal experience, this is rare. In fact, in my own personal experience, usually, code either does not require 1 or requires 1 but not 2 - either way, lists are not the appropriate data structure in those cases.

1. Linked lists require extra per-node memory for pointers. Plain lists (vectors in C++) don't.

2. Linked lists have poor cache locality. Each item is in a different place.

3. Using Person* instead of Person for the list objects results in twice the number of objects. In C++ you have this choice; in many higher-level languages like Java, you don't; generic linked lists only support double-object way. (You could of course manually add pointer fields to your objects to obtain a single-object solution, but this defeats the purpose of write-once-run-with-any-element-type idea of a reusable container data structure library.)

4. You often only care about adding and removing from one or both ends. A vector or deque has O(1) removal in this case as well (assuming it's allocated with adequate space, or you don't care about transient CPU spikes due to reallocations early in your program's run, before it reaches its max size).

5. Large numbers of objects are more stressful on memory allocators and garbage collectors.

In C++ it seems everyone has completely different views.

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"

Not sure if this qualifies as not "breaking encapsulation" but it's as close as you're going to get.

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.

Admittedly, that constant may be fairly large.

EDIT: See for example Stroustrup's discussion on the matter at the 44th minute of this video : http://channel9.msdn.com/Events/GoingNative/GoingNative-2012...

On modern architectures, cache misses are performance killers, and a list is a cache-miss machine. Moving memory is cheaper than doing a linear search through a list. What used to be true 20 years ago isn't true anymore, let's stop using those lists already !

But in practice, the amortized time complexity will indeed usually be half of the worst-case scenario when removing elements from a vector.

f(n) being O(n) means: there's a N and an x such that, for all n > x, N*n > f(n). By this definition, O(n/2) is the same as O(n) is the same as O(n/42). You just choose a different N. But it's better form to write O(n).

The removal time for the second-last element is still O(1). There is no slightly higher here. O() does not count steps or cost or anything like that - it counts worst case or asymptotic complexity. O(1) means constant time/space/whatever-you-are-measuring complexity. Removing the last element of a non-empty vector always takes the same amount of time (since we are talking about time complexity in this case) no matter how many elements are in are in the vector. Similarly, removing the second-last element always takes the same number of steps regardless how many elements are in the vector (as long as there are at least 2) - still O(1).

That doesn't mean that they take equally long - the second-last element does indeed take longer to remove (by some constant factor), but complexity does not care about that, it only cares about the relative difference in respect to n (usually the size of the input) and the worst case (usually; you can also look up θ(..) and Ω(..) and others, but generally worst case is much more useful than best case, though sometimes average case is good to know too).

Note also that a O(n) algorithm may actually execute faster than a O(1) algorithm, at least, for small values of n. For example, finding an item in a hash table may be O(1), but finding an item in an array, O(n), may actually be a lot lot faster, eg, if the entire array fits into L2 cache. On the other hand, if the array is so big that it swaps to disk, the hash table's O(1) will really shine.

I think I'll tend to stick to C most of the time, thanks.

Even the C++ people probably can easily analyze and reason out the C implementation without much effort or dissent, apparently not so with C++.

Unfortunately, in the C implementation of anything beyond a trivial application with no large-scale data structures, the majority of the "reasoning" being done will revolve around basic data structure implementations! The very containers, memory allocation structures, and such that require virtually NO reasoning in the C++ implementation, because they are proven.

After you've implemented the same basic structures again, and again for the hundredth time in large-scale C programs, C++ is a breath of fresh air.

Unfortunately, many people approach C++ before they have many miles on their programming chassis; this is like handing an infant a revolver. Bad things are likely to happen.

This is not a problem with the revolver; it is a parenting issue. Don't let a junior programmer use a language requiring significant reasoning skills, before they have earned the right -- by developing those skills, repeatedly implementing the very structures they'll be accessing in the C++ implementation!

We wouldn't let a first-year civil engineering student develop a bridge design, without first gaining many, many years of experience developing -- and failing -- on much simpler designs. Why should we expect wide-spread success, allowing junior programmers access to a spectacularly powerful and complex programming tool?

Maybe you should read the rest of his article.

Actually, in the specific case of std::list<T>, T can be both unmovable and uncopyable. Instead of using push_back() and insert() to insert elements, you use emplace_back(), and emplace() to construct the elements in place.

Also, the compiler is pretty good about auto-generating move constructors when all the members of a class are safely movable, so classes you write will probably be movable without you needing to do anything.

They started ZeroMQ in 2007 (or even earlier? can't quickly find a reference). So, yes - some of the problems that they faced in ZeroMQ have been addressed years later (although the solution is not yet widely available). I believe this is a point FOR his conclusion that he should have used C, rather than a rebuttal.

I can completely understand why C++11 is not a usable solution for many people at this point.

The author was arguing that writing in C++/STL meant your code was necessarily less efficient than C; that just seems incorrect.

Edit: If you're referring to copying the person values when they're returned from the list: a reference is returned; the compiler will optimize that "pointer" away. Most C++ compilers can even do this when the value itself is returned and avoid the copy. My rule with C++ is that the compiler is stupid, but never where you expect. You need to optimize based on a profiler.

Before C++11, it was a problem that inserting an element into a std::list required a copy (that's the only place though - once in the list there are no more copies). C++11 adds move semantics and also std::list<T>::emplace(), which eliminate the need to copy.

  struct person { int age; };
  std::list<person> people;
  people.push_back(person());
  people.back().age = 42;

He could also use http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/usag... for exactly the "C" layout he wants.

I stopped reading your comment at "I stopped reading" too.

I've _never_ read an intelligent comment starting with "I stopped reading". These kind of comments always try to show how "clever" the commenter is, and how he doesn't tolerate fools, etc, while 90% of the time they miss the point.

Have you continued, you would have seen:

"Assume that the object to be contained in the list is non-Assignable as is the case with any non-trivial objects, for example those holding large memory buffers, file descriptors, handles etc. If the object is Assignable simple std::list<person> would do and there is no problem."

And even if you read the post _before_ he added the above clarification, if you didn't have the knee jerk reaction you could probably have seen that this (object being non assignable) could be a potential problem in your solution too.

However, his clarification, and your proviso are also invalid.

First, your proviso, that it's non-assignable -- his type was unusable; that it's non-assignable simply seemed to be an error. In C++ the default permissions for a class are private (not so in a struct, as I hinted at in my post, in fact, such is the only difference between a class and a struct in C++).

Now, onto his clarification:

The baked in assumption is that in a non-trivial C project that one would not be using a standard set of container abstractions as well. Such is generally not the case. See, for example, GList [1]. The replacement for a template based container in C++ is generally going to be a macro based container abstraction in C, whereas the replacement for a container of pointers in C++ is going to be a void * based generic container implementation (like GList) in C. Both sets of generic implementations are going to have broadly the same performance characteristics (specifically, they're going to have the same number of mallocs of about the same size).

In both languages, if one needs specific performance characteristics -- specifically if mallocs are so critical that they must be restricted as much as possible -- one will use a special purpose data structure. That however is a somewhat rare case for structs which are composed of non-POD types.

[1] http://developer.gnome.org/glib/2.33/glib-Doubly-Linked-List...

I say this as a C++ programmer.

It's an unnecessary time drain and I can't but help wonder how many man-hours a year are wasted by people learning all the intricacies of C++. (Heck, just check out this guy's FAQ on all the things you probably never knew about C++ http://www.parashift.com/c++-faq-lite/). I could almost memorize a list of x86 opcodes faster.

Complexity != powerful language. Clojure makes this point very well.

What really gets my goat is the minimal differences between 'struct' and 'class'. Why do we need both again? If you're going to allow structs to have member functions and such, then you should never have had a 'class' keyword to begin with. Ugh.

1) you re-implement the datastructure for every case (person). Which explains why you'd use a datastructure like a linked list, because anything else would be way too much work.

Since you're likely to search through a "Person" list by name, a linked list would be close to the worst possible option. Even an unsorted array would be better, even if only for practical "doesn't destroy the cache" reasons, unless you have massive numbers of weird inserts.

You see that a lot, in C programs. People using suboptimal datastructures, not because they don't see why it's suboptimal, not because they don't know how to create the optimal one, but because they don't want to tackle the complexity of rewriting a real datastructure for this specific case, and don't want to use macro-hell libraries.

2) you use macros to abstract over strings, and hope that your string expansions work correctly. At this point I would argue that it's actually more complex than the C++ solution.

Both of these options suck.

I would also argue that for these sorts of problems (anything involving business rules pertaining to database objects) you'd want to use a more high-level language, or just a straight-up database schema if you wish to guarantee correctness and constraints without coding for a week. I'd probably prefer python, but there's plenty of options.