CPSC 131: Data Structures in C++

Started by KK20, November 11, 2012, 05:53:22 pm

Previous topic - Next topic

KK20

I'm currently taking this class right now and am slowly not seeing why I need to know this stuff. This was brought up in a conversation within my Facebook group (Video Game Design Club).
Spoiler: ShowHide
Quote from: Melol vectors...my 131 teacher refuses to let me use those. They looked easier to use than linked lists and such with pointers.

Quote from: Person A131 has a purpose, which is to teach you about the most common data structures and their strengths and weaknesses. Off the top of my head, I believe you can use vector to implement all of them, but letting you do it that way would defeat the purpose of the class. In the real world though, vector is pretty much the uber-structure, because it's stored as an array. If your CPU has a pipeline (and pretty much all of them do), then locality of reference* beats the lower time complexity** of the other structures for certain operations almost every time.

* unless you do something stupid like make a vector of pointers, because then you're optimizing for cache misses.

** That's actually not entirely true, since big-O is supposed to take the hardware architecture into consideration, but most most of the time we do it wrong.

Quote from: MeSo 131 is practically "Here's information that you will never have to use in your future careers"? Wow, no wonder I'm bored in that class.

Quote from: Person BYou will use everything in 131, over and over again.
For job interviews, you will be expected to know everything which is taught in 131.


According to Person A, vectors can replace most of the material I'm learning right now and is used more often in career work. So why must I know how to use Linked Lists and the such? I guess knowing how they work is okay, but to know how to use them? Seems like wasted time to me. (And yes, while I may be a helpful Ruby scripter around here, I'm still much a beginner when it comes to theory and how things work, especially since I've only been using C++ for 3-4 months now)

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Blizzard

I disagree. It's actually quite simple to explain, especially since I had the same opinion back then. The equivalent would be somebody trying to learn a martial art and saying "I don't want to learn the basic stuff and how things work, show me how I can beat up somebody!"

You are supposed to learn and understand how these things actually work. Just learning the theory won't stick as good as if you actually implemented it. If you know the advantages and disadvantages between structures like a linked list, an std::vector, std::deque, etc. (and between binary trees, RB-trees, hash maps, std::map, etc.), you can actually make relevant and better decisions for system designs. Sure, you'll use vectors probably 99% of the time. But that remaining 1% might just be a heavy performance bottle neck.
I know that I have a situation like that in our engine. Since the array I needed was often changed and stuff was added at the beginning, this is quite a performance hit if you are using std::vector which has to move stuff around if you add stuff at the beginning. Adding elements at the beginning of an std::list has a complexity of only O(1) so it's much more suited for that kind of thing. I have another situation in our particle engine where it makes much more sense to use std::deque (or more specifically our derived implementation hltypes::Deque) than a simple std::vector because of some of the differences in how it is used and how it works internally.

Somebody without that kind of knowledge is not fit to be a system designer. Everybody can learn how to program these days, but programming engineers are the real heroes here. They are the ones who designed the new systems and languages everybody is using. They are the lead programmers and the bosses. Ever wonder why Java is so slow? It's a bit hard to explain, but it surely isn't because somebody used std::vector at the wrong place where he should have used std::list.

Sure, you may be pissed that you actually have to implement this now, but have some faith in your teachers. They wouldn't be teaching you this stuff if it wasn't relevant. Also, at one point you may have to work with a system that does not have an STL implementation (like early Android OS versions!) in which case you may have to provide your own and if you don't know how it works, you're just fucked.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

KK20

QuoteIt's actually quite simple to explain, especially since I had the same opinion back then.

Glad I'm not the only one.

I think Person A's comment just confused me. He made it sound like vectors are the greatest thing and that everything in this class is easily replaced by it. But thank you for that detailed comment. No one was giving me any straight up answers. You wouldn't believe how much "He doesn't know what he's saying," "He's so wrong," and "131 is very important" comments I received... :facepalm:

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!