Wildcard search inside a Boost.MultiIndex data structure?

Question

I'm trying to optimize my application by reducing round-trips to my database. As part of that effort, I've been moving some of the tables into memory, storing them as Boost.MultiIndex containers.

As a side-effect of this process, I've lost the ability to do wild-card matching on my strings. For example, when the table was stored in MySQL, I could do this:

SELECT * FROM m_table WHERE myString LIKE "foo%"

However, since I'm now using a Boost.MultiIndex container with a key of myString, it seems I've lost that ability.

Obviously, I can use the equal_range() function in order to find all entries that match a specific string exactly:

std::pair< typename T::template index<by_name>::type::iterator,
           typename T::template index<by_name>::type::iterator > p
  = m_table.get<by_name>().equal_range(myString);

while (p.first != p.second )
{
  // do something with the EXACT matching entry
  ++p.first;
}

But it seems like the only way to do a wild-card match is to walk the entire structure and compare each key to a boost::regex with boost::regex_match().

std::pair< typename T::template index<by_name>::type::iterator,
           typename T::template index<by_name>::type::iterator > p
  = std::make_pair(m_table.get<by_name>().begin(),m_table.get<by_name>().end());

while (p.first != p.second )
{
  boost::regex e(myRegex);
  if ( boost::regex_match(p.first->myString, e ) )
  {
     // Do something with the REGEX matching entry
  }
  ++p.first;
}

Is there a better way?

Answer 1

Well, first you don't actually have to use a boost::regex, if the wildcard is simple enough, you can get away by rolling you own unary operator. I would note that Boost.Regex is one of the few part of the library which actually requires to be linked (not header-only).

As for the problem of walking the whole structure, I am sorry but there is not much one can do you here... if you don't know the searches in advances.

If you know the parameters that you would be looking for in advance, then you can create a special view of the Multi-Index container suited to perform this task with a dedicated comparator/hasher (for example, one that only takes into account the first 3 characters).

If you were hoping for more, please provide more information regarding the kind of wildcards you want to use and the circumstances.

Answer 2

In your specific case, you can do a lower_bound("foo") and then walk forwards looking for matches, until you hit something that doesn't match or reach the end of the container. I don't think there is a general way to do this lookup though.