Обратный поиск & amp; функция find_next в контейнере Multi_Index
У меня есть контейнер для повышения multi_index, как это:
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;
и метод поиска:
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;
}
Я делаю поиск с отметкой времени (get<1> index) и это сработало, но оно начало поиск по первым (самым старым) данным. Я хочу сделать это, начиная с последних добавленных (новейших) данных в соответствии с порядком вставки (get<0> index). Я пробовал этот код, но он не работал.
myCont.rearrange(get<0>(myCont).rbegin());
1-й вопрос: Есть ли способ начать поиск по последним введенным данным (в соответствии с ПОРЯДОК ВСТАВКИ, а не TIMESTAMP, я имею в виду получить<0> индекс)
2-й вопрос: Если найденные данные не являются теми, которые мне нужны, как я могу продолжить поиск с текущей позиции / индекса? Я имею в виду, есть ли такой метод, как find_next? (Я не мог найти это на документах)
Я работаю над Visual Studio 2008 с буст-версией 1.47.0.
Благодарю.
Решение
Вы должны, вероятно, просто использовать std::find от <algorithm>вместе с обратными итераторами из первого индекса:
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;
}
Примечание. Если вы хотите «спроецировать» обратный итератор на (прямой) итератор, используйте .base() на обратном итераторе.
Видеть это Жить на Колиру
Теперь я не знаю, что вам нужно continue searching from the "current" position Функциональность для (я имею в виду, найти либо возвращает совпадение, либо rend()так что дальше нечего было бы продолжать). Тем не менее, в противном случае, вы могли бы сделать что-то вроде (увидеть это Жить на Колиру также 🙂
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;
}
Я придумал совершенно глупые примеры «альтернативных» предикатов сопоставления. Как видите, это все заурядный Использование алгоритма STL. Это возможно благодаря тому, что алгоритмы отделены от контейнеров с помощью итераторов.
Полный код
#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";
}
Другие решения
Рассматривали ли вы использование upper_bound примерно так?
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;
}