An item search based on 2 values for "index". How to do efficient?

[Nobun]

I have to be more code specific (I usually try to abstract my code). As you can see I use a lot Qt classes... however they work very similar to standard libraries, so it should be not a problem to look at this question.

class FrameManager {
    QList<FRAME> frameData;
  public:
    int frameID(int grpno, int imgno);
};

//---------------
// struct FRAME contains "groupno" and "imageno" to identify a frame.
// it contains also other datas (the other informations) but we don't care now
//--------------

//inside a CPP file
int FrameManager::frameID(int grpno, int imgno) {
  int value = 0;
  for(value==0, value < frameData.count(); value ++) {
    if(frameData[value].groupno == grpno && 
       frameData[value].imageno == imgno) return value;
  }
  return -1; //if not found, returns -1
}

now I know the example search only the ID and doesn't allow the access of the actual data... this is not the question.

The problem is... I will need to define an AnimationManager class that will collect sequence of frames (identified by the unique couple of value) in animations... so it will need to use a massive search of item from the couple of value (and not ID, unluckly)

I fear if I use an approach similar to the one written in the example (search from the start to the end until the element is found) can be very unefficient.
In the same time the AnimationManager should always know if frame exist or not (if not exist an invisible image will be shown) and if in the meantime changed.

Another problem is that I cannot order the data sequence inside FrameManager (becouse it is expected to mantain the original order, even when it is chaotic).

I tried to take a look around QMap (or std::map) but it is not clear at all how the optimiziation works and how I can use it in my case

I tried also to take a look at the "hash" concept, but for me it is too complex to understand deeply.

So... I am feeling like I am entrapped... I am unable to find a good "exit"...

[JLBorges]

Use a std::map< std::pair<int,int>, FrameManager >?

[Nobun]

First of all, thank for replying

Do you remember the "Singleton" BinaryHandler that needed to be used from class BinaryInterface? Well... FrameManager actually IS the class BinaryInterface (tbh the true classname is SffInterface) that will be a singleton too (only 1 FrameManager and 1 AnimationManager must be executed during runtime, so I will expand your previous suggestion).

So perhaps I would need to map DATA (in the example I called it "FRAME").
But... as I explained I don't understand how actually use std::map and how std::map< std::pair <int, int>, FRAME> and how that map could speed the search.... (how using 2 objects is more efficient - in terms of quickness - than iterating into list? It is not clear for me)... and however it is not clear to me how actually use map to "map and search" inside my list of frames (If I understood it I would use QMap or QHash instead, together with QPair, that are the Qt alternatives of std::map or std::unordered_map and std::pair... the logic is the same.... however I never understood how to use maps and how/if they can be considered actually efficient)

[JLBorges]

Iterating over a list to find an element takes O(N) time.

Looking up a key in a std::map<> (BST) takes O( log N ) time.

Looking up a key in a std::unordered_map<> (hash table) takes amortized O(1) (constant) time.

#include <utility>
#include <list>
#include <algorithm>
#include <map>
#include <unordered_map>

struct frame
{
    typedef std::pair<int,int> id_t ;
    frame( int g, int i ) : group_id(g), image_id(i) {} ;
    id_t id() const { return std::make_pair(group_id,image_id) ; }

    bool operator== ( const frame& that ) const { return id() == that.id() ; }
    bool operator< ( const frame& that ) const { return id() < that.id() ; }
    // other rel ops

    int group_id ;
    int image_id ;

    // ...
    struct hash
    {
        std::size_t operator() ( const frame::id_t& id ) const
        {
            static const std::hash<long long> h ;
            return h( id.first * 100000 + id.second ) ;
        }
    };
};

int main()
{
    constexpr int N = 100 ;

    // ******************  insertion *****************

    // sequence of N*N (10000) unique frames
    std::list<frame> sequence ;
    for( int i = 0 ; i < N ; ++i )
        for( int j = 0 ; j < N ; ++j )
            sequence.emplace_back( i, j ) ; // insertion in O(1) time

    // (ordered) map of id to frame
    std::map< frame::id_t, frame > ordered_map ;
    // insertion of an item in O( log N ) time
    for( const frame& f : sequence ) ordered_map.emplace( f.id(), f ) ;

    // (unordered) map of id to frame
    std::unordered_map< frame::id_t, frame, frame::hash > unordered_map ;
    // insertion of an item in amortized O(1) time
    for( const frame& f : sequence ) unordered_map.emplace( f.id(), f ) ;



    // ******************  iteration *****************

    // sequence - iterate in insertion order
    for( const frame& f : sequence ) { /* ... */ }

    // ordered map - iterate in  order of ids
    for( const auto& p : ordered_map ) { const frame& f = p.second ; /* ... */ }

    // unordered map - no iteration order can be assumed
    for( const auto& p : unordered_map ) { const frame& f = p.second ; /* ... */ }



    // ******************  look up *****************

    frame f { 50, 50 } ;

    // sequence - look up in O(N) time
    {
        auto iter = std::find( sequence.begin(), sequence.end(), f ) ;
        if( iter != sequence.end() ) { frame& found = *iter ; /* ... */ }
    }

    // ordered map - look up in O( log N ) time
    {
        auto iter = ordered_map.find( f.id() ) ;
        if( iter != ordered_map.end() ) { frame& found = iter->second ; /* ... */ }
    }

    // unordered map - look up in amortized O(1) time
    {
        auto iter = unordered_map.find( f.id() ) ;
        if( iter != unordered_map.end() ) { frame& found = iter->second ; /* ... */ }
    }
}

EDIT: std::set<> and std::unordered_set<> are also options.

[Nobun]

Wow this sounds very complex.... I am not sure to have understood anything...

the raw FRAME is composed by 5 basic elements (plus others): grpno, imgno, x, y, IMAGE
grpno, imgno is the data to map and, as far I understood your code is thinked to map FRAME throgout a std::list<int,int> that refers o the grpno, imgno (they identify image, infact).

But a lot of things are totally unclear for me... very sorry....

1) its not clear to me where to store the remaining data (I mean, a part grpno, imgno) inside your frame (perhaps is the struct "hash"?)

If not... what is the purpose of struct "hash" and how it works (it is a very mistery for me ... )

2) I never seen before this syntax
for( const frame& f : sequence ) unordered_map.emplace( f.id(), f ) ;

what "const frame & f : sequence" means? I am used to see the for syntax with 3 parameters - for (x = 0; x < 10; x++) [initilization, condition, increment/decrement]
and however I never seen the operator ":" used in this way O.o

3) It is also unclear another thing how do you store the std::list<frame> into the std::map ???? I missed something...... (A thing I don't like in STL templates is that the nomenclature of the functions are a bit obscure... I prefer Qt that is more clear in that - like .append, .prepend, .replace, .swap, etc etc)

4) and how to find a desired frame and access to the rest of the data?

------

You surely already wrote the answer to all my questions here, but I am unable to see them by myself. Thank a lot for you patience

(Note: I never used the "auto" keyword... never used "constexpr"... I usually say simply "const")

[JLBorges]

1) its not clear to me where to store the remaining data (I mean, a part grpno, imgno) inside your frame

I've not shown the remaining data; just indicated it by a ....
Store it as members in the frame. Like this:

struct frame
{
    typedef std::pair<int,int> id_t ;
    frame( int g, int i ) : group_id(g), image_id(i) {} ;
    id_t id() const { return std::make_pair(group_id,image_id) ; }

    bool operator== ( const frame& that ) const { return id() == that.id() ; }
    bool operator< ( const frame& that ) const { return id() < that.id() ; }
    // other rel ops

    int group_id ;
    int image_id ;

    // ... 
    // the ... indicated other members of the frame.
    // for instance
    double x ;
    double y ;
    IMAGE* img ;
    // and so on

    struct hash
    {
        std::size_t operator() ( const frame::id_t& id ) const
        {
            static const std::hash<long long> h ;
            return h( id.first * 100000 + id.second ) ;
        }
    };
};

An unordered_map<> requires a hash function to hash the keys; frame::hash is the function object that provides this. It is required only by the hash table implementation (std::unordered_map<>).


> 2) I never seen before this syntax
> for( const frame& f : sequence )

See: http://www.stroustrup.com/C++11FAQ.html#for



> 3) It is also unclear another thing how do you store the std::list<frame> into the std::map

A std::map<> stores pairs of key and associated data.
In this case, the key is: std::pair<int,int> group_id,image_id
and the associated data is the frame object.

See: http://www.cplusplus.com/reference/map/map/


> how to find a desired frame and access to the rest of the data?

As in the lookup example above.

int group_id = 7 ;
int image_id = 26 ;
std::pair<int,int> key = std::make_pair( group_id, image_id ) ;
auto iter = ordered_map.find( key ) ;
if( iter != ordered_map.end() )
{
    // we found it
    frame& data = iter->second ;
    // use data
}
else
{
    // a frame with this key is not there
}

[Nobun]

Again... thank a lot for your patience.
After your replies I read again a lot about std::map and std::unordered_map to understand the efficency system.
I find what red-black-tree is... so now it is clear why std::map is faster than iterating each item. The efficiency of std::unordered_map is unclear, instead. It seems to me that the "hash table" works as "index map" and in this case probably std::unordered_map can be not so efficient (or perhaps equal to simple iterators).

Correct me if I am wrong (and if so, can you try to explain how hash can improve search efficency compared to item iterator?)

Some other questions:
1) is it possible to use std::map to check a list of unordered_list? I mean... even if std::map ordering data inside itself, can be used without changing the order of original list of data?
example: std::list<frame> frames; //unordered list
std::map<std::pair<int, int>, frame> frame_map; //ordered inside, but will not touch std::list<frame> order

2) if the question 1) is true... how to don't "duplicate" frame datas (for example referencing frames or using pointers or other things) without changing order of original list?

3) std::map (or std::unordered_map) is able to check if the searched item actually exists? if not what happens?

Thank a lot for your help

[JLBorges]

> can you try to explain how hash can improve search efficency compared to item iterator?

See: http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html



> how to don't "duplicate" frame datas (for example referencing frames or using pointers or other things) without changing order of original list?

Use any one of these:

std::map< std::pair<int,int>, std::list<frame>::iterator > - map key to list iterator

std::map< std::pair<int,int>, frame* > - map key to pointer

std::map< std::pair<int,int>, std::reference_wrapper<frame> > - map key to reference (wrapper)

Keep both in sync while inserting and erasing.

An example with reference wrappers:

#include <iostream>
#include <list>
#include <functional>
#include <map>

struct frame
{
    frame( int aa, int bb, const std::string& t ) : a(aa), b(bb), tag(t) {}
    int a ;
    int b ;

    using key_type = std::pair<int,int> ;
    key_type key() const { return key_type(a,b) ; }

    std::string tag ;
    char other_data[1000] {0} ;
};

std::ostream& operator<< ( std::ostream& stm, const frame& a )
{ return stm << "{(" << a.a << ',' << a.b << "):" << a.tag << "}" ; }

struct containers
{
    std::list<frame> lst ;
    std::map< frame::key_type, std::reference_wrapper<frame> > map ;

    bool insert( const frame& a )
    {
        if( map.find( a.key() ) == map.end() )
        {
            lst.push_back(a) ;
            map.emplace( a.key(), lst.back() ) ;
            return true ;
        }
        return false ;
    }

    bool erase( frame::key_type key ) ; // if present, erase from both lst and map

    frame& look_up( frame::key_type key )
    {
        auto iter = map.find(key) ;
        if( iter == map.end() ) throw "not found" ;
        return iter->second ;
    }
};

int main()
{
    containers c ;
    c.insert( { 9, 6, "one" } ) ;
    c.insert( { 4, 0, "two" } ) ;
    c.insert( { 1, 8, "three" } ) ;
    c.insert( { 2, 3, "four" } ) ;
    c.insert( { 1, 5, "five" } ) ;
    c.insert( { 2, 2, "six" } ) ;

    // iterate in list order
    for( const frame& a : c.lst ) std::cout << a << ' ' ;
    std::cout << '\n' ;

    // iterate in key order
    for( const auto& p : c.map ) std::cout << p.second << ' ' ;
    std::cout << '\n' ;

    // look up (2,3), (6,7)
    try
    {
        std::cout << "looking up (2,3):  " ;
        frame& a1 = c.look_up( frame::key_type(2,3) ) ;
        std::cout << "found it - tag == " << a1.tag << '\n' ;
        std::cout << "looking up (6,7):  " ;
        frame& a2 = c.look_up( frame::key_type(6,7) ) ;
        std::cout << "found it - tag == " << a2.tag << '\n' ;
    }
    catch(...)
    {
        std::cout << "lookup failed\n" ;
    }
}

http://liveworkspace.org/code/DIWvl$0


> std::map (or std::unordered_map) is able to check if the searched item actually exists?
> if not what happens?

std::map<>::find() and std::unordered_map<>::find() return an iterator.
If the searched item is not present, the iterator returned corresponds to end()
see: http://en.cppreference.com/w/cpp/container/map/find
http://en.cppreference.com/w/cpp/container/unordered_map/find

[Nobun]

Well thank a lot for your patience and for writing me so many things and line of codes :)

I will try to stop here this question and read deeply all you wrote (I don't want to bother you too much) and I will mark the question as solved. I think there is all I need to look and think-for in order to understand this thing (it will require some time, but it is nice :) ).