4 ms·

The problem is that abstractions are leaky. E.g. when I first started learning C++ in high school, I didn't know a tree if it bit me. But, the STL has a set imp

by eshvk 13y ago

The problem is that abstractions are leaky. E.g. when I first started learning C++ in high school, I didn't know a tree if it bit me. But, the STL has a set implementation. If you take a closer look at the docs, you will find out that it is implemented as a red-black tree. I am not sure the assertion that you will never come across a tree or a graph in your life will be true always.

SamReidHughes 13y ago
There's nothing that says std::map has to be implemented as a red-black tree. And using an abstract data type that's implemented with a tree is not the same thing as making your own tree for your own purposes.
- eshvk 13y ago
  > There's nothing that says std::map has to be implemented as a red-black tree. Of course not, but understanding what that means is key to using it. If you think a red black tree is some arcane bullshit that you never are going to use, you will probably skip over it when you read the docs and get bitten.
  - SamReidHughes 13y ago
    > Of course not, but understanding what that means is key to using it. Not at all. A user could think it's a hash table and they'd still be likely to maximize the potential utility of the type in their application. They could understand that it's implemented with a balanced search tree without knowing about the details of the balancing algorithm and that's pretty much the maximum utility right there. (In fact it's a good mnemonic for understanding almost all the performance and iterator guarantees of a std::map's functions.) And you're not going to find that it's implemented as a red black tree in "the docs". You generally don't know that. All you know and all you'll see documented is the performance requirements and iterator invalidation behavior of various functions. I mean look at the docs. That's what's there. The real benefit of being comfortable with trees and graphs is so that you're comfortable with actually using trees and graphs yourself, directly, when they'd be useful to manipulate. If you want to look at a commit log, well, that's a graph, and I guess you can't work with that if you claim that graphs are weird obscure stuff and cringe at the word "acyclic". Want to use a filesystem? Apparently that's a hard thing for some people, sadly enough because it's a tree (or graph, depending on your attitude about soft and hard links). That's where you're writing code that manipulates the actual data structure, instead of just using some lookup-table interface.
    - eshvk 13y ago
      > The real benefit of being comfortable with trees and graphs is so that you're comfortable with actually using trees and graphs yourself, directly, when they'd be useful to manipulate. If you want to look at a commit log, well, that's a graph, and I guess you can't work with that if you claim that graphs are weird obscure stuff and cringe at the word "acyclic". Want to use a filesystem? Apparently that's a hard thing for some people, sadly enough because it's a tree (or graph, depending on your attitude about soft and hard links). That's where you're writing code that manipulates the actual data structure, instead of just using some lookup-table interface. I am not clear how you are disagreeing with me here. :) Surely manipulating commit logs, understanding say how Git works, squashing commits, rebasing, manipulating access to the file system, surely, these are things that are not out of the realm of being asked to do. Hell, if you are dealing with a freaking linked list at some point or not in your career, you are dealing with a DAG.

by eshvk 13y ago

SamReidHughes 13y ago

There's nothing that says std::map has to be implemented as a red-black tree. And using an abstract data type that's implemented with a tree is not the same thing as making your own tree for your own purposes.

eshvk 13y ago
> There's nothing that says std::map has to be implemented as a red-black tree. Of course not, but understanding what that means is key to using it. If you think a red black tree is some arcane bullshit that you never are going to use, you will probably skip over it when you read the docs and get bitten.
- SamReidHughes 13y ago
  > Of course not, but understanding what that means is key to using it. Not at all. A user could think it's a hash table and they'd still be likely to maximize the potential utility of the type in their application. They could understand that it's implemented with a balanced search tree without knowing about the details of the balancing algorithm and that's pretty much the maximum utility right there. (In fact it's a good mnemonic for understanding almost all the performance and iterator guarantees of a std::map's functions.) And you're not going to find that it's implemented as a red black tree in "the docs". You generally don't know that. All you know and all you'll see documented is the performance requirements and iterator invalidation behavior of various functions. I mean look at the docs. That's what's there. The real benefit of being comfortable with trees and graphs is so that you're comfortable with actually using trees and graphs yourself, directly, when they'd be useful to manipulate. If you want to look at a commit log, well, that's a graph, and I guess you can't work with that if you claim that graphs are weird obscure stuff and cringe at the word "acyclic". Want to use a filesystem? Apparently that's a hard thing for some people, sadly enough because it's a tree (or graph, depending on your attitude about soft and hard links). That's where you're writing code that manipulates the actual data structure, instead of just using some lookup-table interface.
  - eshvk 13y ago
    > The real benefit of being comfortable with trees and graphs is so that you're comfortable with actually using trees and graphs yourself, directly, when they'd be useful to manipulate. If you want to look at a commit log, well, that's a graph, and I guess you can't work with that if you claim that graphs are weird obscure stuff and cringe at the word "acyclic". Want to use a filesystem? Apparently that's a hard thing for some people, sadly enough because it's a tree (or graph, depending on your attitude about soft and hard links). That's where you're writing code that manipulates the actual data structure, instead of just using some lookup-table interface. I am not clear how you are disagreeing with me here. :) Surely manipulating commit logs, understanding say how Git works, squashing commits, rebasing, manipulating access to the file system, surely, these are things that are not out of the realm of being asked to do. Hell, if you are dealing with a freaking linked list at some point or not in your career, you are dealing with a DAG.