Thread: *Instant* Container Access

  1. #1
    ...and never returned. StainedBlue's Avatar
    Join Date
    Aug 2009
    Posts
    168

    *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.
    goto( comeFrom() );

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    What do you want the iterator to do? What order should it iterate?

  3. #3
    ...and never returned. StainedBlue's Avatar
    Join Date
    Aug 2009
    Posts
    168
    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.
    goto( comeFrom() );

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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.

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    'Allo, 'Allo, Allo
    Join Date
    Apr 2008
    Posts
    639
    Quote Originally Posted by StainedBlue View Post
    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")
        );
    
    }
    Last edited by adeyblue; 05-30-2010 at 02:17 PM.

  7. #7
    ...and never returned. StainedBlue's Avatar
    Join Date
    Aug 2009
    Posts
    168
    @ adeyblue
    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!
    goto( comeFrom() );

  8. #8
    ...and never returned. StainedBlue's Avatar
    Join Date
    Aug 2009
    Posts
    168
    Quote Originally Posted by dwks View Post
    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.
    goto( comeFrom() );

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Access via iterator to pointer container
    By atlmallu in forum C++ Programming
    Replies: 2
    Last Post: 07-20-2009, 01:13 PM
  2. Replies: 33
    Last Post: 05-14-2009, 10:15 AM
  3. sorting container
    By l2u in forum C++ Programming
    Replies: 6
    Last Post: 09-01-2007, 01:12 PM
  4. container random access
    By l2u in forum C++ Programming
    Replies: 9
    Last Post: 08-29-2007, 09:46 PM
  5. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM