On 10/8/2019 at 10:37 AM, Dawoodoz said:Today we have huge but slow memory with fast computation and using a linked list as a default container is like a bad joke about cache misses.
I thought std::vector was the standard container back in the day and was usually an array behind the scenes. While std::list was for those who specifically wanted the features of a linked list.
I'll admit I only ever used C++ as a student or a hobbyist though so :shrug:
On 10/9/2019 at 1:58 AM, Shaarigan said:I think the standard library is outdated too but in my opinion for reasons like code style, conventions and the heavy nesting of templates
I think the interface used by the standard library is quite solid for it's stated purpose: It provides a general purpose library of functionality. It does that quite well.
The deep templates-of-templates-of-templates that some implementations use is an implementation detail. There are implementations like STLPort and EASTL that do not follow that detail.
Further, many implementations use those deep nestings to take advantage of a feature of C++ not present in the other modern languages: Extreme levels of eliding optimizations. The biggest reason you don't get introspection features in C++, features like reflection and properties, is because the c++ language was designed to strip out EVERYTHING that wasn't used. In order to provide many of those modern features the original code must be available, especially when implemented as templates or otherwise work with replaceable types.
When dealing with the C++ standard library and if you debug in to nested type after nested type just to ultimately resolve down to a single function call or a single lookup, if you look it up in the optimized release build you typically find it vanishes completely, the nesting doesn't exist, it is replaced only with the function call or the lookup directly. This would fail terribly with many modern features that would allow runtime systems to swap out or modify behavior of those intermediate layers.
Regarding the choices on data types, all data types have tradeoffs. Linked lists are no different.
By far the biggest advantage of linked lists (and container types that use them) benefit from stability of objects. You can continue to use pointers/references to objects without worrying that the objects will move as the container is modified. There are drawbacks, such as cache inefficiencies and overhead for maintaining the links, but those can be reduced through implementation details like using memory pools and indexed chains of nodes, and if you are willing to work with special case code instead of the general purpose standard library, in some cases it can be eliminated.
The C++ vector, an implementation of a dynamic array, should generally be your data type of choice. This shouldn't be a surprise to anyone who has studied computer science or computer architecture, as the linear format has extremely low overhead and very high predictability for the cache. However, it comes with drawbacks, perhaps the most significant is the difficulty with resizing when elements are added, and the space wasted when elements are removed.
And note that there are data structures designed for the behavior in between, in the C++ standard library this is the deque class. While implementations vary, It is frequently implemented as a combination of the two, a linked list of dynamic arrays. The array is divided up into pages. Adding and removing items tends to modify only that page. When a new page is added or one is removed, they are removed from the linked list of pages. Advancing beyond the boundaries of a page will --- behind the scenes --- move the iterator to the adjoining page so you can continue immediately. It gets many benefits from cache friendliness and reduced overhead from the dynamic array parts, and gains significant stability (though not absolute stability) through the linked object parts.
And if those built in types from the standard library aren't enough for you, you are free to implement your own custom functionality rather than relying on the general purpose functionality.
In games I generally try to look for the standard library first, and only when there is an actual reason I turn to non-standard container types and non-standard algorithm implementations. The standard library is good and full featured in the general case, but the library creators knew even at the outset that special cases meant general purpose would be a bad fit. General purpose libraries are not universally good.
But the general purpose libraries are generally good, and in most general programming you should use them when they fit.
