June 29, 2006 MinTL, SortedSet and searching | ||||
---|---|---|---|---|
| ||||
Hello, I'm new to programming and to D. I 'inherited' some C code (a small library I want to port to D) that used an array to store in sorted order pointers to structs. I thought it would be nice fit for the MinTL SortedSet. But how does one go about doing a (<= O(n)) search on a MinTL SortedSet that returns a value? The value I would search using is a struct with only some of its members set. The opCmp on the struct allows for this. I'm using SortedSet.values but I'm balking at it.. Perhaps I should just keep using an array of pointers with reallocations and binary search. Or is there room in the MinTL for something else? Or am I missing something? - Paul Findlay P.S. I'm sorry if this is the wrong newsgroup.. |
July 05, 2006 Re: MinTL, SortedSet and searching | ||||
---|---|---|---|---|
| ||||
Posted in reply to Paul Findlay | "Paul Findlay" <r.lph50+d@gmail.com> wrote in message news:e80htr$2jtd$1@digitaldaemon.com... > Hello, > > I'm new to programming and to D. > > I 'inherited' some C code (a small library I want to port to D) that used an array to store in sorted order pointers to structs. I thought it would be nice fit for the MinTL SortedSet. But how does one go about doing a (<= O(n)) search on a MinTL SortedSet that returns a value? The value I would search using is a struct with only some of its members set. The opCmp on the struct allows for this. I'm using SortedSet.values but I'm balking at it.. > > Perhaps I should just keep using an array of pointers with reallocations and binary search. Or is there room in the MinTL for something else? Or am I missing something? > > - Paul Findlay > P.S. I'm sorry if this is the wrong newsgroup.. I'm not sure what the problem is but here's an exmaple usage from the unittests: // test SortedSet SortedSet!(char[]) s2; s2.add("hello","world"); assert( s2["world"] ); assert( s2["hello"] ); assert( !s2["worldfoo"] ); foreach(char[] val ; s2) { printf("%.*s\n",val); } assert( !s2.isEmpty ); Lookups should be O(log(n)). If you never need to traverse the set in order you could also use a HashAA instead of a SortedAA and get O(1) lookups. -Ben |
Copyright © 1999-2021 by the D Language Foundation