fixed length ordered list (C++)
Author
I don't want to reinvent the wheel, so I'm looking for compact solutions that already exist to the following problem (preferably using std::list).
I want a list of fixed maximum length (known at compile time) such that the list is ordered on an attribute of its stored class and the insertion of an object into the list drops the last item in the list if the list is already full (N items stored). I'd like it to be memory efficient such that there are only ever at most N objects of the stored type in existance... thus reusing a dropped item for insertion would be nice (if that makes sense).
Yes, I could do this by creating my own linked list class with ordered inserts, but there must be a trivial way of doing this with std::list (and probably reverse iterators) that I'm just not seeing atm. Any and all help is greatly appreciated.
Thanks,
Timkin
Obviously there are extremes you could go to depending upon what is more important to you, speed or space.
If space was the most important then you'd use a vector because you don't have to store pointers for each item. But then insertion is often slow.
If speed was the most important, you'd use a set because the bottleneck is inserting into the list, which is of course O(n), whereas the set is O(logn).
I'm not sure what your priorities on speed / space are here, making this difficult to answer. Using a atd::list seems like the worst of both. You get O(n) insertion AND two pointers per object.
Can you elaborate on what this is used for perhaps?
Does it really have to be fully sorted, or do you only ever extract the min or max item, as in a heap?
If space was the most important then you'd use a vector because you don't have to store pointers for each item. But then insertion is often slow.
If speed was the most important, you'd use a set because the bottleneck is inserting into the list, which is of course O(n), whereas the set is O(logn).
I'm not sure what your priorities on speed / space are here, making this difficult to answer. Using a atd::list seems like the worst of both. You get O(n) insertion AND two pointers per object.
Can you elaborate on what this is used for perhaps?
Does it really have to be fully sorted, or do you only ever extract the min or max item, as in a heap?
Author
Speed is more of an issue than space. Typically N will be small (<10), but there may be many insertions into the list (with subsequently an equal number of items dropping off the end of the list). As for extractions, the whole list is extracted at completion of the algorithm that requires this list. There are plenty of applications for such a data structure, but at the moment I'm using it for storing the current N best solutions to a search problem... or at least, that's what I want to use it for. I have a current implementation that just uses a fixed length array, but it requires shuffling array elements after every insertion, which seems inefficient to me. I was hoping someone could suggest a 'neater', more efficient data structure using existing storage classes.
Cheers,
Timkin
Cheers,
Timkin
Quote:Original post by Timkin
Speed is more of an issue than space. Typically N will be small (<10), but there may be many insertions into the list (with subsequently an equal number of items dropping off the end of the list). As for extractions, the whole list is extracted at completion of the algorithm that requires this list. There are plenty of applications for such a data structure, but at the moment I'm using it for storing the current N best solutions to a search problem... or at least, that's what I want to use it for. I have a current implementation that just uses a fixed length array, but it requires shuffling array elements after every insertion, which seems inefficient to me. I was hoping someone could suggest a 'neater', more efficient data structure using existing storage classes.
If your algorithm doesn't actually look at the list often [or if it does, but doesn't care about the ordering], you could use the heap functions. As you add items, call push_heap, and if your size is too big call pop_heap. Then, when the algorithm completes, call sort_heap and return the results. This has the benefit that the popped items stick around, so you get that reuse you wanted.
Actually, you might be able to adapt a priority_queue to do this same thing.
The obvious solution is std::[multi]map, with a similar size check when adding elements.
CM
Author
Quote:Original post by Conner McCloud
If your algorithm doesn't actually look at the list often [or if it does, but doesn't care about the ordering], you could use the heap functions.
Not possible. The algorithm is constantly checking to see if it should store its latest output in this set of good solutions. For this, it needs to know what the worst case scenario in the stored set is. The easiest way to do this is to maintain an ordered list and thus comparison is O(1) (first or last item, depending on ordering). The alternative is to store an unordered list but to pay for the search of the largest value stored (if this is not maintained during insertion). Clearly a custom class could manage this, but as I said, I'm trying to avoid reinventing the wheel.
Quote:
Actually, you might be able to adapt a priority_queue to do this same thing.
That's what I've been looking at lately, but creating an adaptor is not what I was looking for ideally.
Quote:
The obvious solution is std::[multi]map, with a similar size check when adding elements.
std::multimap does much of what I want, except for managing its own size. I can see I'm going to have to write a wrapper class if I use one of the STL containers.
I've also realised that there is one problem with fixing the size of the set to N and that is where an N+1'th solution is found that is equally as good as the worst case scenario found so far. I need a way of preferring one over the other, or allowing the set to grow for this case and then shrink again if a better solution is found that removes the N'th and N+1'th solutions. Mmmm... more work. 8(
CM
Quote:Original post by Timkin
Not possible. The algorithm is constantly checking to see if it should store its latest output in this set of good solutions. For this, it needs to know what the worst case scenario in the stored set is. The easiest way to do this is to maintain an ordered list and thus comparison is O(1) (first or last item, depending on ordering). The alternative is to store an unordered list but to pay for the search of the largest value stored (if this is not maintained during insertion). Clearly a custom class could manage this, but as I said, I'm trying to avoid reinventing the wheel.
A wrapper of some sort is going to be neccessary, that's almost certain. Your desires are a little too specific.
If I understand this, all you need to know is the worst case, right? If the new element is worse than the worst case, it is discarded. Otherwise the worst case is removed and the new one added. If this is correct, the heap functions are ideal, because they ensure that the first element in the list is the largest/smallest one. Its everything after the first that is hard to follow.
priority_queue is implemented internally using these same functions. So you'd be reinventing very little, whether you go with a priority_queue or a set. Just wrapping up the container itself and modifying the interface a little.
CM
Oh yeah, of course! I had thought of using a heap earlier, but not using the opposite kind of heap to what you'd expect.
Normally if you want access to the largest item you'd use a max-heap, but in this case you'd use a min-heap, purely for the purposes of finding the smallest item to compare against, to see if it gets replaced or not. Then if it does, you simply swap the min item with the new item and downheap.
Of course, you don't get the largest items in order this way, but it sounds like you only want them sorted at the end, at which point performing a sort, or taking a sorted copy, should be just fine.
Nice one, Conner McCloud!
Normally if you want access to the largest item you'd use a max-heap, but in this case you'd use a min-heap, purely for the purposes of finding the smallest item to compare against, to see if it gets replaced or not. Then if it does, you simply swap the min item with the new item and downheap.
Of course, you don't get the largest items in order this way, but it sounds like you only want them sorted at the end, at which point performing a sort, or taking a sorted copy, should be just fine.
Nice one, Conner McCloud!
Author
I'd sort of arrived at a similar conclusion; that a priority queue was close to what I wanted... but I also wanted some of the functionality of a multimap... so I can see some customisation coming up... unless of course someone knows of an implementation of a heap-style multimap class? To be honest, it won't take long to write a wrapper for a priority queue class, so maybe I'll just go with that.
Thanks for the help guys,
Timkin
Thanks for the help guys,
Timkin
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement