Reverse search & find_next function in Multi_Index container

Question

I have a boost multi_index container like this:

typedef multi_index_container<
    MyData, 
        indexed_by<    
            random_access<>,  // keep insertion order
            ordered_non_unique< member<MyData, time_t, &MyData::timestamp> >
        > 
> myContType;

typedef myContType::nth_index<1>::type myContType_by_time;

and an search method:

unsigned long searchByTimestamp(time_t timestamp) 
{   

    myContType_by_time& idIndex = myCont.get<1>();
    myContType_by_time::iterator itTime = idIndex.find(timestamp);

    if (itTime == idIndex.end())
        return 0;

    // change the index from timestamp to insertionoder(id) 
    myContType::const_iterator itId = myCont.project<0>(itTime);

    return itTime->id; 
} 

I do the search with timestamp(get<1> index) and its worked but it started the search from the first (oldest) data. I want to do it starting from the last added(newest) data according to the insertion order (get<0> index). I tried that code but it doesn't worked.

myCont.rearrange(get<0>(myCont).rbegin());

1st question: Is there a way to start the search from the last entered data (according to the INSERTION ORDER not TIMESTAMP I mean get<0> index)

2nd question: If the found data is not the one that I want how can I continue searching from the current position/index? I mean is there a method like find_next? (I couldn't find it on docs)

I am working on Visual Studio 2008 with boost version 1.47.0.

Thanks.

Answer 1

You should probably just use std::find from <algorithm>, together with reverse iterators from the first index:

unsigned long searchByTimestamp(Time_t timestamp) 
{   
    auto& idIndex = myCont.get<0>();

    auto itTime = std::find_if(
                idIndex.rbegin(), idIndex.rend(), 
                [=](MyData const& item) { return item.timestamp == timestamp; }
            );

    if (itTime == idIndex.rend())
        return 0;

    return itTime->id; 
} 

Note: If you want to "project" a reverse iterator to a (forward) iterator, use .base() on the reverse iterator.

See it Live On Coliru

---

Now, I don't really know what you needed the continue searching from the "current" position funcitonality for (I mean, find either returns the match, or rend(), so there would be nothing to continue for). However, otherwise, you could do stuff like (see it Live On Coliru as well :)

unsigned long searchByTimestamp(Time_t timestamp) 
{   
    auto& idIndex = myCont.get<0>();

    auto current = std::find_if(idIndex.rbegin(), idIndex.rend(), 
            [=](MyData const& item) { return item.timestamp >= timestamp; });

    if (current != idIndex.rend())
    {
        bool some_extra_condition = current->timestamp == timestamp; // exact match?

        if (some_extra_condition)
            return current->id; // we have an exact match
    } else
    {
        // otherwise look for the next item that has an id divisible by 3 (3,6,9,...)
        auto alternative = std::find_if(current, idIndex.rend(), 
            [=](MyData const& item) { return (item.id % 3) == 0; });

        if (alternative != idIndex.rend())
            return alternative->id;
    }

    return 0;
} 

I made up fully silly examples of 'alternative' matching predicates. As you can see, it's all run-of-the-mill STL algorithm usage. This is possible due to algorithms being decoupled from containers by way of iterators.

Full Code

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

using namespace boost::multi_index;
static int idgen = 0;

enum Time_t { last_month, last_week, yesterday, today, tomorrow };
std::ostream& operator<<(std::ostream& os, Time_t tt) {
    switch(tt)
    {
        case last_month: return os << "last_month";
        case last_week:  return os << "last_week";
        case yesterday:  return os << "yesterday";
        case today:      return os << "today";
        case tomorrow:   return os << "tomorrow";
        default: return os << "?";
    };
}

struct MyData
{
    int id = ++idgen;

    MyData(Time_t timestamp) : timestamp(timestamp) {}
    Time_t timestamp;

    friend std::ostream& operator<<(std::ostream& os, MyData const& md)
    {
        return os << "(id:" << md.id << ", timestamp:" << md.timestamp << ")";
    }
};

typedef multi_index_container<
    MyData, 
        indexed_by<    
            random_access<>,  // keep insertion order
            ordered_non_unique< member<MyData, Time_t, &MyData::timestamp> >
        > 
> myContType;

typedef myContType::nth_index<1>::type myContType_by_time;

myContType myCont;

unsigned long searchByTimestamp(Time_t timestamp) 
{   
    auto& idIndex = myCont.get<0>();

    auto itTime = std::find_if(
                idIndex.rbegin(), idIndex.rend(), 
                [=](MyData const& item) { return item.timestamp == timestamp; }
            );

    if (itTime == idIndex.rend())
        return 0;

    return itTime->id; 
} 

#include <iostream>

int main()
{
    myCont.emplace_back(Time_t(last_week));
    myCont.emplace_back(Time_t(tomorrow));
    myCont.emplace_back(Time_t(last_month));
    myCont.emplace_back(Time_t(yesterday));

    std::cout << "Insertion order:\n";
    for (auto const& item : myCont)
        std::cout << item << "\n";

    std::cout << searchByTimestamp(today)     << "\n";
    std::cout << searchByTimestamp(last_month) << "\n";
}

Answer 2

Have you considered using upper_bound more or less like this?

unsigned long searchByTimestamp(time_t timestamp) 
{   

    myContType_by_time& idIndex = myCont.get<1>();
    myContType_by_time::iterator itTime = idIndex.upper_bound(timestamp);

    if (itTime == idIndex.end())
        return 0;

    if (itTime != idIndex.begin()){
       myContType_by_time::iterator prev = itTime;
       --prev;
       if(prev->timestamp == timestamp) itTime=prev;
    }

    // change the index from timestamp to insertionoder(id) 
    myContType::const_iterator itId = myCont.project<0>(itTime);

    return itTime->id; 
}