key_of_value on treap_set seems to be broken in 1.69 about intrusive HOT 9 CLOSED

Looking further, this seems to have been introduced in 4cf3898

The priority comparison function changed from being defined on T to being defined on key_type. Surely this is a mistake?

To go down this path, it seems like there should he priority_of_value option to match key_of_value.

from intrusive.

I have a possible fix in commit jm-mikkelsen@d3bd80d

from intrusive.

Thanks for the report. I previously thought that priority should always go with key_type, but maybe you are right, the correct approach would to have a priority_of_value option. The default could to use value_type for priority comparisons.

from intrusive.

My pull request is after my priority_of_value thought ... It is much more simple.

from intrusive.

You commit seems to fail in integration tests (https://travis-ci.org/boostorg/intrusive/builds/489375350?utm_source=github_status&utm_medium=notification).

from intrusive.

Yes, it does. I did not consider insert_check().

The underlying problem is that insert_unique_check() in treap_algorithms.hpp calls rebalance_after_insertion_checks() if the insertion is successful, which requires a full value object because priority comparison is defined in terms of a reference to the full value object, not just the key.

The changes to insert_unique_check() are obviously wrong when I consider how they are used from insert_unique(). It seems to me that the call at to rebalance_after_insertion_checks can be moved to the beginning of treap_algortihms::insert_unique_commit(). This should be OK because commit_data only remains valid while there are no insertions or deletions in the tree.

Does this sound reasonable?

from intrusive.

I updated the pull request to implement priority_of_value with the same defaults as key_of_value. The default uses value_type.

This issue with this patch at the moment is that the sizeof(treap) tests fail because I added a member variable to avoid an ambiguous base class. It is it possible for the value comparison and the priority comparison base classes to have the same type. Adding a wrapper and using a base class should resolve this issue, but I wanted to check that this basic approach was OK before going further.

from intrusive.

Many thanks for the patch. Based on your patch I've prepared commit:

3618260

The main change is that some "insert_check/insert_unique_check" overloads need an additional priority parameter apart from the priority comparison, since the priority is a different attribute that can be obtained from a different method. By default priority_of_value is the identity operation, so your test case now compiles fine.

Using priority_of_value your example would become:

#include <boost/intrusive/treap_set.hpp>
#include <string>

using namespace boost::intrusive;

class Test : public bs_set_base_hook<>
{
public:
    Test(int priority, std::string key) :
	m_priority(priority), m_key(std::move(key))
    {
    }

    int priority() const { return m_priority; }
    std::string const& key() const { return m_key; }

private:
    int m_priority;
    std::string m_key;
};

struct PriorityOrder
{
    bool operator()(int const& lhs, int const& rhs) const {
	return lhs < rhs;
    }
};

struct StringKey
{
    using type = std::string;

    type const& operator()(Test const& v) const {
	return v.key();
    }
};

struct IntPrio
{
    using type = int;

    type operator()(Test const& v) const {
	   return v.priority();
    }
};

int main()
{
    Test t1(1, "hello");
    treap_set<Test, key_of_value<StringKey>, priority_of_value<IntPrio>, priority<PriorityOrder>> s;
    s.insert(t1);
}

from intrusive.

Thanks for making the change. You didn't take the tagging ebo_functor_holder. That breaks code where the key comparison and the priority comparison are the same type. I will open another issue.

from intrusive.