C++ :: Fastest Comparison Algorithm Based On A Predefined Container?

Suppose you have defined a container of elements and you want do define a comparison function between elements based on the ordering of the elements in that container. What algorithm for the comparison would be the most efficient?

Example:
master = {tom, sam, mary, sally, bert, frank}
subset = {bert, sam, mary, tom}
goal: change subset to {tom, sam, mary, bert}

My current idea is to simply iterate from the beginning of the container, and whichever of the two elements is found first is the lesser (assuming the second is not the same as the first). It seems kind of naïve though. Any better performing algorithm? This is what I have so far:

#include <iostream>
#include <iterator>
#include <list>
#include <vector>
#include <stdexcept>
#include <algorithm>

[code]....

Would perhaps forcing the container to have a random access iterator, like vector, and then writing a specialized comparison function based on that perform even faster? Or perhaps force the container to be a map to integers, and compare the elements by comparing the integer mapped values?