Partial string search in boost::multi_index_container

Question

I have a struct to store info about persons and multi_index_contaider to store such objects. Mult-index uses for search by different criteria.

I've added several persons into container and want to find person by lastname. It works great, if I use whole lastname. But it returns nothig if I try to find person by a part of a lastname (first letters of a lastname).

As you know, partial string search works as a charm for std::set<string>. So I've only wraped strings by a struct and lost that functionality.

Here is compilable code:

#include <iostream>
#include <string>
#include <algorithm>
#include <set>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>

#define DEFAULT_ADDRESS "Moscow"
#define DEFAULT_PHONE "11223344"

typedef unsigned int uint;

using namespace boost;
using namespace boost::multi_index;

struct person
{
    std::string m_first_name;
    std::string m_last_name;
    std::string m_third_name;
    std::string m_address;
    std::string m_phone;

    person();
    person(std::string f, std::string l, std::string t = "", std::string a = DEFAULT_ADDRESS, std::string p = DEFAULT_PHONE) : 
        m_first_name(f), m_last_name(l), m_third_name(t), m_address(a),
        m_phone(p) { }

    virtual ~person()
        { /*std::cout << "Destructing person..." << std::endl;*/ }

    person& operator=(const person& rhs);
};

typedef multi_index_container<
    person,
    indexed_by<
        ordered_unique<identity<person> >,
        ordered_non_unique<
            composite_key<
                person,
                member<person, std::string, &person::m_last_name>,
                member<person, std::string, &person::m_first_name>,
                member<person, std::string, &person::m_third_name>
            >
        >
    >
> persons_set;

person& person::operator=(const person &rhs)
{
    m_first_name = rhs.m_first_name;
    m_last_name = rhs.m_last_name;
    m_third_name = rhs.m_third_name;
    m_address = rhs.m_address;
    m_phone = rhs.m_phone;
    return *this;
}

bool operator<(const person &lhs, const person &rhs)
{
    if(lhs.m_last_name == rhs.m_last_name)
    {
        if(lhs.m_first_name == rhs.m_first_name)
            return (lhs.m_third_name < rhs.m_third_name);

        return (lhs.m_first_name < rhs.m_first_name);
    }
        return (lhs.m_last_name < rhs.m_last_name);
}

std::ostream& operator<<(std::ostream &s, const person &rhs)
{
    s << "Person's last name: " << rhs.m_last_name << std::endl;
    s << "Person's name: " << rhs.m_first_name << std::endl;
    if (!rhs.m_third_name.empty())
        s << "Person's third name: " << rhs.m_third_name << std::endl;
    s << "Phone: " << rhs.m_phone << std::endl;
    s << "Address: " << rhs.m_address << std::endl << std::endl;
    return s;
}

struct comp_persons
{
    bool operator()( const person& p1, const person& p2) const
    {
        if (p2.m_last_name.empty()) return false;
        return ( p1.m_last_name.find(p2.m_last_name) == 0 );
    }
};



int main()
{    
    persons_set my_set;

    persons_set::nth_index<0>::type &general_index = my_set.get<0>(); // shortcut to the 1st index
    persons_set::nth_index<1>::type &names_index = my_set.get<1>();   // shortcut to the 2nd index

    // adding persons
    general_index.insert(person("Alex", "Johnson", "Somename"));
    general_index.insert(person("Alex", "Goodspeed"));
    general_index.insert(person("Peter", "Goodspeed"));
    general_index.insert(person("Akira", "Kurosava"));

    // search via 2nd index (based on last_name)
    std::pair<persons_set::nth_index<1>::type::const_iterator, persons_set::nth_index<1>::type::const_iterator> 
        n_it = names_index.equal_range("Goodspeed");

    // this finds nothing
    /*std::pair<persons_set::nth_index<1>::type::const_iterator, persons_set::nth_index<1>::type::const_iterator> 
        n_it = names_index.equal_range("Goodspe");*/

    // idea by Kirill V. Lyadvinsky. This code crashes on the start.
    // I guess because behaviour of comp_persons differs from default less<> or reloaded operator <
    /*std::pair<persons_set::nth_index<1>::type::const_iterator, persons_set::nth_index<1>::type::const_iterator> 
        n_it = std::equal_range(names_index.begin(), names_index.end(), person("Alex", "Goodspe"), comp_persons());*/

    std::copy( n_it.first ,n_it.second,
        std::ostream_iterator<person>(std::cout));

    return 0;

}

Answer 1

You could use equal_range or lower_bound with custom comparison functor. It could look like the following (not tested):

struct comp_substr {
  bool operator()( const char* input, const std::string& s) const {
    if ( s.empty() ) return false;
  return ( s.find( input ) == 0 );
}

// ...
// use it as follows
n_it = names_index.equal_range( "Good", comp_substr() );

Answer 2

Inspired by Kirill V Lyadvinsky!

Here is correct functor:

struct comp_substr
{
    bool operator()( const char* in, const std::string s) const 
    {
        if (s.empty()) return false;
        return (!(s.find(in) == 0));
    }
    bool operator()(const std::string s, const char* in) const 
    {
        if (s.empty()) return false;
        return (!(s.find(in) == 0));
    }
};

Usage is the same:

n_it = names_index.equal_range( "Good", comp_substr() );

Answer 3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool str_match(char* str,char* ser_str)
{
    char *tmp = ser_str;
    if(!str || !ser_str)
        return 0;
    while(*str != '\0')
    {
        if(*tmp != '*')
        {
            if(*tmp != *str)
            {
                str++;
                if(*str == '\0')
                    return 0;
                else
                    continue;
            }
        }
        else
        {

            while(*tmp == '*')
            {
                tmp++;
            }
            if(*tmp == '\0')
                return 1;
            str_match(str,tmp);
        }

        tmp++;
        str++;
        if(*tmp == '\0')
            return 1;
    }
    return 0;
}

int main(int argc, _TCHAR* argv[])
{
    char str[10][50] = {{"sdeedddd"},{"xaasass"},{"aasaddddfc"},{"wewwwwwwrrr"},{"dddddddhhhhhhh"},
    {"eeeeeessss"},{"asaqqqqqqqq"},{"qqqqqqqq"},{"eeeeeeeeee"},{"xaasa"}};
    char ser_str[50] = "*aas*";
    for(int i=0;i<10;++i)
    {
        if(str_match(str[i],ser_str))
        {
            printf("%s\n",str[i]);
        }
    }
    return 0;
}