4 ms·

This is not a linked list, it's a dynamic array. http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays http://en.wikipedia.org/wiki/Linked_l

• tptacek 16y ago
  That's a pedantic comment to make, given that Python doesn't care about the difference. Ruby calls the same thing an "Array".
  • omnigoat 16y ago
    Well you've clearly never had to worry about memory paging and the cost of indirection, like I have (actually from memory I think you must have at some point?). The difference is real and significant. Try writing a particle system using a linked-list over a vector, the speed difference will be crippling. I really feel that most of the hatred for C++ stems from people not understanding why such complexity exists in the language.
    • nostrademons 16y ago
      The point is that you don't have to worry about the difference in Python, because you don't use Python for the parts where performance matters. If you've got a million instances in your collection, you probably want to write your data structure and key traversal functions in C. Python has a sequence protocol, so you can easily wrap it to operate on it just like a native list (which is really a vector), but the operations that need to be fast should be in heavily-optimized C. In every system I've written, there's been a large chunk of code that runs on startup, or implements a feature that only 1% of users care about, or performs setup for one of these expensive operations but itself only touches a few data items. This usually consumes about 90% of the code but only about 1% of the runtime. Heck, probably 50% of my code never makes it to production at all, because it's exploratory or analysis code that's intended to define the problem, not implement the solution. Why not write it in a language that makes you really productive, and spend the time saved to optimize the hell out of the remaining 10%?
    • tptacek 16y ago
      The performance difference between a vector and a list has nothing at all to do with what we're talking about. Stop picking random things in the discussion to nerd out about. We get it, you're awesome. The point is that in Python the distinction isn't made.
  • JeremyBanks 16y ago
    Python has a linked list type (collections.deque), but their standard list type is a dynamic array/vector and so has entirely different performance characteristics. Treating it as a linked list could screw you. I don't think that's pedantic at all.
    • nostrademons 16y ago
      ...which is why both the Python and C++ examples used a vector. The post I was replying to said "If I want a linked list or any other common data structure in C++". The discussion is about how easy it is to use basic data types, not about what those data types are.
  • marte 16y ago
    No, it does. There's a type in Python called "deque" that more closely resembles the performance characteristics of a linked list. I agree that this is not the main point of the discussion, though.