git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: ordered string-list considered harmful, was Re: [PATCH v3] Allow aliases that include other aliases

From
brian m. carlson <sandals@crustytoothpaste.net>
Date
Sep 8, 2018, 16:49 UTC
Message-ID
<20180908164900.GP432229@genre.crustytoothpaste.net>
In-Reply-To
<20180907072353.GC172953@aiede.svl.corp.google.com>
On Fri, Sep 07, 2018 at 12:23:53AM -0700, Jonathan Nieder wrote:
Show 9 quoted lines
> Ævar Arnfjörð Bjarmason wrote:
> > If this turns out to be a common use-case perhaps the easiest way to
> > support that would be to make the hashmap (optionally?) ordered, as Ruby
> > 1.9 did with their hash implementation:
> > https://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/
> 
> That's about recording the order of insertion.  I'm talking about
> something much simpler: sorting an array (as preparation for emitting
> it) and binary searching to find an entry in that array.

If you want both a collection that is always sorted and has efficient lookup for an arbitrary entry, then a B-tree is probably a better choice. That's the primitive that Rust provides for that situation.

-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204
Previous: Jonathan NiederNext: Jeff King
Message 8 of 13 in “ordered string-list considered harmful, was Re: [PATCH v3] Allow aliases that include other aliases”
  1. Jeff KingSep 6, 2018
  2. Jeff KingSep 6, 2018
  3. Jonathan NiederSep 6, 2018
  4. Jeff KingSep 7, 2018
  5. Jonathan NiederSep 7, 2018
  6. Ævar Arnfjörð BjarmasonSep 7, 2018
  7. Jonathan NiederSep 7, 2018
  8. brian m. carlsonSep 8, 2018
  9. Jeff KingSep 7, 2018
  10. Stefan BellerSep 6, 2018
  11. Jeff KingSep 6, 2018
  12. Stefan BellerSep 6, 2018
  13. Jeff KingSep 7, 2018

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.