(C++) std::list

 

std::list is an STL container implemented as a doubly-linked list.

 

std::list is suitable for constant-time random-access insertion and deletion at the cost of linear-time read and write.

 

 

 

 

 

Examples

 

• std::list example 1: basics

 

 

 

 

 

Advice

 

• Insertion operators, such as insert() and push_back() are often more efficient on a std::vector than on a std::list [1]
• A std::list is relatively expensive to traverse [2]
• A std::list usually has a four-word-per-element memory overhead [3]

 

 

 

 

 

References

 

1. Bjarne Stroustrup. The C++ Programming Language (4th edition). 2013. ISBN: 978-0-321-56384-2. Chapter 31.6. Advice. page 924: '[3] Insertion operators, such as insert() and push_back() are often more efficient on a vector than on a list'
2. Bjarne Stroustrup. The C++ Programming Language (4th edition). 2013. ISBN: 978-0-321-56384-2. Chapter 31.6. Advice. page 925: '[28] A list is relatively expensive to traverse'
3. Bjarne Stroustrup. The C++ Programming Language (4th edition). 2013. ISBN: 978-0-321-56384-2. Chapter 31.6. Advice. page 925: '[29] A list usually has a four-word-per-element memory overhead'