Dmitri Zhukov wrote:
Hello everyone,
I am implementing software which has a medium sized number of text strings
(max 100K) which are represented in a listbox.
I want user to be able to search the string by typing the first letters of
the record and showing coinciding record if any (similar to quickserach
functionality of Norton/Total commander).
So i guess I need some kind of hasing algorithm to be able to find string
by its prefix. Any recommendations ?
Dmitri Zhukov.
Maybe the following code has some ideas that you find useful:
#include <string>
#include <set>
typedef std::string String;
typedef std::set< String > StringSet;
typedef StringSet::cons t_iterator StringSetConstI terator;
StringSetConstI terator
prefix_begin ( StringSet const & the_set,
String const & prefix ) {
return( std::lower_boun d( the_set.begin() ,
the_set.end(),
prefix ) );
}
StringSetConstI terator
prefix_end ( StringSet const & the_set,
String prefix ) {
// this breaks if the prefix is empty:
++ prefix[ prefix.length()-1 ];
return( std::lower_boun d( the_set.begin() ,
the_set.end(),
prefix ) );
}
#include <iostream>
int main ( void ) {
StringSet the_set;
the_set.insert( String( "aaa" ) );
the_set.insert( String( "hell" ) );
the_set.insert( String( "hello" ) );
the_set.insert( String( "help" ) );
the_set.insert( String( "zzz" ) );
{
String prefix ("hel" );
StringSetConstI terator from = prefix_begin( the_set, prefix );
StringSetConstI terator to = prefix_end( the_set, prefix );
for ( StringSetConstI terator iter = from; iter != to; ++iter ) {
std::cout << *iter << "\n";
}
}
std::cout << "\n";
{
String prefix ("hell" );
StringSetConstI terator from = prefix_begin( the_set, prefix );
StringSetConstI terator to = prefix_end( the_set, prefix );
for ( StringSetConstI terator iter = from; iter != to; ++iter ) {
std::cout << *iter << "\n";
}
}
}
Best
Kai-Uwe Bux
