开发者

Data structure for sorting/retrieval strings

I have multiple arr开发者_开发百科ays of strings, I used a comparison function to sort them in a priority queue. I overlooked the fact that I need to iterate through the strings..

What other data structure would you recommend? Perhaps something that allows a comparison function so that I get a sorted set of strings

I could effectively pop the elements from the priority queue but that means I would need auxiliary space before pushing them back onto the priority queue

It would be ideal if a vector allows a comparison function. Would an STL "set" work? I have a fixed number of elements (about 450).

Edit: Confirming that STL's set is working.. even without defining my own comparison function for strings.


I'm not really sure on what you need. I assume that by "I need to iterate through the strings" you mean that you need to iterate over the remaining (not "popped") strings in unsorted order and in addition need to access them using a priority queue (through "pop"). If you need to iterate over a sorted sequence, you should sort the input strings up front (e.g. through std::set) and not use a priority queue (priority queues doesn't necessarily fully sort all of the items right away, it sorts the sequence "on demand").

std::priority_queue uses an underlying container (defaults to std::vector). By inheriting this class you could get access to the container. The protected member variable is defined in the standard, and this should in theory be safe to do (don't bet that it is in real life though). However, inheriting STL containers is frowned upon.

An alternative is to create you're own priority queue, e.g. based on std::vector and std::make_heap, std::pop_heap and std::push_heap. std::priority_queue uses these functions internally.


A set would work, but you could just make a vector, reserve enough capacity, and then use sorted inserts using lower_bound. Since strings are cheap to swap, this should be fine (and in any case 450 is a tiny number).

A vector has constant-time lookup and random access, so if you don't need to insert and erase a lot, it's a better choice.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜