0

I have multiple arrays 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.

cisgreat
  • 75
  • 1
  • 6
  • 2
    You can use `std::sort` on a `std::vector`, and you can pass in a comparison function to define the sort order. Do you need anything besides being able to iterate in order? – Ben Voigt Jul 02 '11 at 16:33
  • The comparison function is not a property of the container, but of the sort algorithm; any ordered container with random-access iterators will work fine with `std::sort`, which in turn allow a custom comparison functor. – Matteo Italia Jul 02 '11 at 16:36

2 Answers2

1

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.

Community
  • 1
  • 1
larsmoa
  • 12,604
  • 8
  • 62
  • 85
0

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.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084