I had to fight the urge to stop there too; it's also more idiomatic and probably both more economic and performant to use a vector in this situation; "lists" in C++, at least on the projects I worked on, tended to be a code smell.
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.
I've been programming in C++ for about ten years, first as a hobbyist, then as a student and finally professionally and it is extremely rare that I've seen an std::list needed over an std::vector or std::deque.
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.
It was a bit of a shock in 1998 when I first started writing professional C++ to realize that lists and hash tables were unidiomatic in (what was then) STL. I was a lists-and-hash-tables C programmer at the time.
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.
> red-black trees...are often a better option than hash tables
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 with most data structure questions, there are no hard-and-fast rules
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)
C++11 has hash tables now. Check out unordered_set and unordered_map if you really require a container backed by them. I agree with you on the RB trees though.
Edit: I should add (and you probably know) that std::set and std::map are typically RB Tree based containers.
STLport, IIRC, always had them. If you picked a specific STL instead of using the c++stdlib bundled with your compiler, you could generally always have hash tables with iterator semantics. But <map> was usually the right choice; even apart from worst-case behavior, you'd always end up needing not just to look things up, but to traverse the collection.
That's true, I remember using <hash_map> back in 2003 or so for something, but since then reverted back to just using <map> and the vanilla C++ stdlib which has always met my requirements and performance needs.
Though, nowadays, I sometimes find myself using tbb::concurrent_unordered_map and tbb::concurrent_hash_map, not to mention tbb::concurrent_queue.
To the first part: I guess it's true that if you see someone using a STL list for "just a bucket of stuff" that this is bad form. But they're general purpose doubly-linked lists and absolutely should be there in the API for situations where they're needed (i.e. something where order is important, the size is likely to be large, and you need to mutate in the middle).
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.
I'm not saying C++ shouldn't have a doubly linked list. I'm saying that C programmers are trained to use linked lists. They are the first variable-length containers most programmers come into contact with and so C programmers tend to be imprinted on them like ducklings. Linked lists are a poor general purpose container.
I've been putting myself through C++ "boot camp". I got a copy of Bjarne's "The C++ Programming Language" and I'm doing every exercise. I'm up to 302 at last count, and only a couple more chapters to go.
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.
I recently assigned myself a project to learn C++ too, mainly in the interest of learning an entirely different kind of language (I only know python very well) but also to scratch a long pending itch of writing a few simple games and doing some graphics related work.
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).
I recommend Stroustroup's book as it really leaves no area unexplored. It is better to read it after having read some other material, as you have. I would wait for the 4th edition, though, which covers C++11.
It's really tough to say, I've been working on it off and on for a few months. But I didn't really keep track of the time spent. I'll probably put it up on github when finished and see if anyone wants to rip apart my solutions and/or contribute better ones.
As I see it, the only use case where linked lists are superior to other types of lists, like, perhaps, ArrayList in java or vector/deque in C++, is if the following conditions are met:
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.
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.