I don't know what is the common name for this data structure I named it like this due to a definition in wikipedia that states the following: In a 'multiply linked list', each node contains two or more link  fields, each field being used to connect the same set of data records  in a different order (e.g., by name, by department, by date of birth,  etc.). While doubly linked lists can be seen as special cases of  multiply linked list, the fact that the two orders are opposite to  each other leads to simpler and more efficient algorithms, so they are  usually treated as a separate case.I would like to know if this is a proper implementation of this data structure. Also any kind of improvements are welcome.Implementation: #pragma once#include <functional>#include <stdexcept>namespace dts {    template < typename T >    class MultiplyList    {    public:        using Comparator = std::function < int(const T&, const T&)>;    private:            class MultiNode            {            public:                T data;                MultiNode** nexts;                MultiNode** prevs;                unsigned size;                MultiNode(unsigned psize, const T& pdata)                     : data(pdata), nexts(new MultiNode*[psize]),                         prevs(new MultiNode*[psize]), size(psize)                { }                MultiNode(unsigned psize, T&& pdata)                    :data(std::move(pdata)), nexts(new MultiNode*[psize]),                         prevs(new MultiNode*[psize]), size(psize)                { }                MultiNode(unsigned psize)                    :MultiNode(psize, T())                { }                ~MultiNode()                 {                    delete[] nexts;                    delete[] prevs;                }                MultiNode* getNext(unsigned index) const                {                    check(index);                    return nexts[index];                }                void setNext(unsigned index, MultiNode* node)                {                    check(index);                    nexts[index] = node;                }                MultiNode* getPrev(unsigned index) const                {                    check(index);                    return prevs[index];                }                void setPrev(unsigned index, MultiNode* node)                {                    check(index);                    prevs[index] = node;                }                void check(unsigned index) const                 {                    if ( index >= size)                        throw new std::out_of_range(out of range);                }            };            Comparator* arrayCmp;            unsigned sizeCmp;            int keyIndex;            MultiNode* sentinel;            unsigned size;            void addNodeBefore(unsigned, MultiNode* newNode, MultiNode* node);            bool findTightBoundary(unsigned, const T&, MultiNode*&) const;            void deleteNode(MultiNode*);            void resetSentinel();            template<typename TT>            bool genericAdd(TT&&);    public:            MultiplyList(std::initializer_list<Comparator>, int);            MultiplyList(std::initializer_list<Comparator>);            ~MultiplyList();            bool add(const T&); //override T&&            bool add(T&&);            template<typename Predicate>            bool remove(const Predicate&);            template<typename Predicate>            bool remove(const Predicate&, T&);            bool empty() const;            unsigned length() const;            template<typename Func>            void foreach(Func, unsigned index)const;            template<typename Func>            void foreach(Func)const;            template<typename Predicate>            bool find(Predicate, T&);            void clear();            bool hasKey();            int paths();            T getMax(int) const;            T getMin(int) const;        };    template<typename T>    MultiplyList<T>::MultiplyList(std::initializer_list<Comparator> cmps)         :MultiplyList(cmps, -1)    { }    template<typename T>    MultiplyList<T>::MultiplyList(std::initializer_list<Comparator> cmps, int key)            : sizeCmp(cmps.size()), size(0), arrayCmp(new Comparator[cmps.size()]),            sentinel(new MultiNode(cmps.size() + 1)), keyIndex(key)    {        unsigned index = 0;        for (const Comparator& e : cmps)            arrayCmp[index++] = e;        resetSentinel();        if (0 <= key && key < sizeCmp)            std::swap(arrayCmp[key], arrayCmp[0]);        else key = -1;    }    template<typename T>    MultiplyList<T>::~MultiplyList()    {        clear();        delete[] arrayCmp;        delete sentinel;    }    //O(sizeCmp*n)    template<typename T>    template<typename TT>    bool MultiplyList<T>::genericAdd(TT&& e)    {        MultiNode *node = nullptr;        bool isUnique = findTightBoundary(0, e, node);        if (hasKey() && !isUnique) return false;        auto newNode = new MultiNode(sizeCmp + 1, std::forward<TT>(e));        addNodeBefore(0, newNode, node);        for (unsigned i = 1; i < sizeCmp; ++i)        {            findTightBoundary(i, e, node);            addNodeBefore(i, newNode, node);        }        addNodeBefore(sizeCmp, newNode, sentinel);        ++size;        return true;    }    template<typename T>    bool MultiplyList<T>::add(T&& e)    {        genericAdd(std::move(e));    }    template<typename T>    bool MultiplyList<T>::add(const T& e)    {        genericAdd(e);    }    template<typename T>    template<typename Predicate>    bool MultiplyList<T>::remove(const Predicate& pre)    {        T out;        return remove(pre, out);    }    template<typename T>    template<typename Predicate>    bool MultiplyList<T>::remove(const Predicate& pre, T& out)    {        const unsigned path = 0;        auto node = sentinel->getNext(path);        while (node != sentinel && !pre(node->data))            node = node->getNext(path);        bool exist = node != sentinel;        if (exist)        {            out = node->data;            deleteNode(node);        }        return exist;    }    template<typename T>    bool MultiplyList<T>::empty() const    {        return size == 0;    }    template<typename T>    unsigned MultiplyList<T>::length() const    {        return size;    }    template<typename T>    template<typename Func>    void MultiplyList<T>::foreach(Func func, unsigned cmpIndex) const    {        auto node = sentinel->getNext(cmpIndex);        while (node != sentinel)        {            func(node->data);            node = node->getNext(cmpIndex);        }    }    template <typename T>    template<typename Func>    void  MultiplyList<T>::foreach(Func f) const    {        foreach(f, sizeCmp);    }    template<typename T>    template<typename Predicate>    bool MultiplyList<T>::find(Predicate pre, T& e)    {        const unsigned index = sizeCmp;        auto node = sentinel->getNext(index);        while (node != sentinel && !pre(node->data))            node = node->getNext(index);        bool found = node != sentinel;        if (found) e = node->data;        return found;    }    template<typename T>    void MultiplyList<T>::addNodeBefore(unsigned cmpIndex, MultiNode* newNode, MultiNode* node)    {        newNode->setNext(cmpIndex, node);        newNode->setPrev(cmpIndex, node->getPrev(cmpIndex));        node->getPrev(cmpIndex)->setNext(cmpIndex, newNode);        node->setPrev(cmpIndex, newNode);    }    template<typename T>    bool MultiplyList<T>::findTightBoundary(unsigned cmpIndex, const T& e, MultiNode*& node) const    {        auto ig = 1;        node = sentinel->getNext(cmpIndex);        while (node != sentinel && (ig = arrayCmp[cmpIndex](e, node->data)) > 0)            node = node->getNext(cmpIndex);        return ig != 0;    }    template<typename T>    void MultiplyList<T>::deleteNode(MultiNode* node)    {        for (unsigned i = 0; i <= sizeCmp; ++i)        {            node->getPrev(i)->setNext(i, node->getNext(i));            node->getNext(i)->setPrev(i, node->getPrev(i));        }        delete node;        --size;    }    template<typename T>    void MultiplyList<T>::clear()    {        const unsigned path = 0;        auto node = sentinel->getNext(path);        while (node != sentinel)        {            auto borrar = node;            node = node->getNext(path);            delete borrar;        }        resetSentinel();    }    template <typename T>    void  MultiplyList<T>::resetSentinel()    {        for (unsigned i = 0; i <= sizeCmp; ++i)        {            sentinel->setNext(i, sentinel);            sentinel->setPrev(i, sentinel);        }    }    template <typename T>    bool MultiplyList<T>::hasKey()    {        return  keyIndex >= 0;    }    template <typename T>    int MultiplyList<T>::paths()    {        return sizeCmp + 1;    }    template<typename T>     T MultiplyList<T>::getMax(int index) const    {        if (empty()) throw std::underflow_error(underflow);        return sentinel->getPrev(index)->data;    }    template<typename T>    T MultiplyList<T>::getMin(int index) const    {        if (empty()) throw std::underflow_error(underflow);        return sentinel->getNext(index)->data;    }}Example: (This example is just to show some client code I have no particular interest in getting a review of this part)#include <tuple>#include <vector>#include <algorithm>#include <iostream>#include MultiplyList.husing str = std::tuple < int, char, std::string >;using namespace dts;void pruebaListaMultiply(MultiplyList<str>* list){    std::vector<std::string> vecS =         {             bb,             aa,            ccc,            dfsf,             atsdfds,             ggg,             hhh,             qqq,             sdad,             asdda,             dsfdsf,             dsffsf         };    std::vector<char> vecC =         {             'a','b',            'c','r',             'o', 'l',             'u', 'f',             'r', 'p',             'w', 'k'         };    unsigned min = std::min(vecS.size(), vecC.size());    for (unsigned i = min-1; i !=0; --i)    {           list->add(str(i, vecC[i], vecS[i]));    }    for (unsigned i = 0; i < 4; ++i)    {        std::cout << Criterio #  << i << std::endl;        list->foreach(            [](str x)        {            std::cout << std::get<0>(x)                <<   << std::get<1>(x)                <<   << std::get<2>(x).c_str()                <<   << std::endl;        },i);    }       list->remove([](str x){ return std::get<0>(x) == 6; });    std::cout << Despues << std::endl << std::endl;    for (unsigned i = 0; i < 3; ++i)    {        std::cout << Criterio #  << i << std::endl;        list->foreach(            [](str x)        {            std::cout << std::get<0>(x)                <<   << std::get<1>(x)                <<   << std::get<2>(x).c_str()                <<   << std::endl;        },i);    }}void example(){    auto list = new MultiplyList<str>    ({        [](str x, str y)        {            if (std::get<1>(y) < std::get<1>(x))return 1;            if (std::get<1>(x) < std::get<1>(y))return -1;            return 0;        },            [](str x, str y)        {            if (std::get<0>(y) < std::get<0>(x))return 1;            if (std::get<0>(x) < std::get<0>(y))return -1;            return 0;        },        [](str x, str y)        {            if (std::get<2>(y) < std::get<2>(x))return 1;            if (std::get<2>(x) < std::get<2>(y))return -1;            return 0;        }    },1);    pruebaListaMultiply(list);    list->clear();    pruebaListaMultiply(list);}int main(int argc, char** argv) {    example();}
Multiply linked list - implementation
c++;c++11;linked list
Pointers And Double Pointers, Oh MyLet's start with the composition of your Node. You have:MultiNode** nexts;MultiNode** prevs;unsigned size;Two issues I have here. First, according to the problem description, the list is multiply linked - but nowhere is it stipulated that each link is bidirectional. Given that it is stated that doubly linked list is a special case of multiply linked list, that suggests that we just want a bunch of links. And furthermore, let's use C++ here and stick them in a vector:std::vector<MultiNode*> links;This lets you do things like drop the destructor, always a plus.ComparatorsSimilarly, your comparators should be:std::vector<Comparator> comparators;And typically, comparators return bool. Yours return int. I see what you're getting at, but that means I can't use operator< as a comparator - which may be surprising to many users. Add iteratorsYou need iterators. I'd recommend adding overloads for begin() and end() that take a comparator index. So something like;iterator begin() { return begin(0); }iterator begin(size_t idx) { /* return iterator based on this index */ }InsertionWhy does genericAdd() check for uniqueness? It's pretty reasonable to want a list of repeated objects - you should allow that. And adding the iterators allows for a much more pleasant search.void add(T const& elem){    auto new_node = new MultiNode(comparators.size(), elem);    for (size_t i = 0; i < comparators.size(); ++i) {        auto loc = std::lower_bound(begin(i), end(i), elem, comparators[i]);        insert_one(loc, new_node);    }    ++size;}Where insert_one is a private member function that will stick that new node in front of that iterator. Each iterator should be aware of which comparator index it's updating. The above is much easier to follow in my opinion.Unnecessary code bloatYou have a find() member function and a foreach() member function. Both of those go away if you add iterators, since your users can just use std::find_if() and std::for_each(), not to mention all the other algorithms.Naminglength() should be named size().remove() should be named erase() and should have an overload that removes a single iterator and an overload that takes an iterator range. Try getting the erase-remove idiom to work with your class. KeyIndexWhat is the purpose of this variable?