putting iterator on a container inside it

Question

I'd like to write a template which get a container template as parameter (such as vector, set, unordered_set) and a type T and return a doubly linked container, that is each item of the container should contain a triple:

• a T
• a prev iterator pointing to some other triple of T
• a next iterator pointing to some other triple of T

That is something like the following:

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;

It seems to be accepted by the compilers (gcc and clang), but I can't understand if I'm invoking undefined behavior as in Are C++ recursive type definitions possible, in particular can I put a vector<T> within the definition of T?

Edit: Here is some background as asked by @Richard Hodges:

I want to store a partition (in the mathematical sense) of a set of objects inside a container such that the equivalence classes associated to the partition are ordered. Therefore my idea is to make those equivalence classes as linked lists, since it suits my needs for fast removal and sequencial iteration. The set will be fixed when I will start to play with those equivalence classes, so that there is no problem with iterators being invalidated. Of course comparison, equality and hashes will only depend on the T attribute of the triple.

Right now I'm not sure which container will be better for my algorithm. Therefore, I'm trying to write such a template to postpone the choice. I'll be able to change the container at the end.

Note: I could as well use a map associating two iterators to a T and boost::flat_set if I want the equivalent of a vector but this is completely orthogonal to the template question raised here.

Answer 1

Here is a solution to what I think is the problem you're trying to solve.

vec is the original immutable vector of Something objects (this is like your T, above).

weightedIndex is a vector of interators into vec which in this case has been ordered by ascending Something.weight() (but it could be any predicate)

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

Output:

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}