25 ms·
If the list of chunks is represented as a deque, then concatenation and popping the first character can both be done in constant time.
by chalst 7y ago
If the list of chunks is represented as a deque, then concatenation and popping the first character can both be done in constant time.
- joosters 7y agoSure, 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.