All geek questions in one place

Container with quick inserts and index?

I am looking for a C ++ container class that is indexed as std::vector but has quick insertion, deletion, and indexing. For example, the vector interface implemented with the base balancing tree will contain O / logN) and O (logN) inserts / deletes.

To be clear: I'm not looking for std::map<int, T> . Inserting an element with index N should increase the indices of all subsequent elements in the array, which would not be the case with std::map<int, T> .

I found an AVL Array that does exactly what I am looking for. It has the correct interface, but I would like to see if there are other options.

Do you know any other (production qualities) implementations? Maybe something more popular (with something like something like that?). Something with a smaller memory size? (A node containing a pointer in an AVL array is 64 bytes on my machine.)

+5
source share
1 answer

Thinking of using SkipLists yet? This is basically a linked list with several levels of shortcuts added at the top, which are organized like a tree. No shuffling nodes, just a few pointers. Shortcuts allow faster iterations on your list. One of my favorite.

http://openmymind.net/Building-A-Skiplist/

http://en.wikipedia.org/wiki/Skip_list

+1
source

Source: https://habr.com/ru/post/1201750/

More articles:


All Articles