Comments (9)
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:
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.
Related Issues (20)
- MSVC-12 ICE after 1.70
- UB due to union based type punning HOT 1
- constexpr HOT 1
- Problem with MSVC 19.26.28806 HOT 1
- Invalid casting in BOOST_INTRUSIVE_BSR_INTRINSIC
- *set.rbegin() looks like O(log(N)) HOT 1
- Add noexcept support to the library HOT 5
- Licensing question for math.hpp HOT 1
- nop splice removes element HOT 4
- [Feature request] punch hole hook for aggregates HOT 1
- pointer_rebinder does not support types of the form template<class T, int N> HOT 1
- Extend traits class to support custom logic after swaps and rotations
- Latest commit `01b4f62` breaks Interprocess, Unordered HOT 6
- Support B+ tree HOT 1
- Move constructor of list hook is missing
- Bug: Rehashing an empty unordered_set with `cache_begin` set to true hits an assert HOT 1
- One test fails to compile due to errors C2976 C3203 C2516 C2039 C3646 C4430 C2873 C2131 with latset reversion on boost master branch HOT 1
- boost/intrusive/hashtable.hpp: build failure (undeclared indentifier) HOT 2
- <functional> might not be included soon enough when building treap_multiset_test.cpp HOT 1
- unordered_set rehash breaks insert_commit_data HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from intrusive.