27 ms·
Sure, but the page O(1) examples are: 1) Getting the data for a writev() call: Sure, it’s just returning a pointer to an array of iovecs, but someone is going
by joosters 7y ago
Sure, but the page O(1) examples are:
1) Getting the data for a writev() call: Sure, it’s just returning a pointer to an array of iovecs, but someone is going to have to linearly scan that array.
2) Substituting or moving data anywhere in the string: As you say, you can do stuff with the start or end of a (v)string with O(1) but anywhere else will require a linear walk of the data chunks
- chalst 7y agoIf the claim is random access, then I agree that O(1) is imposssible. Rope would allow these tasks to be carried out in logarithmic time. The tasks I chose were the first two API desiderata from http://www.and.org/vstr/design http://www.and.org/vstr/design - which is the examples page you had in mind?
- joosters 7y agoI was quoting from the ‘about’ section of the linked page. I’m not deliberately trying to pick on or criticise this data structure, it’s certainly a good way of manipulating some forms of text (I’ve used similar data structures for efficient HTTP processing/mangling). It’s just that there can be hidden costs and the O(1) claims appeared misleading.