存储引用/指针以增强多集索引

提问者：小点点

存储引用/指针以增强多集索引

我试图构建两个类collection和collectionView，后者是Boost.MultiIndex之上的抽象。这个想法有点简单:给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来让用户确定排序（从预定义的集合，因为必须在编译时知道它），那么实现这一点的方法就会有点问题。

CollectionView在理想情况下通过知道如何获取正确的索引来遍历集合
迭代索引可能会根据用户输入而更改

不知何故，我必须存储当前迭代索引，并且实际上还必须从集合的项集访问该索引。

理想情况下，我将向Collection添加以下属性:

struct CollectionView {
    t_index_type    currentIndex { col.itemSet.get<0>() }
    
    void Build() {
        for (const auto& item : currentIndex) {
            // Do stuff here
        }
    }
}

我不知道T_index_type可能是什么（如果有的话），因为每个索引（sequenced，ordered_non_unique等）有自己的类型。我可以强制用户实现void迭代(function)，但这会给API的用户带来更多的代码。

我是不是在这里走入了死胡同，或者我的模板-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;};

但也不是很好。

共1个答案

匿名用户

听起来，Boost Multi Index(BMI)的random_access_index确实可以为您提供服务。

你可以按照你想要的任何方式重新安排它。因此，即使您想让用户手动重新排列一些东西，例如，它们

添加一个元素，它将显示为最后一个项目，而不管集合中其余部分的顺序如何
选择与BMI索引之一不完全匹配的自定义排序顺序

那你就可以。

顺便说一句:注意，您也可以使用BMI容器来仅仅索引非所有或共享的元素。该实现允许元素类型为T*，T const*，std::reference_wrapper，shared_ptr等，而无需对功能进行任何其他更改。注意，它为此使用了泛型pointer_traits，因此您甚至可以使用std::reference_wrapper； >，它仍然可以工作。

这与答案无关，但确实与你所考虑的“外部观点”的概念产生了共鸣。

例如，参见https://www.boost.org/doc/libs/1_73_0/libs/multi_index/doc/reference/key_extract.html#chained_pointers

假设我们将一个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());
}

#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" }