存储 references/pointers 以提升 MultiSet 索引
Storing references/pointers to Boost MultiSet indexes
我正在尝试构建两个 类 Collection 和 CollectionView，这是对 Boost.MultiIndex 的抽象。这个想法有点简单：将 Collection 类型的实例提供给 CollectionView，它将处理渲染。 Collection 添加了一个用于添加或删除项目的接口，这反过来会向 CollectionView 发出信号，表明它需要做一些工作。
类 的摘录如下所示：
template<class ItemType, typename ... Indexes>
struct Collection {
using t_container = multi_index_container<ItemType, indexed_by<Indexes...>>;
t_container itemSet;
}
template<class TCollectionType>
struct CollectionView {
// Imagine that this view also keeps track of which
// item in col corresponds to which item on the screen
TCollectionType& col;
}
这个想法是 API 的用户可以完全控制可以索引哪些列，并且在编译期间尽可能多地验证其正确性。
但是如果我们想象一下 CollectionView 有一个 UI 来让用户确定排序（来自 pre-defined 集合，因为它必须是已知的在编译时），实现的方式有点问题。
- CollectionView 会理想地遍历 collection，知道如何到达正确的索引
- 迭代索引可能会随着对用户输入的响应而改变
我以某种方式必须存储当前迭代索引是什么，实际上也可以从 Collection 的 itemSet 中访问它。
理想情况下，我会将以下 属性 添加到 Collection：
struct CollectionView {
t_index_type currentIndex { col.itemSet.get<0>() }
void Build() {
for (const auto& item : currentIndex) {
// Do stuff here
}
}
}
我无法弄清楚 t_index_type 可能是什么（如果有的话），因为每个索引（已排序、ordered_non_unique 等）都有自己的类型。我可以强加给用户实现 void Iterate(function<void(const ItemType&>)，但这会给 API.
的用户强加更多的代码
我是走到了死胡同，还是我的 templating-fu 不够好？
编辑：
一种可能的解决方案是像这样使用模板：
// Previous definitions omitted
struct Collection {
using t_callback_fn = std::function<void(const ItemType&)>;
using t_iter_fn = std::function<void(t_callback_fn)>;
void Iterate(t_callback_fn cb) const
{
iterFn(cb);
}
template<int N, bool reverse = false>
void SetSortIndex()
{
iterFn = [this](t_callback_fn fn) {
// The ideal would be to store this index as part of the class itself!
auto& index = itemSet.template get<N>();
if (reverse) {
for (auto it { index.rbegin() }; it != index.rend(); ++it)
fn(*it);
} else {
for (const auto &item : index)
fn(item);
}
};
}
}
并使用容器：
col.SetSortIndex<0, true>;
col.Iterate([](const auto& it) { std::cout << it << '\n;};
但不是很好。
听起来您真的会被来自 Boost Multi Index (BMI) 的 random_access_index 服务。
您可以 rearrange it 以任何您希望的方式进行。因此，即使您想让用户手动重新排列事物，例如他们
- 添加一个元素，它显示为最后一项，而不管集合中其余元素的顺序如何
- select 与 BMI 指数之一不完全匹配的自定义排序顺序
那就可以了。
As an aside: note that you can also use BMI containers to merely index non-owned or shared elements. The implementation allows the element type to be T*, T const*, std::reference_wrapper, shared_ptr etc. without any other change to the functionality. Note that it uses generic pointer_traits for this so you can even use std::reference_wrapper<std::shared_ptr<T const*> > and it would still work.
This is not related to the answer but does resonate with the concept of "external views" as you were contemplating.
演示
假设我们将 random_access 索引透明地添加到您的容器中：
template<class ItemType, typename ... Indexes>
class Collection {
template <typename> friend struct CollectionView;
struct View;
using t_container = bmi::multi_index_container<ItemType,
bmi::indexed_by<
Indexes...,
bmi::random_access<bmi::tag<View> > // additional!
>
>;
private:
t_container itemSet;
};
现在我们可以定义视图以基本上处理该额外索引：
template<class TCollectionType>
struct CollectionView {
using MIC = typename TCollectionType::t_container;
using Tag = typename TCollectionType::View;
using Index = typename MIC::template index<Tag>::type;
TCollectionType& col;
Index& idx { col.itemSet.template get<Tag>() };
// Imagine that this view also keeps track of which
// item in col corresponds to which item on the screen
//
explicit CollectionView(TCollectionType& col) : col(col) {}
auto begin() const { return idx.begin(); }
auto end() const { return idx.end(); }
};
现在，我将添加一些排列功能，均按现有索引排列：
template <int n> void arrange_by() {
idx.rearrange(col.itemSet.template get<n>().begin());
}
或按用户指定的免费比较函数排列：
template <typename Cmp> void arrange_by(Cmp cmp) {
std::vector<std::reference_wrapper<T const> > v(idx.begin(), idx.end());
std::sort(v.begin(), v.end(), cmp);
idx.rearrange(v.begin());
}
Live On Coliru
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <iomanip>
namespace bmi = boost::multi_index;
template<class ItemType, typename ... Indexes>
class Collection {
template <typename> friend struct CollectionView;
struct View;
using t_container = bmi::multi_index_container<ItemType,
bmi::indexed_by<
Indexes...,
bmi::random_access<bmi::tag<View> > // additional!
>
>;
public:
explicit Collection(std::initializer_list<ItemType> init) : itemSet(init) {}
bool insert(ItemType const& item) {
return itemSet.insert(item).second;
}
template <int index = 0, typename K>
bool erase(K const& key) {
return itemSet.template get<index>().erase(key);
}
private:
t_container itemSet;
};
template<class TCollectionType>
struct CollectionView {
using MIC = typename TCollectionType::t_container;
using T = typename MIC::value_type;
using Tag = typename TCollectionType::View;
using Index = typename MIC::template index<Tag>::type;
TCollectionType& col;
Index& idx { col.itemSet.template get<Tag>() };
// Imagine that this view also keeps track of which
// item in col corresponds to which item on the screen
//
explicit CollectionView(TCollectionType& col) : col(col) {}
template <int n> void arrange_by() {
idx.rearrange(col.itemSet.template get<n>().begin());
}
template <typename Cmp> void arrange_by(Cmp cmp) {
std::vector<std::reference_wrapper<T const> > v(idx.begin(), idx.end());
std::stable_sort(v.begin(), v.end(), cmp);
idx.rearrange(v.begin());
}
auto begin() const { return idx.begin(); }
auto end() const { return idx.end(); }
};
/// example application
struct Item {
int id;
std::string name;
// some natural ordering just for demo
bool operator<(Item const& other) const
{ return std::tie(id, name) < std::tie(other.id, other.name); }
bool operator>(Item const& other) const
{ return std::tie(id, name) > std::tie(other.id, other.name); }
};
using Items = Collection<Item,
bmi::ordered_unique<bmi::member<Item, int, &Item::id> >,
bmi::ordered_unique<bmi::member<Item, std::string, &Item::name> > >;
int main() {
Items items {
{ 3, "three" },
{ 1, "one" },
{ 5, "five" },
{ 4, "four" },
{ 2, "two" },
{ 6, "six" },
};
CollectionView view(items);
auto dump = [&view](auto caption) {
std::cout << std::setw(12) << caption << ": ";
for (auto const& [id, name] : view)
std::cout << " { " << id << ", " << std::quoted(name) << " }";
std::cout << "\n";
};
dump("default");
view.arrange_by<1>(); // by name
dump("by name");
view.arrange_by<0>(); // by id
dump("by id");
view.arrange_by(std::less<Item>{});
dump("std::less");
view.arrange_by(std::greater<Item>{});
dump("std::greater");
auto funky = [](Item const& a, Item const& b) {
return (a.name.length() - a.id) < (b.name.length() - b.id);
};
view.arrange_by(funky);
dump("funky");
// mutations are fine
if (items.erase(1))
std::cout << "Removed 1\n";
dump("funky");
if (items.insert(Item { 42, "answer" }))
std::cout << "Inserted the answer (appears at end)\n";
dump("funky");
view.arrange_by<1>();
dump("by name");
}
版画
default: { 3, "three" } { 1, "one" } { 5, "five" } { 4, "four" } { 2, "two" } { 6, "six" }
by name: { 5, "five" } { 4, "four" } { 1, "one" } { 6, "six" } { 3, "three" } { 2, "two" }
by id: { 1, "one" } { 2, "two" } { 3, "three" } { 4, "four" } { 5, "five" } { 6, "six" }
std::less: { 1, "one" } { 2, "two" } { 3, "three" } { 4, "four" } { 5, "five" } { 6, "six" }
std::greater: { 6, "six" } { 5, "five" } { 4, "four" } { 3, "three" } { 2, "two" } { 1, "one" }
funky: { 4, "four" } { 2, "two" } { 3, "three" } { 1, "one" } { 6, "six" } { 5, "five" }
Removed 1
funky: { 4, "four" } { 2, "two" } { 3, "three" } { 6, "six" } { 5, "five" }
Inserted the answer (appears at end)
funky: { 4, "four" } { 2, "two" } { 3, "three" } { 6, "six" } { 5, "five" } { 42, "answer" }
by name: { 42, "answer" } { 5, "five" } { 4, "four" } { 6, "six" } { 3, "three" } { 2, "two" }
我正在尝试构建两个 类 Collection 和 CollectionView，这是对 Boost.MultiIndex 的抽象。这个想法有点简单：将 Collection 类型的实例提供给 CollectionView，它将处理渲染。 Collection 添加了一个用于添加或删除项目的接口，这反过来会向 CollectionView 发出信号，表明它需要做一些工作。
类 的摘录如下所示：
template<class ItemType, typename ... Indexes>
struct Collection {
using t_container = multi_index_container<ItemType, indexed_by<Indexes...>>;
t_container itemSet;
}
template<class TCollectionType>
struct CollectionView {
// Imagine that this view also keeps track of which
// item in col corresponds to which item on the screen
TCollectionType& col;
}
这个想法是 API 的用户可以完全控制可以索引哪些列，并且在编译期间尽可能多地验证其正确性。
但是如果我们想象一下 CollectionView 有一个 UI 来让用户确定排序（来自 pre-defined 集合，因为它必须是已知的在编译时），实现的方式有点问题。
- CollectionView 会理想地遍历 collection，知道如何到达正确的索引
- 迭代索引可能会随着对用户输入的响应而改变
我以某种方式必须存储当前迭代索引是什么，实际上也可以从 Collection 的 itemSet 中访问它。
理想情况下，我会将以下 属性 添加到 Collection：
struct CollectionView {
t_index_type currentIndex { col.itemSet.get<0>() }
void Build() {
for (const auto& item : currentIndex) {
// Do stuff here
}
}
}
我无法弄清楚 t_index_type 可能是什么（如果有的话），因为每个索引（已排序、ordered_non_unique 等）都有自己的类型。我可以强加给用户实现 void Iterate(function<void(const ItemType&>)，但这会给 API.
我是走到了死胡同，还是我的 templating-fu 不够好？
编辑：
一种可能的解决方案是像这样使用模板：
// Previous definitions omitted
struct Collection {
using t_callback_fn = std::function<void(const ItemType&)>;
using t_iter_fn = std::function<void(t_callback_fn)>;
void Iterate(t_callback_fn cb) const
{
iterFn(cb);
}
template<int N, bool reverse = false>
void SetSortIndex()
{
iterFn = [this](t_callback_fn fn) {
// The ideal would be to store this index as part of the class itself!
auto& index = itemSet.template get<N>();
if (reverse) {
for (auto it { index.rbegin() }; it != index.rend(); ++it)
fn(*it);
} else {
for (const auto &item : index)
fn(item);
}
};
}
}
并使用容器：
col.SetSortIndex<0, true>;
col.Iterate([](const auto& it) { std::cout << it << '\n;};
但不是很好。
听起来您真的会被来自 Boost Multi Index (BMI) 的 random_access_index 服务。
您可以 rearrange it 以任何您希望的方式进行。因此，即使您想让用户手动重新排列事物，例如他们
- 添加一个元素，它显示为最后一项，而不管集合中其余元素的顺序如何
- select 与 BMI 指数之一不完全匹配的自定义排序顺序
那就可以了。
As an aside: note that you can also use BMI containers to merely index non-owned or shared elements. The implementation allows the element type to be T*, T const*, std::reference_wrapper, shared_ptr etc. without any other change to the functionality. Note that it uses generic
pointer_traitsfor this so you can even usestd::reference_wrapper<std::shared_ptr<T const*> >and it would still work.This is not related to the answer but does resonate with the concept of "external views" as you were contemplating.
演示
假设我们将 random_access 索引透明地添加到您的容器中：
template<class ItemType, typename ... Indexes>
class Collection {
template <typename> friend struct CollectionView;
struct View;
using t_container = bmi::multi_index_container<ItemType,
bmi::indexed_by<
Indexes...,
bmi::random_access<bmi::tag<View> > // additional!
>
>;
private:
t_container itemSet;
};
现在我们可以定义视图以基本上处理该额外索引：
template<class TCollectionType>
struct CollectionView {
using MIC = typename TCollectionType::t_container;
using Tag = typename TCollectionType::View;
using Index = typename MIC::template index<Tag>::type;
TCollectionType& col;
Index& idx { col.itemSet.template get<Tag>() };
// Imagine that this view also keeps track of which
// item in col corresponds to which item on the screen
//
explicit CollectionView(TCollectionType& col) : col(col) {}
auto begin() const { return idx.begin(); }
auto end() const { return idx.end(); }
};
现在，我将添加一些排列功能，均按现有索引排列：
template <int n> void arrange_by() {
idx.rearrange(col.itemSet.template get<n>().begin());
}
或按用户指定的免费比较函数排列：
template <typename Cmp> void arrange_by(Cmp cmp) {
std::vector<std::reference_wrapper<T const> > v(idx.begin(), idx.end());
std::sort(v.begin(), v.end(), cmp);
idx.rearrange(v.begin());
}
Live On Coliru
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <iomanip>
namespace bmi = boost::multi_index;
template<class ItemType, typename ... Indexes>
class Collection {
template <typename> friend struct CollectionView;
struct View;
using t_container = bmi::multi_index_container<ItemType,
bmi::indexed_by<
Indexes...,
bmi::random_access<bmi::tag<View> > // additional!
>
>;
public:
explicit Collection(std::initializer_list<ItemType> init) : itemSet(init) {}
bool insert(ItemType const& item) {
return itemSet.insert(item).second;
}
template <int index = 0, typename K>
bool erase(K const& key) {
return itemSet.template get<index>().erase(key);
}
private:
t_container itemSet;
};
template<class TCollectionType>
struct CollectionView {
using MIC = typename TCollectionType::t_container;
using T = typename MIC::value_type;
using Tag = typename TCollectionType::View;
using Index = typename MIC::template index<Tag>::type;
TCollectionType& col;
Index& idx { col.itemSet.template get<Tag>() };
// Imagine that this view also keeps track of which
// item in col corresponds to which item on the screen
//
explicit CollectionView(TCollectionType& col) : col(col) {}
template <int n> void arrange_by() {
idx.rearrange(col.itemSet.template get<n>().begin());
}
template <typename Cmp> void arrange_by(Cmp cmp) {
std::vector<std::reference_wrapper<T const> > v(idx.begin(), idx.end());
std::stable_sort(v.begin(), v.end(), cmp);
idx.rearrange(v.begin());
}
auto begin() const { return idx.begin(); }
auto end() const { return idx.end(); }
};
/// example application
struct Item {
int id;
std::string name;
// some natural ordering just for demo
bool operator<(Item const& other) const
{ return std::tie(id, name) < std::tie(other.id, other.name); }
bool operator>(Item const& other) const
{ return std::tie(id, name) > std::tie(other.id, other.name); }
};
using Items = Collection<Item,
bmi::ordered_unique<bmi::member<Item, int, &Item::id> >,
bmi::ordered_unique<bmi::member<Item, std::string, &Item::name> > >;
int main() {
Items items {
{ 3, "three" },
{ 1, "one" },
{ 5, "five" },
{ 4, "four" },
{ 2, "two" },
{ 6, "six" },
};
CollectionView view(items);
auto dump = [&view](auto caption) {
std::cout << std::setw(12) << caption << ": ";
for (auto const& [id, name] : view)
std::cout << " { " << id << ", " << std::quoted(name) << " }";
std::cout << "\n";
};
dump("default");
view.arrange_by<1>(); // by name
dump("by name");
view.arrange_by<0>(); // by id
dump("by id");
view.arrange_by(std::less<Item>{});
dump("std::less");
view.arrange_by(std::greater<Item>{});
dump("std::greater");
auto funky = [](Item const& a, Item const& b) {
return (a.name.length() - a.id) < (b.name.length() - b.id);
};
view.arrange_by(funky);
dump("funky");
// mutations are fine
if (items.erase(1))
std::cout << "Removed 1\n";
dump("funky");
if (items.insert(Item { 42, "answer" }))
std::cout << "Inserted the answer (appears at end)\n";
dump("funky");
view.arrange_by<1>();
dump("by name");
}
版画
default: { 3, "three" } { 1, "one" } { 5, "five" } { 4, "four" } { 2, "two" } { 6, "six" }
by name: { 5, "five" } { 4, "four" } { 1, "one" } { 6, "six" } { 3, "three" } { 2, "two" }
by id: { 1, "one" } { 2, "two" } { 3, "three" } { 4, "four" } { 5, "five" } { 6, "six" }
std::less: { 1, "one" } { 2, "two" } { 3, "three" } { 4, "four" } { 5, "five" } { 6, "six" }
std::greater: { 6, "six" } { 5, "five" } { 4, "four" } { 3, "three" } { 2, "two" } { 1, "one" }
funky: { 4, "four" } { 2, "two" } { 3, "three" } { 1, "one" } { 6, "six" } { 5, "five" }
Removed 1
funky: { 4, "four" } { 2, "two" } { 3, "three" } { 6, "six" } { 5, "five" }
Inserted the answer (appears at end)
funky: { 4, "four" } { 2, "two" } { 3, "three" } { 6, "six" } { 5, "five" } { 42, "answer" }
by name: { 42, "answer" } { 5, "five" } { 4, "four" } { 6, "six" } { 3, "three" } { 2, "two" }