Ney André de Mello Zunino wrote:
Hello.
Given a sorted collection of strings, what would a good (the best?)
strategy be to allow fast access to an item, based on a search substring
which should match the beginning of the searched item? The actual goal
is to implement a functionality similar to that found in help indices,
where one can locate an item by gradually typing its initial characters.
I expect that some kind of tree structure be present in the solution,
but I am not sure.
Since I am multiposting this to comp.programmin g and comp.lang.c++, I
would like to make it on-topic on the latter as well by asking whether
the STL provides any algorithms that could help here, assming, for
instance, that the strings are stored in a std::set or sorted std::vector.
Thank you,
I needed something similar at work. My goal was to lookup an object
based on an object name. My implementation used the STL map<key,object> ,
because the map stores object sorted and is therefore 2ln(n) for lookups.
The map needs a key that supports the < operator in order to sort the
objects. So I created a class called SortableString that implemented
the < operator using the c function strcmp.
So my template instantiation looked like
map<SortableStr ing, Object*> objectMap;
I believe this sort of implementation would work for what you want to
do. First you would populate the map with a set of SortableStrings with
their text set to the topics of your help articles. The objects would
be pointers to your articles.
When the user types in a partial string you would create a temporary
SortableString object with its text set to the what the user typed in.
You can then use the lower_bound() function to locate the first element
greater than your temporary string (which should be the closest match
amoung all your subject headers. Psuedocode below.
class SortableString {
SortableString( char* string);
~SortableString ();
bool operator < (SortableString & other);
};
map<SortableStr ing, ArticleObject*> subjectHeaderMa p;
bool AddSubject(char * subject, ArticleObject* article)
{
SortableString* newSubject = new SortableString( subject);
bool rvalue = objectHeaderMap .insert(map<Sor tableString*,
ArticleObject*> ::value_type(ne wSubject,articl e).second;
return rvalue;
}
bool MatchSubject(ch ar *test_subject, SortableString* found_subject,
ArticleObject** found_article)
{
bool match_found = false;
SortableString* newSubject = new SortableString( subject);
map<SortableStr ing, ArticleObject*> ::Iterator iter;
iter = objectHeaderMap .lower_bound(ne wSubject);
if (iter != objectHeaderMap .end())
{
*found_subject = iter->first;
*found_article = iter->second;
match_found = true;
}
delete newSubject;
return match_found;
}
