c++ - Fast bucket implementation -

in graph class need handle nodes integer values (1-1000 mostly). in every step want remove node , neighbors graph. want begin node of minimal value. thought long how in fastest possible manner , decided following:

• the graph stored using adjancency lists
• there huge array std::vector<node*> bucket[1000] store nodes value
• the index of lowest nonempty bucket stored , kept track off
• i can find node of minimal value fast picking random element of index or if bucket empty increase index
• removing selected node bucket can done in o(1), problem removing neighbors need search bucket bucket[value of neighbor] first neighbor nodes, not fast.

is there more efficient approach this?

i thought of using std::list<node*> bucket[1000], , assign every node pointer "list element", such can remove node list in o(1). possible stl lists, can done normal double linked list implement hand?

i did similar priority queue implementation using buckets.

what did use hash tables (unordered_map), way, don't need store 1000 empty vectors , still o(1) random access (general case, not guaranteed). now, if need store/create graph class 1 time, doesn't matter. in case needed create priority queue tens/hundreds of time per second , using hash map made huge difference (due fact created unordered_sets when had element of priority, no need initialize 1000 empty hash sets). hash sets , maps new in c++11, have been available in std::tr1 while now, or use boost libraries.

the difference can see between & usecase, need able remove neighboring nodes. i'm assuming every node contains list of pointers it's neighbors. if so, deletion of neighbors should take k * o(1) k number of neighbors (again, o(1) in general, not guaranteed, worst case o(n) in unordered_map/set). go on every neighboring node, priority, gives correct index hash map. find pointer in hash set priority maps to, search in general o(1) , removing element again o(1) in general.

all in all, think got pretty idea of do, believe using hash maps/sets speed code quite lot (depends on exact usage of course). me, speed improvement of implementation unordered_map<int, unordered_set> versus vector<set> around 50x.