Nested QHash in range for loop

[Scope]

Hi,

It is possible to use this data structure:

struct Data{
        QString scope;
        QString name;
        QVariant value;
};
 
QHash<QString, QHash<QString, Data>> data;

struct Data{
        QString scope;
        QString name;
        QVariant value;
};

QHash<QString, QHash<QString, Data>> data;

To copy to clipboard, switch view to plain text mode 

in range for loop like that:

for( const Data & d : data )
    qDebug()<< d.scope << d.name << d.value;

for( const Data & d : data )
    qDebug()<< d.scope << d.name << d.value;

To copy to clipboard, switch view to plain text mode 

[Scope]

I know that I must implement begin() and end() inside class which contains these nested QHash.
But how connect all ranges from inner QHash?

[yeye_olive]

The nested QHashes must be wrapped in a class for which you need to implement your own iterator and const_iterator. Such an iterator could consist of a triple ((const)iterator on the outer QHash, (const)iterator on the current inner QHash, (c)end() of the current inner QHash).

Do you really need to go through all this trouble? Consider theses options:

1. Replace your nested QHash with a flat QHash whose key type is a pair of QStrings.
2. Keep the nested QHash, and iterate over it with two nested for loops.

I recommend option 1. Option 2 (and your nested structure in general) only makes sense if you need to collectively manage all bindings sharing the same outer key.

[Scope]

QPair can not be a key in my case.
Every Data structure is identified by scope ( first QString ) and name (second QString ) and now when i want set some Data i have function:

class Container
{
public:
    void setData(const Data &data);
 
private:
    QHash<QString, QHash<QString, Data>> d;
 
};
 
 
void Container::setData(const Data &data)
{
    const QString scope = data.scope;
    const QString name = data.name;
 
    if( d.contains(scope) ) {
        if( d.value(scope).contains(name) )
            d[scope][name] = data;
        else
            d[scope].insert(name, data);
    }
    else {
        d.insert(scope, QHash<QString, Data>{{name, data}});
    }
}

class Container
{
public:
    void setData(const Data &data);

private:
    QHash<QString, QHash<QString, Data>> d;

};


void Container::setData(const Data &data)
{
    const QString scope = data.scope;
    const QString name = data.name;

    if( d.contains(scope) ) {
        if( d.value(scope).contains(name) )
            d[scope][name] = data;
        else
            d[scope].insert(name, data);
    }
    else {
        d.insert(scope, QHash<QString, Data>{{name, data}});
    }
}

To copy to clipboard, switch view to plain text mode 

and now I want allow to use this class in range for loop like that

Container container;
    for(const Data &data : container )
      qDebug()<< data.scope << data.name << data.value;

Container container;
    for(const Data &data : container )
      qDebug()<< data.scope << data.name << data.value;

To copy to clipboard, switch view to plain text mode 

but if I understand you correctly it will be very difficult.

[yeye_olive]

QPair can not be a key in my case.

Really? What about this:

class Container
{
public:
    void setData(const Data &data);
 
private:
    QHash<QPair<QString, QString>, Data> d;
 
};
 
void Container::setData(const Data &data)
{
    d.insert(qMakePair(data.scope, data.name), data);
}

class Container
{
public:
    void setData(const Data &data);

private:
    QHash<QPair<QString, QString>, Data> d;

};

void Container::setData(const Data &data)
{
    d.insert(qMakePair(data.scope, data.name), data);
}

To copy to clipboard, switch view to plain text mode 

And here is how you iterate on the container:

class Container {
    // ...
    public:
        using const_iterator = QHash<QPair<QString, QString>, Data>::const_iterator;
        const_iterator cbegin() const {return d.cbegin();}
        const_iterator cend() const {return d.cend();}
        const_iterator begin() const {return d.begin();}
        const_iterator end() const {return d.end();}
        // I omit the non-const iterators on purpose, because they would be more complex than const_iterator, as we have an invariant to maintain on d
    // ...
};
 
// ...
Container container;
// ...
for(const Data &data : static_cast<const Container &>(container))
    qDebug()<< data.scope << data.name << data.value;

class Container {
    // ...
    public:
        using const_iterator = QHash<QPair<QString, QString>, Data>::const_iterator;
        const_iterator cbegin() const {return d.cbegin();}
        const_iterator cend() const {return d.cend();}
        const_iterator begin() const {return d.begin();}
        const_iterator end() const {return d.end();}
        // I omit the non-const iterators on purpose, because they would be more complex than const_iterator, as we have an invariant to maintain on d
    // ...
};

// ...
Container container;
// ...
for(const Data &data : static_cast<const Container &>(container))
    qDebug()<< data.scope << data.name << data.value;

To copy to clipboard, switch view to plain text mode 

Disclaimer: I have not tried to compile these snippets.

[Scope]

Really? What about this:

Yes, because in my case, scope( first string ) must be unique and name of data ( second string ) also must be unique in their scope. Then your example with QPair as key has horrible bad performance and complexity when we compare this to nested hash.

[yeye_olive]

Yes, because in my case, scope( first string ) must be unique and name of data ( second string ) also must be unique in their scope.

Which is equivalent to saying that there must be only one Data for each unique (scope, name) combination. Which is why I suggested the pair as key in the first place.

Then your example with QPair as key has horrible bad performance and complexity when we compare this to nested hash.

How do you know? Have you run benchmarks? I would like to hear your argument, because I actually believe the opposite to be true in general. You do realize that a hash table has amortized constant average complexity, right? Besides, a flat QHash wastes less memory than nested ones.

If nesting was so much better, then we would never see things like QHash<QString, Foo>. Instead, people would use crazy structures like QHash<QString, QHash<QString, Foo> > in which you split the original string into two substrings to index into the two levels. But guess what, they don't.

Seriously though, there is nothing wrong with a hash table indexed by a pair of QStrings. It is about as efficient a structure as you can get with generic containers. As I already pointed out, nesting is useful if you have operations like slicing (e.g. quickly get all bindings for a given scope) or a very specific distribution of (scope, name) pairs. But all we know is that you are interested in iterating over the whole (flat) collection. Other people seem to agree with me:
http://stackoverflow.com/questions/2...han-nested-map
http://programmers.stackexchange.com...-combined-keys

But hey, if you want to waste your time with overly complex data structures with no gain in performance or memory usage (and most likely a loss), be my guest.

[Scope]

How do you know? Have you run benchmarks? I would like to hear your argument

As you said when we want take all values from specific scope

// with QPair as key
QList<Data> Container::data(const QString &scope)
{
    QList<Data> data;
    for( const QPair<QString, QString> &key : d.keys() )
        if( key.first == scope )
            data.append( d.value(key));
 
    return data;
}
 
// with nested QHash
QList<Data> Container::data(const QString &scope)
{
    if( d2.contains(scope) )
        return d2.value(scope).values();
 
    return QList<Data>();
}

// with QPair as key
QList<Data> Container::data(const QString &scope)
{
    QList<Data> data;
    for( const QPair<QString, QString> &key : d.keys() )
        if( key.first == scope )
            data.append( d.value(key));

    return data;
}

// with nested QHash
QList<Data> Container::data(const QString &scope)
{
    if( d2.contains(scope) )
        return d2.value(scope).values();

    return QList<Data>();
}

To copy to clipboard, switch view to plain text mode 

Maybe first version can be better using std::find_if or std::binary_search but second version is faster.
But maybe you have right that QPair as key is not worse as I said...

I am just trying find the best structure, for properties like scope, name and value.
Main goal is high performance for insert and lookup, and possibility use in range for loop.

[yeye_olive]

OK, if you need such slicing, then the nested QHashes are the reasonable solution; in that case your setData method would be more efficiently implemented by:

void Container::setData(const Data &data) {
    d[data.scope].insert(data.name, data);
}

void Container::setData(const Data &data) {
    d[data.scope].insert(data.name, data);
}

To copy to clipboard, switch view to plain text mode 

You could implement a flat iterator by a triple (see my first post).

[Scope]

Thank you very much,
I found in boost iterator_facade template and example

# include "node.hpp"
# include <boost/iterator/iterator_facade.hpp>
 
class node_iterator
  : public boost::iterator_facade<
        node_iterator
      , node_base
      , boost::forward_traversal_tag
    >
{
 public:
    node_iterator()
      : m_node(0) {}
 
    explicit node_iterator(node_base* p)
      : m_node(p) {}
 
 private:
    friend class boost::iterator_core_access;
 
    void increment() { m_node = m_node->next(); }
 
    bool equal(node_iterator const& other) const
    {
        return this->m_node == other.m_node;
    }
 
    node_base& dereference() const { return *m_node; }
 
    node_base* m_node;
};

# include "node.hpp"
# include <boost/iterator/iterator_facade.hpp>

class node_iterator
  : public boost::iterator_facade<
        node_iterator
      , node_base
      , boost::forward_traversal_tag
    >
{
 public:
    node_iterator()
      : m_node(0) {}

    explicit node_iterator(node_base* p)
      : m_node(p) {}

 private:
    friend class boost::iterator_core_access;

    void increment() { m_node = m_node->next(); }

    bool equal(node_iterator const& other) const
    {
        return this->m_node == other.m_node;
    }

    node_base& dereference() const { return *m_node; }

    node_base* m_node;
};

To copy to clipboard, switch view to plain text mode 

but i did not know how jump from end of one QHash to begin another?

[yeye_olive]

Here you go, a proof of concept in pseudocode of the flat const iterator. It only supports dereferencing and incrementation. It is in fact a quadruple (current and end iterator for outer and inner maps):

Data members:
    // Iterator on the outer QHash
    QHash<QString, QHash<QString, Data> >::const_iterator m_outer;
    // End iterator on the outer QHash
    QHash<QString, QHash<QString, Data> >::const_iterator m_outerEnd;
    // Iterator on the inner QHash. Has an indeterminate value if m_outer == m_outerEnd; otherwise, points to the current binding in the current inner map
    QHash<QString, Data>::const_iterator m_inner;
    // End iterator on the inner QHash. Has an indeterminate value if m_outer == m_outerEnd; otherwise, is the end() iterator of the current inner map
    QHash<QString, Data>::const_iterator m_innerEnd;
 
// Dereferences the iterator; assumes m_outer != m_outerEnd
Dereference:
    Return *m_inner
 
// Tests for equality with another iterator on the same container
Equals(const const_iterator &other):
    If m_outer == m_outerEnd
        Return other.m_outer == other.m_outerEnd
    Else
        Return m_outer == other.m_outer && m_inner == other.m_inner
 
// A private operation that updates the state right after m_outer has received a new value
NewOuter:
    While m_outer != m_outerEnd
        m_inner = m_outer->begin()
        m_innerEnd = m_outer->end()
        If m_inner != m_innerEnd
            Break
        Increment m_outer
 
// Sets up this iterator at the beginning of the collection c
Begin(const QHash<QString, QHash<QString, Data> > &c):
    m_outer = c.begin()
    m_outerEnd = c.end()
    Call NewOuter
 
// Sets up this iterator at the end of the collection c
End(const QHash<QString, QHash<QString, Data> > &c):
    m_outer = m_outerEnd = c.end()
 
// Increments this iterator; assumes m_outer != m_outerEnd
Increment:
    Increment m_inner
    If m_inner == m_innerEnd
        // Done iterating on the current inner map; move to the next outer binding
        Increment m_outer
        Call NewOuter

Data members:
    // Iterator on the outer QHash
    QHash<QString, QHash<QString, Data> >::const_iterator m_outer;
    // End iterator on the outer QHash
    QHash<QString, QHash<QString, Data> >::const_iterator m_outerEnd;
    // Iterator on the inner QHash. Has an indeterminate value if m_outer == m_outerEnd; otherwise, points to the current binding in the current inner map
    QHash<QString, Data>::const_iterator m_inner;
    // End iterator on the inner QHash. Has an indeterminate value if m_outer == m_outerEnd; otherwise, is the end() iterator of the current inner map
    QHash<QString, Data>::const_iterator m_innerEnd;

// Dereferences the iterator; assumes m_outer != m_outerEnd
Dereference:
    Return *m_inner

// Tests for equality with another iterator on the same container
Equals(const const_iterator &other):
    If m_outer == m_outerEnd
        Return other.m_outer == other.m_outerEnd
    Else
        Return m_outer == other.m_outer && m_inner == other.m_inner

// A private operation that updates the state right after m_outer has received a new value
NewOuter:
    While m_outer != m_outerEnd
        m_inner = m_outer->begin()
        m_innerEnd = m_outer->end()
        If m_inner != m_innerEnd
            Break
        Increment m_outer

// Sets up this iterator at the beginning of the collection c
Begin(const QHash<QString, QHash<QString, Data> > &c):
    m_outer = c.begin()
    m_outerEnd = c.end()
    Call NewOuter

// Sets up this iterator at the end of the collection c
End(const QHash<QString, QHash<QString, Data> > &c):
    m_outer = m_outerEnd = c.end()

// Increments this iterator; assumes m_outer != m_outerEnd
Increment:
    Increment m_inner
    If m_inner == m_innerEnd
        // Done iterating on the current inner map; move to the next outer binding
        Increment m_outer
        Call NewOuter

To copy to clipboard, switch view to plain text mode