best way to search through 'history'

[anykey]

Here is a summary of my question:
I have a particular class

class Combination;

there is a function which generates objects of this class:

Combination makeCombination();

there is a function which evaluates Combination objects acc. to some criteria:

int scoreCombination(Combination combo);

it is possible that makeCombination() is going to generate same Combination objects and get into a loop. So I want to make a 'history' of previously created Combo objects and check if an object is in history before i pass it to score function. History should store the last max_size objects generated.

now I could do it like this:

std::list<Combination> history;

void add_to_history(Combination c) {
  if(history.size() == max_size) {
    history.pop_front();
  }
  history.push_back(c);
}

and then search for it something like this:

Combination c;

std::list<Combination>::iterator it;
it = find(history.begin(), history.end(), c);
if(it != history.end())  int score = scoreCombination(c);

this is ok, but find() can work a bit slow with lists and it could become a problem if max_size gets large. If i declare history as std::set<Combination> searching through it will be a bit faster but I have no idea how to track which elements have been inserted into the set first. Any ideas for a more efficient way of implementing what I want to do would be much appreciated.
Thanks

[Daved]

Basically you have two different keys - insertion order and whatever makes a Combination unique. I believe there is a Boost container that allows two fast lookups based on two different keys. Or you could make your own by keeping two containers. It appears that Combination is a pretty lightweight class since you are moving it around by value. In that case, you might simply have a list and a set. The list would maintain order and the set would allow lookup. When something needs to be removed from the list, it would be easy to look it up in the set and remove it from there.

If you require removal based on object value, or if you require modification of the state of existing objects, then the solution is slightly more complicated. You could store the list iterators in the set, and create a sorting function to use the Combination value that the iterator points to. Since list iterators don't get invalidated unless they are removed from the list, this would work as long as you always removed the iterator from the set before removing the object from the list.

Those are just a couple ideas.

[anykey]

Daved, thanks for the quick reply.
I'm unfortunately not very familiar with boost, but I like the idea with a list and a set. I think I could do something like this.
As far as history is concerned I don't need to know the value of the Combination objects, I only need to keep the last n of them in history.
Once again, thanks.