Should std::list be deprecated?

问题:

According to Bjarne Stroustrup's slides from his Going Native 2012 keynote, insertion and deletion in a std::list are terribly inefficient on modern hardware:

Vector beats list massively for insertion and deletion

If this is indeed true, what use cases are left for std::list? Shouldn't it be deprecated then?

回答1:

Vector and list solve different problems. List provides the guarantee that iterators never become invalidated as you insert and remove other elements. Vector doesn't make that guarantee.

Its not all about performance. So the answer is no. List should not be deprecated.

Edit Beyond this, C++ isn't designed to work solely on "modern hardware." It is intended to be useful across a much wider range of hardware than that. I'm a programmer in the financial industries and I use C++, but other domains such as embedded devices, programmable controllers, heart-lung machines and myriad others are just as important. The C++ language should not be designed solely with the needs of certain domains and the performance of certain classes of hardware in mind. Just because I might not use a list doesn't mean it should be deprecated from the language.

回答2:

Whether a vector outperforms a list or not also depends on the type of the elements. For example, for int elements vector is indeed very fast as most of the data fits inside the CPU cache and SIMD instructions can be used for the data copying. So the O(n) complexity of vector doesn't have much impact.

But what about larger data types, where copying doesn't translate to a stream operation, and instead data must be fetched from all over the place? Also, what about hardware that doesn't have large CPU caches and possibly also lacks SIMD instructions? C++ is used on much more than just modern desktop and workstation machines. Deprecating std::list is out of the question.

What Stroustrup is saying in that presentation is that before you pick std::list for your data, you should make sure that it's the right choice for your particular situation. In other words, benchmark and profile. It definitely doesn't say you should always pick std::vector.

回答3:

No, and especially not based on one particular graph. There are instances where list will perform better than vector. See: http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/

And that's ignoring the non-performance differences, as others have mentioned.

Bjarne's point in that talk wasn't that you shouldn't use list. It was that people make too many assumptions about list's performance that often turn out to be wrong. He was simply justifying the stance that vector should always be your default go-to container type unless you actually find a need for the performance or other semantic characteristics of lists.

回答4:

Of course not. std::list is a different data structure. Comparing different data structure is good indication of its properties, advantages or disadvantages. But each data structure has its advantage.

回答5:

Look at the both links below:

http://msdn.microsoft.com/en-us/library/802d66bt.aspx

http://msdn.microsoft.com/en-us/library/9xd04bzs.aspx

First read the first lines and then look at the following sections: Parameters, Remarks and Members - Constructors, Typedefs, Member Functions and Operators.

After reading all, you will find out the differences between list and vector and be able to compare them, and find out their pros and cons - advantages and disadvantages.

Who needs or likes the pros and advantages of the list more, then he/she uses list instead, and this is the reason why list should not be deprecated.

Also someone will stop using vector, and start using list instead, if he had problem with the cons and disadvantages of the vector, that the list doesn't have.

You will find out what member functions and operators both list and vector have in common, what member functions and operators vector has only, and what member functions and operators list has only.

I read these msdn pages in the member functions and operators sections, and I noticed that only the vector class supports the at member function and the [] operator, but in the other hand only the list class supports the push_front and pop_front member functions.

You will learn the limits you will have to face against when using vector only, and the limits you will have to face against when using list only. If you use vector, but it is missing something very important to you, but list doesn't, then you will consider to switch to use list instead vector, and vice versa (from list to vector).

There is no something perfect exists. No way that vector is better than list in everything. If it was true, then list was never exist in the C++ in all times history.

But there is list exists, then there must be some points that list is better than vector, if absolutely not in the graph you show us, then in other things.

Maybe many years ago, programmers that used vector only had difficulties and problems that they had to solve them, and they got the solution by inventing the list class and use it instead vector.

I don't really know, and maybe I wrong, but I wonder that the list class was invented after that the vector class was invented.

I will appreciate you guys, if you will tell me if I correct or wrong, and tell me the true fact about it.

If vector was not problematic in some points, then I don't think that list was ever invented.

By the way about that graph I mentioned, when I saw it in the first time, before I read what you said about it, I thought it shows the times that take to iterate through list and vector. I was surprised to read that you said that this is insertion and deletion times. I thought that insert and delete take much less time then iterating the whole collection.