c++ - 将迭代器放在其中的容器上

Question

我想写一个模板，它获取一个容器模板作为参数(例如vector、set、unordered_set)和一个输入 T 并返回一个双向链接的容器，即容器的每个项目都应包含一个三元组:

• T
• 一个 prev 迭代器，指向 T 的其他三元组
• next 迭代器，指向 T 的其他三元组

类似于下面的内容:

template <template <class Tr> class Container, class T>
struct Triple {
  T value;
  typename Container< Triple<Container, T> >::iterator prev, next;
};

template <template <class Tr> class Container, class T>
using DoublyLinkedContainer = Container< Triple< Container, T> >;

#include <vector>

// default partial specialisation of the Allocator parameter
template <class T> using SimpleVector = std::vector<T>;
DoublyLinkedContainer<SimpleVector, int> v;

它似乎被编译器(gcc 和 clang)接受，但我不明白我是否正在调用未定义的行为，如 Are C++ recursive type definitions possible, in particular can I put a vector<T> within the definition of T?

编辑:这是@Richard Hodges 询问的一些背景:

我想将一组对象的分区(在数学意义上)存储在一个容器内，这样与该分区关联的等价类是有序的。因此我的想法是将这些等价类做成链表，因为它适合我快速删除和顺序迭代的需要。当我开始使用这些等价类时，该集合将被修复，因此迭代器失效就没有问题了。当然，比较、相等和哈希仅取决于三元组的 T 属性。

现在我不确定哪个容器更适合我的算法。因此，我试图编写这样一个模板来推迟选择。我将能够在最后更改容器。

注意:如果我想要等效于一个 vector ，但这与此处提出的模板问题完全正交。

Answer 1

这是我认为您要解决的问题的解决方案。

vec 是 Something 对象的原始不可变 vector (这就像上面的 T)。

weightedIndex 是 vec 的一个 vector ，在这种情况下，它是通过升序排序的 Something.weight() (但它可以是任何谓词)

#include <iostream>
#include <vector>
#include <algorithm>

struct Something
{
    Something(int weight)
    : _creationOrder { _createCount++ }
    , _weight { weight }
    {}

    int weight() const { return _weight; }

    std::ostream& write(std::ostream& os) const {
        os << "Something { createOrder=" 
        << _creationOrder 
        << ", weight=" << _weight << "}";
        return os;
    }
private:
    int _creationOrder;
    int _weight;
    static int _createCount;
};

std::ostream& operator<<(std::ostream& os, const Something& st) {
    return st.write(os);
}

int Something::_createCount { 0 };

using namespace std;

int main()
{
    vector<Something> vec { 10, 23, 76, 12, 98, 11, 34 };
    cout << "original list:";
    for(const auto& item : vec) {
        cout << "\n" << item;
    }

    using iter = decltype(vec)::const_iterator;
    vector<iter> weightIndex;
    weightIndex.reserve(vec.size());
    for(auto i = vec.begin() ; i != vec.end() ; ++i) {
        weightIndex.push_back(i);
    }
    sort(weightIndex.begin(), weightIndex.end() , [](const iter& i1, const iter& i2) {
       return i1->weight() < i2->weight(); 
    });

    // weightIndex is now a vector of pointers to the Something elements, but the pointers
    // are ordered by weight of each Something

    cout << "\nSorted index:";
    for(const auto p : weightIndex) {
        cout << "\n" << *p;
    }

    cout << endl;

    // find the mid-weight
    auto ii = next(weightIndex.begin(), 3);

    // next one in list is
    auto next_ii = next(ii, 1);

    // find previous in weighted order
    auto prev_ii = prev(ii, 1);
    cout << "Selection:\n";
    cout << "Current = " << **ii << endl;
    cout << "Next = " << **next_ii << endl;
    cout << "Previous = " << **prev_ii << endl;


   return 0;
}

输出:

original list:
Something { createOrder=0, weight=10}
Something { createOrder=1, weight=23}
Something { createOrder=2, weight=76}
Something { createOrder=3, weight=12}
Something { createOrder=4, weight=98}
Something { createOrder=5, weight=11}
Something { createOrder=6, weight=34}
Sorted index:
Something { createOrder=0, weight=10}
Something { createOrder=5, weight=11}
Something { createOrder=3, weight=12}
Something { createOrder=1, weight=23}
Something { createOrder=6, weight=34}
Something { createOrder=2, weight=76}
Something { createOrder=4, weight=98}
Selection:
Current = Something { createOrder=1, weight=23}
Next = Something { createOrder=6, weight=34}
Previous = Something { createOrder=3, weight=12}