C++ High Performance

List and forward_list

The std::list is a doubly linked list, meaning that each element has one link to the next element and one link to its previous element. This makes it possible to iterate over the list both backwards and forwards. There is also a singly linked list named std::forward_list . The reason why you wouldn't always choose the doubly linked list over std::forward_list is because of the excessive memory occupied by the back pointers in the double linked list. So, if you don't need to traverse the list backwards, use std::forward_list. Another interesting feature of the forward list is that it's optimized for very short lists. When the list is empty, it only occupies one word, which makes it a good data structure for sparse data. ...