*Instant* Container Access

Imagine I have 3 separate containers (for example, 3 lists) that are identical, point to the same exact objects, but are sorted on different criteria.

Is there a way, or design scheme that would allow me to essentially return an iterator-like pointer by simply calling some "get_iterator()" method on the object?

Example: (X is the same object, but has a different position in each container)

[] [] [] [] [X] [] [] get iterator to x here
[][X][][][][][] and here
[][][][][][][X] and here

I'm looking for a way to do this, without having to hand-code my own custom container, unless there is no other way.

What do you want the iterator to do? What order should it iterate?

Iterate either direction from x.

Each list contains the same objects, but each list is sorted differently. So in the grander-scheme of things, the lists are basically search filters.

To avoid O of N^2 and even redundant searches at N, i'd like to get say, 3 iterators (1 for each list) that is already at the object's position (obviously a different position for each of the 3 lists) by calling some method like:

Code:

---

get_iterator(foo& f);

---

if there is nothing already out there, i'll have to code the lists by hand, where each node wold have next, prev, and some other pointer that points to the object's "self" in another container.

Ah I see. I don't think there's something like that in the standard library.

You'll have to keep track of that yourself.

From what I understand, you basically need to do a lookup from an object (or a pointer) to the position of the object in each of the lists that you are maintaining. One way to do this would be to use an std::map with keys of type foo* and values containing indices or pointers into your lists. This would probably be O(log n), as my gcc uses a red-black tree to implement std::map.

You could also put a "next_list" pointer in each element of each list. The pointer at the [X] in the first list, for example, would point to the [X] in the second list, and so on until the [X] in the last list points to the [X] in the first. Then you'd only have to do lookups to find the [X] once (using a linear search, or a logarithmic std::map search as described above). This probably means your own custom data type, of course, but you could also do it with a wrapper object for the value type.

Maybe you can describe what you're trying to do in more detail. I gather you have a reference to an object and you want to find elements that are "close" to it according to different search criteria, or something like that?

Quote:

---

Originally Posted by StainedBlue

Imagine I have 3 separate containers (for example, 3 lists) that are identical, point to the same exact objects, but are sorted on different criteria.

...
I'm looking for a way to do this, without having to hand-code my own custom container, unless there is no other way.

---

Sounds like an ideal job for boost::multi_index_container. Here's a quick example but there are different ways to index and use it that may be more efficient or natural to your data set.

Code:

---

#include <iostream>
#include <iterator>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/global_fun.hpp>

struct Object
{
    int uniqueVal;
    int nonUniqueVal;

    static int counter;

    Object(int nonUniqueVal)
        : uniqueVal(++counter),
        nonUniqueVal(nonUniqueVal)
    {}

    bool operator<(const Object& other) const
    {
        return uniqueVal < other.uniqueVal;
    }
};

int Object::counter = 0;

int NonUniqueMod3(const Object& obj)
{
    return obj.nonUniqueVal % 3;
}

Object CreateObject()
{
    return Object(rand() % 500);
}

std::ostream& operator<<(std::ostream& out, const Object& obj)
{
    out << "Unique: " << obj.uniqueVal <<
        ", nonUniqueVal: " << obj.nonUniqueVal <<
        ", Mod 3: " << NonUniqueMod3(obj);
    return out;
}

int main(int, char**)
{
    using namespace boost::multi_index;
    typedef multi_index_container<
        Object,  // the object to contain
        indexed_by<
            ordered_unique<
                identity<Object> // initial order by operator<
            >,
            ordered_non_unique<
                member<Object, int, &Object::nonUniqueVal>
            >,  // secondary order by nonUniqueVal member
            ordered_non_unique<
                global_fun<const Object&, int, &NonUniqueMod3>
            > // tertiary order by NonUniqueMod function
        >
    > list;
    typedef list::iterator initialListIter;
    typedef list::nth_index<1>::type secondOrderList;
    typedef secondOrderList::const_iterator secondOrderListIter;
    typedef list::nth_index<2>::type thirdOrderList;
    typedef thirdOrderList::const_iterator thirdOrderListIter;

    srand(time(0));
    list myObjList;
    std::generate_n(std::inserter(myObjList, myObjList.end()), 10, &CreateObject);

    // get() returns the view of a different ordering, as specified by the template argument
    const secondOrderList& nonUniqueList = myObjList.get<1>();
    secondOrderListIter nonUniqueBegin = nonUniqueList.begin();
    // the items according to the third ordering
    const thirdOrderList& nonUniqueMod3List = myObjList.get<2>();
    thirdOrderListIter nonUniqueMod3Begin = nonUniqueMod3List.begin();

    initialListIter iter = myObjList.begin(), end = myObjList.end();
    std::cout << "By initial sort order\n";
    for(; iter != end; ++iter)
    {
        // project takes an iterator from any view and returns the corresponding
        // iterator in a different view (specified by the template argument)
        secondOrderListIter secondOrderIter = myObjList.project<1>(iter);
        size_t secondOrderPos = std::distance(nonUniqueBegin, secondOrderIter);
        thirdOrderListIter thirdOrderIter = myObjList.project<2>(secondOrderIter);
        size_t thirdOrderPos = std::distance(nonUniqueMod3Begin, thirdOrderIter);
        std::cout << "Unique " << iter->uniqueVal << ", second order pos = " << secondOrderPos <<
            " (" << secondOrderIter->nonUniqueVal << "), third order pos = " << thirdOrderPos <<
            " (" << NonUniqueMod3(*thirdOrderIter) << ")\n";
    }
    std::cout << "\nBy second sort order:\n";
    std::copy(nonUniqueList.begin(),
        nonUniqueList.end(),
        std::ostream_iterator<Object>(std::cout, "\n")
    );
    std::cout << "\nBy third sort order:\n";
    std::copy(nonUniqueMod3List.begin(),
        nonUniqueMod3List.end(),
        std::ostream_iterator<Object>(std::cout, "\n")
    );

}

---

@ adeyblue

Quote:

---

Sounds like an ideal job for boost::multi_index_container.

---

Holy smokes, that's exactly what I need! Throw in the project() function and the rest is history, too cool. Thank you!

Quote:

---

Originally Posted by dwks

I gather you have a reference to an object and you want to find elements that are "close" to it according to different search criteria, or something like that?

---

thank you as well dwks. You were spot on with your last paragraph, and your approach may even provide more efficiency than the boost container. I'll consider all the ideas, and see what works out best for my situation, which is almost exactly as you've described. Thank you.