Prefix search through list/dictionary using .NET S

Question

I was wondering if .NET offers any standard functionality for doing a prefix search through a list or a dictionary object. I came across the StringDictionary, but couldn't figure out if it can do that for me.

And if it can do a prefix search, can it also do substring search or let me search using something like a regular expression?

Thanks in advance.

Answer 1

StringDictionary is merely a hash table where the keys and values are strings. This existed before generics (when Dictionary<string, string> was not possible).

The data structure that you want here is a trie. There are implementations on CodeProject:

1. Phone Directory Implementation Using TRIE
2. A Reusable Prefix Tree using Generics in C# 2.0

Or, if you're that kind of guy, roll your own (see CLRS).

Answer 2

I made a generic implementation of this available here.

Since string implements IEnumerable<char>, you can use it with char as parameter for TKeyElement.

Answer 3

I don't believe StringDictionary supports a prefix search, but if you use a SortedList<,> you can binary search through the range of keys until you find the first entry before and after your prefix.

Answer 4

I think the StringDictionary is old school (pre-generics). You should probably use a Dictionary(Of String, String) instead because it implements IEnumerable (think LINQ). One extremely lame thing about StringDictionary is that it's case-insensitive.