5 ms·

ordered containers exist in most standard libraries. e.g. C++ std::map. Java TreeMap. So it's not a question of having containers ordered. But C++ and Java use

ordered containers exist in most standard libraries. e.g. C++ std::map. Java TreeMap. So it's not a question of having containers ordered. But C++ and Java use red black trees (though avl trees satisfy the requirements set by the C++ standard). These are equivalent to BTrees with a small fanout. I would rather have something like B+Tree with an enormous fan out so the use of being ordered (ranged reads) gets better cache coherency.

throwaway_pdp09 6y ago
I know ordered containers exist in some standard libs, question is, how useful are they? Have you ever had a need for one? Because I've decades of programming and I can't recall ever needing one directly (indirectly via a DB, of course, but I mean directly). What do you do that you feel would benefit from cache locality that in-mem btrees give over other structures? How often have you needed an ordered map at all?
- fnord123 6y ago
  I use ordered structures all the time when I have them. Otherwise I'll approximate with vectors, filling it up and sorting when I'm done.
  - throwaway_pdp09 6y ago
    That seems to miss the point. Ordered containers maintain order. What you're describing is needing ordered results at the end "...and sorting when I'm done". And if you need ordered results only at some end point, it's probably more efficient to accumulate them unsorted then sort them just when needed. What do you regularly do that needs a data structure that maintains order consistently? A LUT for compiler symbols could be implemented as a binary (or n-ary) tree but that order is incidental; it's only used to get fast lookup. A hash would be faster. I think graph algos may be different but I've never used one, and they tend to use heaps to get an order, but don't need to maintain an ordered collection.
    - fnord123 6y ago
      Time Series. But also prefix lookup. You can do some sweet tricks with trees where lookup on strings can use a prefix and then you get an iterator. You can then use this iterator to read the items until you find one where the prefix doesn't match. I've used this in developing storage systems, but it seems like a useful trick that I might want to use elsewhere.
      - throwaway_pdp09 6y ago
        Thanks, I guess you work in different domain than me. I'll do some reading up on both of these. If you have any pointers, please feel free to post them.

throwaway_pdp09 6y ago

I know ordered containers exist in some standard libs, question is, how useful are they? Have you ever had a need for one? Because I've decades of programming and I can't recall ever needing one directly (indirectly via a DB, of course, but I mean directly). What do you do that you feel would benefit from cache locality that in-mem btrees give over other structures? How often have you needed an ordered map at all?

fnord123 6y ago
I use ordered structures all the time when I have them. Otherwise I'll approximate with vectors, filling it up and sorting when I'm done.
- throwaway_pdp09 6y ago
  That seems to miss the point. Ordered containers maintain order. What you're describing is needing ordered results at the end "...and sorting when I'm done". And if you need ordered results only at some end point, it's probably more efficient to accumulate them unsorted then sort them just when needed. What do you regularly do that needs a data structure that maintains order consistently? A LUT for compiler symbols could be implemented as a binary (or n-ary) tree but that order is incidental; it's only used to get fast lookup. A hash would be faster. I think graph algos may be different but I've never used one, and they tend to use heaps to get an order, but don't need to maintain an ordered collection.
  - fnord123 6y ago
    Time Series. But also prefix lookup. You can do some sweet tricks with trees where lookup on strings can use a prefix and then you get an iterator. You can then use this iterator to read the items until you find one where the prefix doesn't match. I've used this in developing storage systems, but it seems like a useful trick that I might want to use elsewhere.
    - throwaway_pdp09 6y ago
      Thanks, I guess you work in different domain than me. I'll do some reading up on both of these. If you have any pointers, please feel free to post them.