Container for database-like searches

Question

I'm looking for some STL, boost, or similar container to use the same way indexes are used in databases to search for record using a query like this:

select * from table1 where field1 starting with 'X';

or

select * from table1 where field1 like 'X%';

I thought about using std::map, but I cannot because I need to search for fields that "start with" some text, and not those that are "equal to". Beside that, I need it to work on multiple fields (each "record" has 6 fields, for example), so I would need a separate std::map for each one.

I could create a sorted vector or list and use binary search (breaking the set in 2 in each step by reading the element in the middle and seeing if it's more or less than 'X'), but I wonder if there is some ready-made container I could use without reinventing the wheel?

Answer 1

std::map is fine, or std::set if there's no data other than the string. Pass your prefix string into lower_bound to get the first string which sorts at or after that point. Then iterate forward through the map until you hit the end or find an element which doesn't begin with your prefix.

Answer 2

Boost.Multi-Index allows you to manage with several index and it implements the lower_bound as for std::set/map. You will need to select the index corresponding to the field and then do as if it was a map or a set.

Next follows a generic function that could be used to get a couple of iterators, the fist to the first item starting with a given prefix, the second the first item starting with the next prefix, i.e. the end of the search

template <typename SortedAssociateveContainer>
std::pair<typename SortedAssociateveContainer::iterator, 
          typename SortedAssociateveContainer::iterator> 
starts_with(
  SortedAssociateveContainer const& coll, 
  typename SortedAssociateveContainer::key_type const& k)
{
  return make_pair(coll.lower_bound(k), 
                   coll.lower_bound(next_prefix(k));
}

where

• next_prefix gets the next prefix using lexicographic order based on the SortedAssociateveContainer comparator (of course this function needs more arguments to be completely generic, see the question).

The result of starts_with can be used on any range algorithm (see Boost.Range)