Will a sorted List<string> perform a contains faster

If I perform a Contains() on a list of sorted simple string tags (as opposed to complex sentences), will it run any faster than a randomly sorted one? If not, what is a better data structure. I don't necessarily wan开发者_开发百科t to hash them first in a dictionary ( for performance reasons), but I'm open to suggestions

---

Not if you just sort List<string>, no. You could use List<T>.BinarySearch, but Contains won't do it for you as it doesn't really "know" that your list is sorted. Hashing them is precisely for performance though - HashSet<T> is likely to be your best bet - it will have O(1) Contains performance assuming you don't run into hash collisions.

You could use SortedSet<T> in .NET 4 which is basically a sorted list - you'll get O(log n) performance, but that won't require a hash computation, which could speed things up if your strings are extremely long. (You'd need to benchmark to be sure, of course.) This is broadly equivalent to the "sort and then use binary search" approach, but doesn't rely on you doing things manually.

SortedList<,> and SortedDictionary<,> are also available if you're only using .NET 2, but ideally you should use a set if you don't need a key/value mapping and you don't care about order.