c++ - Rank-Preserving Data Structure other than std:: vector? -
i faced application have design container has random access (or @ least better o(n)) has inexpensive (o(1)) insert , removal, , stores data according order (rank) specified @ insertion.
for example if have following array:
[2, 9, 10, 3, 4, 6] i can call remove on index 2 remove 10 , can call insert on index 1 inserting 13.
after 2 operations have:
[2, 13, 9, 3, 4, 6] the numbers stored in sequence , insert/remove operations require index parameter specify number should inserted or number should removed.
my question is, kind of data structures, besides linked list , vector, maintain this? leaning towards heap prioritizes on next available index. have been seeing fusion tree being useful (but more in theoretical sense).
what kind of data structures give me optimal running time while still keeping memory consumption down? have been playing around insertion order preserving hash table, has been unsuccessful far.
the reason tossing out using std:: vector straight because must construct out preforms vector in terms of these basic operations. the size of container has potential grow hundreds of thousands of elements, committing shifts in std::vector out of question. same problem lines linked list (even if doubly linked), traversing given index take in worst case o (n/2), rounded o (n).
i thinking of doubling linked list contained head, tail, , middle pointer, felt wouldn't better.
in basic usage, able insert , delete @ arbitrary position, can use linked lists. allow o(1) insert/remove, provided have located position in list insert. can insert "after given element" (that is, given pointer element), can not efficiently insert "at given index".
to able insert , remove element given index, need more advanced data structure. there exist @ least 2 such structures aware of.
one rope structure, available in c++ extensions (sgi stl, or in gcc via #include <ext/rope>). allows o(log n) insert/remove @ arbitrary position.
another structure allowing o(log n) insert/remove implicit treap (aka implicit cartesian tree), can find information @ http://codeforces.com/blog/entry/3767, treap implicit keys or https://codereview.stackexchange.com/questions/70456/treap-with-implicit-keys.
implicit treap can modified allow find minimal value in (and support more operations). not sure whether rope can handle this.
upd: in fact, guess can adapt o(log n) binary search tree (such avl or red-black tree) request converting "implicit key" scheme. general outline follows.
imagine binary search tree which, @ each given moment, stores consequitive numbers 1, 2, ..., n keys (n being number of nodes in tree). every time change tree (insert or remove node) recalculate stored keys still 1 new value of n. allow insert/remove @ arbitrary position, key position, require time keys update.
to avoid this, not store keys in tree explicitly. instead, each node, store number of nodes in subtree. result, time go tree root down, can keep track of index (position) of current node — need sum sizes of subtrees have our left. allows us, given k, locate node has index k (that is, k-th in standard order of binary search tree), on o(log n) time. after this, can perform insert or delete @ position using standard binary tree procedure; need update subtree sizes of nodes changed during update, done in o(1) time per each node changed, total insert or remove time o(log n) in original binary search tree.
so approach allows insert/remove/access nodes @ given position in o(log n) time using o(log n) binary search tree basis. can of course store additional information ("values") need in nodes, , can able calculate minimum of these values in tree keeping minimum value of each node's subtree.
however, aforementioned treap , rope more advanced allow split , merge operations (taking substring/subarray , concatenating 2 strings/arrays).