将迭代器放在其中的容器中

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++递归类型定义中可能,特别是我可以将vector <T>放在定义中T'

编辑:以下是@Richard Hodges提出的一些背景知识:

我想在容器内存储一组对象的分区(在数学意义上),以便对与分区关联的等价类进行排序.因此,我的想法是将这些等价类作为链表,因为它适合我对快速删除和顺序迭代的需求.当我开始使用那些等价类时,该集将被修复,因此迭代器无效是没有问题的.当然,比较,平等和散列只取决于T三元组的属性.

现在我不确定哪个容器对我的算法更好.因此,我正在尝试编写这样一个模板来推迟选择.我将能够在最后更换容器.

注意:我也可以使用将两个迭代器关联到a的映射T,boost::flat_set如果我想要一个向量的等价物,但这与此处提出的模板问题完全正交.

Answer 1

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

vec 是 Something 对象的原始不可变向量（这就像上面的 T）。

WeightedIndex 是 vec 中的迭代器向量，在本例中已按升序 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}