algorithm - memory efficient structure to track a subset of an array in its original order -

algorithm - memory efficient structure to track a subset of an array in its original order -

i using c# don't think language specific question.

i working on info construction track subset of big array. example, have changing array of characters , want track vowels in it. want track them in such way original order maintained.

to illustrate, let's character array is: [a, b, d, c, i, a, e, f]. vowels subset want [a, i, a, e]. if after while character array changed [t, b, d, c, i, a, e, f] (the first element has changed t), vowels subset become [i, a, e].

the vowels subset random-accessed if array: vowels[0], vowels[3] ... etc.

i can hence summarize features required info structure:

1) memory efficient - both underlying array , subset can large. benchmarking 1000000 entries.

2) original order of elements in underlying array must maintained in subset.

3) fast random access speed. utilize subset in same way using array.

4) deletion , insertion needs efficient. have alter notification on underlying array - eg. when i-th character in underlying array has changed, notification saying "i-th element has changed b". need insert or delete corresponding item in subset

5) if going create difference, prefer faster deletion , can give performance of insertion. nature of our application has showed me insertion on subset much less frequent deletion, , happens @ tail. deletion, can happen lot, in head or middle portion of subset.

ps. have seen smart way fast deletion of array element: maintain counter of how many elements in array. when deleting element, swap lastly element in array , cut down counter. makes deletion o(1) operation. although waste memory not shrinking array, satisfied since info construction array - compact enough. the issue approach is: violates requirement (2). order of element in subset changed original when deletion occurs.

edit: after reading several answers, realize can inquire question in more interesting way (at to the lowest degree think more interesting :) ):

i agree counted b-tree working solution. don't need support: 1) element look-up. e.g. don't need find first 'a' in subset 2) don't need sorting. want maintain original order.

it appears i don't need comparing of element @ all. know of sorted info structures based on element comparison. know why optimal complexity o(log n). wondering whether possible improve complexity of of 3 operations(random access, insertion, deletion), or cut down memory complexity, if don't need comparison?

i think need order statistic balanced binary tree maintains order of elements , supports insertion , deletion in o(logn). operations lookup, insertion , deletion o(logn).

algorithm :-

1. store required values in tree <index,vowel> pairs 2. maintain index key tree node. 3. can lookup nth element in tree in o(logn) 4. can delete element in o(logn) 5. can insert element in o(logn) 6. space requirement o(n) memory size variables

algorithm data-structures