CODEWITHSUNDEEP
c++sortingdata-structuresqueuepriority-queue
Thijser
Thijser

Reputation: 2633

c++ is there a default data class for sorted index based acces at reasonable speed?

I'm looking for a dataclass that keeps its data in order but also allows access in any order I want.

Basically I'm looking for a queue that allows me to access items in a random order as well as remain in order (int lowest to highest). When adding items it should not have to resort everything (O(n*log(n)) operation) but instead just insert and remove it in a fast way (O(log (n))). I know such data structures exist(binary tree based queue) but does c++ offer one? My current applications asks that I can do things like get middle from a queue/list of items or get the second highest priority item. Does c++ have a default data class for this? Or do I have to make it myself?

By the way this is c++ 98

Upvotes: 3

Views: 129

Answers (3)

Edmund
Edmund

Reputation: 737

I think the vector plus heap is like what you are looking for.

vector<int> v;

// insert elements
v.push_back(3);
push_heap(v.begin(), v.end());

v.push_back(2);
push_heap(v.begin(), v.end());

v.push_back(4);
push_heap(v.begin(), v.end());

// get the second big
sort_heap(v.begin(), v.end());
cout << v[v.size() - 2] << endl;

// insert elements
make_heap(v.begin(), v.end());
v.push_back(7);
push_heap(v.begin(), v.end());

// get the second big
sort_heap(v.begin(), v.end());
cout << v[v.size() - 2] << endl;

The insertion is fast. But each time before you want to access item which is not the biggest, you have to sort the heap, since the heap only give you the biggest. And after that and before new insertion you have to call make_heap to make the vector a heap again.

Upvotes: 1

Scott Langham
Scott Langham

Reputation: 60341

You have to make it yourself.

Create a wrapper around a std::vector. Add methods as required that delegate to the vector, for insert methods, call std::upper_bound to find where to do the insertion.

Upvotes: 0

Jan Hudec
Jan Hudec

Reputation: 76296

No, such structure does not exist in standard library. I don't think it exists in boost either, but looking at Boost.MultiIndex wouldn't hurt.

Otherwise such structure is conceptually simple—some kind of balanced search tree (a-b or red-black probably) that additionally needs to maintain number of children in it's nodes (which probably makes a-b tree with higher a and b more suitable than 2-3 or red-black. But there does not seem to be anything to help you implement it.

Upvotes: 0

Related Questions