The Boost.Regex algorithms and iterators are all iterator-based, with convenience overloads of the algorithms provided that convert standard library string types to iterator pairs internally. If you want to search a non-standard string type then the trick is to convert that string into an iterator pair: so far I haven't come across any string types that can't be handled this way, even if they're not officially iterator based. Certainly any string type that provides access to it's internal buffer, along with it's length, can be converted into a pair of pointers (which can be used as iterators).

Some non-standard string types are sufficiently common that wrappers have been provided for them already: currently this includes the ICU and MFC string class types.