7 ms·

Data Structures using C++

101 points by michaelrbock 13y ago

minimax 13y ago
I think I'm in the minority, but I'm happy to see C++ in a college course. I thought it was all Python and Java these days.
- fsck--off 13y ago
  A friend of mine has a colleague that deliberately uses C++ in an introductory CS class to "thin the herd" of students he has to teach.
  - greyfade 13y ago
    That it will do.
  - hvs 13y ago
    CS125 at UIUC was taught in Scheme (using the SICP book no less) as the first course in CS and it did a pretty thorough job of separating the wheat from the chaff.
    - zerohp 13y ago
      It is now taught in Java while the data structures class (225) is C++. The Computer Engineering curriculum is going the other way and now teaches computer architecture, assembly, and C (in that order) before sending students over to the CS department for data structures. Former TAs tell me that CompE students find CS 225 to be much easier than Computer Science students.
      - hvs 13y ago
        I can imagine. Just for reference, I graduated in '98, so things have probably changed quite a bit since I was there. Every class after CS125 used C++ (except AI, which was in Lisp), but C++98 was still in committee and the STL wasn't really available (templates existed, though). So it really was more like "C with Classes" than modern C++. I wonder if CS373 is still destroyer of students that it was in my day. The average score (before the curve) was around 40%.
    - rayiner 13y ago
      Ah yes. Intro classes, where the point isn't to teach people but sort out the ones you don't have to teach.
  - alphamethyl 13y ago
    i hear stuff like this all the time. all it accomplishes is to make CS a field of very similar people that happen to have the required mental models for entry. it's ridiculous. other fields don't have this arrogant "you either get it or you don't" attitude. even math, the most opaque of opaque subjects, tries to dampen the learning curve to thinking like a mathematician. most kids that weren't living their childhoods on a computer simply don't understand how to think about computers and programming. to deny them entry to your field because they can't figure out how pointers work is toxic - especially when introductory CS classes are huge and students don't get much one on one help. programmers that think like programmers are a dime a dozen. programmers with more diverse mental models are the ones that innovate, even if it takes them longer to grok programming.
    - fsck--off 13y ago
      I agree with you. This method does drive away many talented young people from programming, and it does create CS culture issues several years later when all of the graduates think the same way.
- bowmessage 13y ago
  I attend Texas A&M University, and maybe it' just because Stroustrup works here, but all of my programming classes are C++ based. I have to learn Haskell this upcoming semester, I'm slightly worried about that!
  - mpyne 13y ago
    Just be careful that they're not teaching you Haskell as a way to 'ease you into' C++ template metaprogramming!
1O0101ll100O 13y ago
My school teaches an intro course in python and then switches to c++ for the data structures and beyond. It's gotta be easier to just start with c++ and run with it.
- michaelrbock 13y ago
  Just for some context, USC starts intro to CS with C++ and then does Data Structures in C++, then switches to Java for more advanced OOP. Upper division classes are usually in Java or C++.
appplemac 13y ago
Uhh that yellow // Actually, I'm glad that C++ has been my first programming language. Its syntax is pretty straightforward, and it's even better to work with when you've got extremely clear guidelines set up – at my university (UPC BarcelonaTech) we had a course PRO1, where you got seriously punished if you used spaces instead of tabs, or if you set 2 as your tabstop, or if you used goto, to name a few. Now I cannot say that I share all those guideline rules, but at least I understand what a good C++ code style is.
dljsjr 13y ago
My CS degree was 100% C based; Java shows up in a class about OOP, and our class on Programming Language theory exposes us to Lisp, Java, and Prolog. They used to be Java based and chose to switch back to a C based curriculum around 2007, as well as focusing more heavily on algorithms and data structures while pushing the more "software engineering" type courses in to elective and offering Software Engineering as a specialization on a CS degree. Joel Spolsky wrote a great article[1] in 2005 that basically says using a massively high level language like Python or Java as the core of a CS curriculum is damaging because the languages aren't "hard" enough. As curmudgeonly as it might sound, I'd be inclined to agree. Even though I rarely write C code anymore (we do everything in Java in our lab), the underlying understanding of memory management that is acquired from having to learn to handle it manually has been invaluable to me as a programmer. Additionally, C/C++ is the language of UNIX and still the lingua franca of high-performance. Most high-level languages worth their salt will have a foreign interface to dynamically load C libraries; we're in robotics and have to work heavily with ROS/Gazebo as participants in the DARPA Robotics Challenge, and even outside of this a lot of really great tools for mathematical optimization and high-performance numerical analysis are all written in C. I'm one of only two or three people in our lab with the requisite knowledge to be able to effectively hand-roll JNI wrappers, and I don't consider this to be a good thing at all. It's pretty clear to me that C/C++ aren't going anywhere any time soon, and it's always good to see a CS curriculum that still focuses on C/C++. 1: http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html http://www.joelonsoftware.com/articles/ThePerilsofJavaSchool...
- dragonwriter 13y ago
  > Joel Spolsky wrote a great article[1] in 2005 that basically says using a massively high level language like Python or Java as the core of a CS curriculum is damaging because the languages aren't "hard" enough. There's certainly a value in getting closer to the machine (as C does), OTOH, there's a value in not having a lot of boilerplate cruft between you and the algorithm, which makes something like Python valuable. Really, I think a CS program that exclusively uses any one language is probably robbing students of valuable insight that comes from the different perspectives that working through different languages (particularly, languages from different design paradigms) provides.
jmt7les 13y ago
Learning C++ was the best. That course is just missing the Algorithm Analysis which mine had along with Data Structures, all C++ and no #includes allowed.
capkutay 13y ago
I don't know what the fuss is about with java and python. It was really beneficial in school to work on large java projects where we were exposed to eclipse, svn, log4j, junit, jdbc, etc. It was unbelievably useful going into my job. On the other hand, we used C when we were studying something low-level like thread communication or operating systems. C/C++ absolutely has its place in the college cs curriculum as do java and python.
HNLogInShit 13y ago
I don't really see exceptions used that much in real-life products. Any thoughts on this?
shreeshga 13y ago
I once tried to code an assignment involving TF-IDF on a corpus of docs. It ran blazingly fast compared to python. But was debugging segmentation faults until the last minute.
16s 13y ago
Understanding the C++ std containers is almost a complete lesson in data structures. std::set is typically a red black tree, std::unordered_set is a hash table, etc. Looking at how these containers are implemented and understanding how/when to use which really separates the men from the boys when it comes to scaling and efficiency. You can probably learn the concepts from other languages, but it's been my experience that C++ devs typically understand these concepts more so than most.
deadfall 13y ago
Similar: Stanford - Abstractions and data structures C++ http://see.stanford.edu/see/lecturelist.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e http://see.stanford.edu/see/lecturelist.aspx?coll=11f4f422-5... Edit: The only thing that takes a little research is tracking down the C++ libraries that coincide with the class.
- elteto 13y ago
  Thanks for this. It is worth pointing out to others that these lectures include videos.
  - deleted 13y ago
    [deleted]
- mhaymo 13y ago
  This one actually includes all the practical material. Thanks :)
zenbowman 13y ago
I was a teaching assistant for that class for 2 years, HNs got me feeling nostalgic.
mhaymo 13y ago
This seems incomplete without the labs and assignments included. The github link on the assignments page leads nowhere.
Peaker 13y ago
Most C++ implementations of linked lists are bad, including std::list and apparently, this course's. People misunderstand linked lists so badly, that they actually list the motivation for linked lists as fine-grained growth, as opposed to an array-based list. The main benefits of linked lists over array-lists are: * Can put data structures in lists even if they are already in some other data structure. For example, have some ordering between array elements. * In intrusive style (can find the list links based on the item), can add after that position in O(1). * In intrusive style with doubly-linked list, can also delete an item in that position in O(1). Non-intrusive lists are incompatible with having the same O() while also allowing an item to be in multiple data structures simultaneously. std::list indeed does not allow this, and is almost useless. It's sad to see this taught incorrectly in courses, too, perpetuating the uselessness of std::list.
- deleted 13y ago
  [deleted]
  - betterunix 13y ago
    1. You can maintain a linked list whose elements are already stored in another data structure. This allows you to impose a different order on the elements without having to copy them. 2. http://www.boost.org/doc/libs/1_45_0/doc/html/intrusive/intrusive_vs_nontrusive.html http://www.boost.org/doc/libs/1_45_0/doc/html/intrusive/intr... Were there any other terms you had trouble with?
    - deleted 13y ago
      [deleted]
- zerohp 13y ago
  Your points 2 and 3 are satisfied by using an iterator to keep track of the position.
  - ambrop7 13y ago
    But then you have to pull those iterators into almost everything that deals with your objects, making the code hard to follow, and wasting memory. The problem also gets worse when your objects are in more than one list (which you can't literally do with std::list anyway) since you have to keep several iterators around.
davvid 13y ago
Michael Crowley's a great professor and a swell dude. His Operating Systems class is also a great crash course that forces you into C programming competence.
krapp 13y ago
I'm taking C++ (almost through with the beginning semester) after basically being self-taught in python, js and php. It's interesting, and I can definitely appreciate how it teaches you fundamentals in a way higher languages don't necessarily. Sort of like learning to drive stick when all you've known is an automatic.

101 points by michaelrbock 13y ago

I think I'm in the minority, but I'm happy to see C++ in a college course. I thought it was all Python and Java these days.

fsck--off 13y ago
A friend of mine has a colleague that deliberately uses C++ in an introductory CS class to "thin the herd" of students he has to teach.
- greyfade 13y ago
  That it will do.
- hvs 13y ago
  CS125 at UIUC was taught in Scheme (using the SICP book no less) as the first course in CS and it did a pretty thorough job of separating the wheat from the chaff.
  - zerohp 13y ago
    It is now taught in Java while the data structures class (225) is C++. The Computer Engineering curriculum is going the other way and now teaches computer architecture, assembly, and C (in that order) before sending students over to the CS department for data structures. Former TAs tell me that CompE students find CS 225 to be much easier than Computer Science students.
    - hvs 13y ago
      I can imagine. Just for reference, I graduated in '98, so things have probably changed quite a bit since I was there. Every class after CS125 used C++ (except AI, which was in Lisp), but C++98 was still in committee and the STL wasn't really available (templates existed, though). So it really was more like "C with Classes" than modern C++. I wonder if CS373 is still destroyer of students that it was in my day. The average score (before the curve) was around 40%.
  - rayiner 13y ago
    Ah yes. Intro classes, where the point isn't to teach people but sort out the ones you don't have to teach.
- alphamethyl 13y ago
  i hear stuff like this all the time. all it accomplishes is to make CS a field of very similar people that happen to have the required mental models for entry. it's ridiculous. other fields don't have this arrogant "you either get it or you don't" attitude. even math, the most opaque of opaque subjects, tries to dampen the learning curve to thinking like a mathematician. most kids that weren't living their childhoods on a computer simply don't understand how to think about computers and programming. to deny them entry to your field because they can't figure out how pointers work is toxic - especially when introductory CS classes are huge and students don't get much one on one help. programmers that think like programmers are a dime a dozen. programmers with more diverse mental models are the ones that innovate, even if it takes them longer to grok programming.
  - fsck--off 13y ago
    I agree with you. This method does drive away many talented young people from programming, and it does create CS culture issues several years later when all of the graduates think the same way.
bowmessage 13y ago
I attend Texas A&M University, and maybe it' just because Stroustrup works here, but all of my programming classes are C++ based. I have to learn Haskell this upcoming semester, I'm slightly worried about that!
- mpyne 13y ago
  Just be careful that they're not teaching you Haskell as a way to 'ease you into' C++ template metaprogramming!

1O0101ll100O 13y ago

My school teaches an intro course in python and then switches to c++ for the data structures and beyond. It's gotta be easier to just start with c++ and run with it.

michaelrbock 13y ago
Just for some context, USC starts intro to CS with C++ and then does Data Structures in C++, then switches to Java for more advanced OOP. Upper division classes are usually in Java or C++.

appplemac 13y ago

Uhh that yellow // Actually, I'm glad that C++ has been my first programming language. Its syntax is pretty straightforward, and it's even better to work with when you've got extremely clear guidelines set up – at my university (UPC BarcelonaTech) we had a course PRO1, where you got seriously punished if you used spaces instead of tabs, or if you set 2 as your tabstop, or if you used goto, to name a few. Now I cannot say that I share all those guideline rules, but at least I understand what a good C++ code style is.

dljsjr 13y ago

My CS degree was 100% C based; Java shows up in a class about OOP, and our class on Programming Language theory exposes us to Lisp, Java, and Prolog. They used to be Java based and chose to switch back to a C based curriculum around 2007, as well as focusing more heavily on algorithms and data structures while pushing the more "software engineering" type courses in to elective and offering Software Engineering as a specialization on a CS degree. Joel Spolsky wrote a great article[1] in 2005 that basically says using a massively high level language like Python or Java as the core of a CS curriculum is damaging because the languages aren't "hard" enough. As curmudgeonly as it might sound, I'd be inclined to agree. Even though I rarely write C code anymore (we do everything in Java in our lab), the underlying understanding of memory management that is acquired from having to learn to handle it manually has been invaluable to me as a programmer. Additionally, C/C++ is the language of UNIX and still the lingua franca of high-performance. Most high-level languages worth their salt will have a foreign interface to dynamically load C libraries; we're in robotics and have to work heavily with ROS/Gazebo as participants in the DARPA Robotics Challenge, and even outside of this a lot of really great tools for mathematical optimization and high-performance numerical analysis are all written in C. I'm one of only two or three people in our lab with the requisite knowledge to be able to effectively hand-roll JNI wrappers, and I don't consider this to be a good thing at all. It's pretty clear to me that C/C++ aren't going anywhere any time soon, and it's always good to see a CS curriculum that still focuses on C/C++. 1: http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html http://www.joelonsoftware.com/articles/ThePerilsofJavaSchool...

dragonwriter 13y ago
> Joel Spolsky wrote a great article[1] in 2005 that basically says using a massively high level language like Python or Java as the core of a CS curriculum is damaging because the languages aren't "hard" enough. There's certainly a value in getting closer to the machine (as C does), OTOH, there's a value in not having a lot of boilerplate cruft between you and the algorithm, which makes something like Python valuable. Really, I think a CS program that exclusively uses any one language is probably robbing students of valuable insight that comes from the different perspectives that working through different languages (particularly, languages from different design paradigms) provides.

jmt7les 13y ago

Learning C++ was the best. That course is just missing the Algorithm Analysis which mine had along with Data Structures, all C++ and no #includes allowed.

capkutay 13y ago

I don't know what the fuss is about with java and python. It was really beneficial in school to work on large java projects where we were exposed to eclipse, svn, log4j, junit, jdbc, etc. It was unbelievably useful going into my job. On the other hand, we used C when we were studying something low-level like thread communication or operating systems. C/C++ absolutely has its place in the college cs curriculum as do java and python.

HNLogInShit 13y ago

I don't really see exceptions used that much in real-life products. Any thoughts on this?

shreeshga 13y ago

I once tried to code an assignment involving TF-IDF on a corpus of docs. It ran blazingly fast compared to python. But was debugging segmentation faults until the last minute.

16s 13y ago

Understanding the C++ std containers is almost a complete lesson in data structures. std::set is typically a red black tree, std::unordered_set is a hash table, etc. Looking at how these containers are implemented and understanding how/when to use which really separates the men from the boys when it comes to scaling and efficiency. You can probably learn the concepts from other languages, but it's been my experience that C++ devs typically understand these concepts more so than most.

deadfall 13y ago

Similar: Stanford - Abstractions and data structures C++ http://see.stanford.edu/see/lecturelist.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e http://see.stanford.edu/see/lecturelist.aspx?coll=11f4f422-5... Edit: The only thing that takes a little research is tracking down the C++ libraries that coincide with the class.

elteto 13y ago
Thanks for this. It is worth pointing out to others that these lectures include videos.
- deleted 13y ago
  [deleted]
mhaymo 13y ago
This one actually includes all the practical material. Thanks :)

zenbowman 13y ago

I was a teaching assistant for that class for 2 years, HNs got me feeling nostalgic.

mhaymo 13y ago

This seems incomplete without the labs and assignments included. The github link on the assignments page leads nowhere.

Peaker 13y ago

Most C++ implementations of linked lists are bad, including std::list and apparently, this course's. People misunderstand linked lists so badly, that they actually list the motivation for linked lists as fine-grained growth, as opposed to an array-based list. The main benefits of linked lists over array-lists are: * Can put data structures in lists even if they are already in some other data structure. For example, have some ordering between array elements. * In intrusive style (can find the list links based on the item), can add after that position in O(1). * In intrusive style with doubly-linked list, can also delete an item in that position in O(1). Non-intrusive lists are incompatible with having the same O() while also allowing an item to be in multiple data structures simultaneously. std::list indeed does not allow this, and is almost useless. It's sad to see this taught incorrectly in courses, too, perpetuating the uselessness of std::list.

deleted 13y ago
[deleted]
- betterunix 13y ago
  1. You can maintain a linked list whose elements are already stored in another data structure. This allows you to impose a different order on the elements without having to copy them. 2. http://www.boost.org/doc/libs/1_45_0/doc/html/intrusive/intrusive_vs_nontrusive.html http://www.boost.org/doc/libs/1_45_0/doc/html/intrusive/intr... Were there any other terms you had trouble with?
  - deleted 13y ago
    [deleted]
zerohp 13y ago
Your points 2 and 3 are satisfied by using an iterator to keep track of the position.
- ambrop7 13y ago
  But then you have to pull those iterators into almost everything that deals with your objects, making the code hard to follow, and wasting memory. The problem also gets worse when your objects are in more than one list (which you can't literally do with std::list anyway) since you have to keep several iterators around.

davvid 13y ago

Michael Crowley's a great professor and a swell dude. His Operating Systems class is also a great crash course that forces you into C programming competence.

krapp 13y ago

I'm taking C++ (almost through with the beginning semester) after basically being self-taught in python, js and php. It's interesting, and I can definitely appreciate how it teaches you fundamentals in a way higher languages don't necessarily. Sort of like learning to drive stick when all you've known is an automatic.