Why can't I use std::function as a std::set or std::unordered_set value type?
Why can't I have a std::set
or std::unordered_set
of std::function
s?
Is there any way to get it to work anyway?
c++ unordered-map std-function stdset
|
show 6 more comments
Why can't I have a std::set
or std::unordered_set
of std::function
s?
Is there any way to get it to work anyway?
c++ unordered-map std-function stdset
3
What do you mean with doesn't work?
– JVApen
Nov 24 at 15:35
6
Because you can't applystd::less
(needed bystd::set
) norstd::hash
andstd::equal_to
(needed bystd::unordered_set
) to it.
– HolyBlackCat
Nov 24 at 15:37
1
@Qix: compile errors would really be useful!
– JVApen
Nov 24 at 15:41
4
@Qix Take the case forstd::set
. What makes one function "less than" another? What would be the criteria?
– PaulMcKenzie
Nov 24 at 15:42
3
What are you trying to achieve by using a set? If yourstd::function
has state, then you might never get the same key/hash value thus making a set useless. Why not use a vector? If you want to identifying functions, then a map with incremental ID as the key might be more appropriate. You would keep the id as a reference to the actual function.
– Phil1970
Nov 24 at 16:01
|
show 6 more comments
Why can't I have a std::set
or std::unordered_set
of std::function
s?
Is there any way to get it to work anyway?
c++ unordered-map std-function stdset
Why can't I have a std::set
or std::unordered_set
of std::function
s?
Is there any way to get it to work anyway?
c++ unordered-map std-function stdset
c++ unordered-map std-function stdset
edited Nov 24 at 17:32
Deduplicator
34k64787
34k64787
asked Nov 24 at 15:34
Qix
7,2621158113
7,2621158113
3
What do you mean with doesn't work?
– JVApen
Nov 24 at 15:35
6
Because you can't applystd::less
(needed bystd::set
) norstd::hash
andstd::equal_to
(needed bystd::unordered_set
) to it.
– HolyBlackCat
Nov 24 at 15:37
1
@Qix: compile errors would really be useful!
– JVApen
Nov 24 at 15:41
4
@Qix Take the case forstd::set
. What makes one function "less than" another? What would be the criteria?
– PaulMcKenzie
Nov 24 at 15:42
3
What are you trying to achieve by using a set? If yourstd::function
has state, then you might never get the same key/hash value thus making a set useless. Why not use a vector? If you want to identifying functions, then a map with incremental ID as the key might be more appropriate. You would keep the id as a reference to the actual function.
– Phil1970
Nov 24 at 16:01
|
show 6 more comments
3
What do you mean with doesn't work?
– JVApen
Nov 24 at 15:35
6
Because you can't applystd::less
(needed bystd::set
) norstd::hash
andstd::equal_to
(needed bystd::unordered_set
) to it.
– HolyBlackCat
Nov 24 at 15:37
1
@Qix: compile errors would really be useful!
– JVApen
Nov 24 at 15:41
4
@Qix Take the case forstd::set
. What makes one function "less than" another? What would be the criteria?
– PaulMcKenzie
Nov 24 at 15:42
3
What are you trying to achieve by using a set? If yourstd::function
has state, then you might never get the same key/hash value thus making a set useless. Why not use a vector? If you want to identifying functions, then a map with incremental ID as the key might be more appropriate. You would keep the id as a reference to the actual function.
– Phil1970
Nov 24 at 16:01
3
3
What do you mean with doesn't work?
– JVApen
Nov 24 at 15:35
What do you mean with doesn't work?
– JVApen
Nov 24 at 15:35
6
6
Because you can't apply
std::less
(needed by std::set
) nor std::hash
and std::equal_to
(needed by std::unordered_set
) to it.– HolyBlackCat
Nov 24 at 15:37
Because you can't apply
std::less
(needed by std::set
) nor std::hash
and std::equal_to
(needed by std::unordered_set
) to it.– HolyBlackCat
Nov 24 at 15:37
1
1
@Qix: compile errors would really be useful!
– JVApen
Nov 24 at 15:41
@Qix: compile errors would really be useful!
– JVApen
Nov 24 at 15:41
4
4
@Qix Take the case for
std::set
. What makes one function "less than" another? What would be the criteria?– PaulMcKenzie
Nov 24 at 15:42
@Qix Take the case for
std::set
. What makes one function "less than" another? What would be the criteria?– PaulMcKenzie
Nov 24 at 15:42
3
3
What are you trying to achieve by using a set? If your
std::function
has state, then you might never get the same key/hash value thus making a set useless. Why not use a vector? If you want to identifying functions, then a map with incremental ID as the key might be more appropriate. You would keep the id as a reference to the actual function.– Phil1970
Nov 24 at 16:01
What are you trying to achieve by using a set? If your
std::function
has state, then you might never get the same key/hash value thus making a set useless. Why not use a vector? If you want to identifying functions, then a map with incremental ID as the key might be more appropriate. You would keep the id as a reference to the actual function.– Phil1970
Nov 24 at 16:01
|
show 6 more comments
4 Answers
4
active
oldest
votes
Why can't I have a
std::set
orstd::unordered_set
ofstd::function
s?
std::set
relies on a comparator, which is used to determine if one element is less than the other.
It uses std::less
by default, and std::less
doesn't work with std::function
s.
(Because there is no way to properly compare std::function
s.)
Similarly, std::unordered_set
relies on std::hash
and std::equal_to
(or custom replacements for them), which also don't operate on std::function
s.
Is there any way to get it to work anyway?
You can write a wrapper around (or a replacement for) std::function
that works with std::less
, std::equal_to
and/or std::hash
.
Via power of type erasure, you can forward std::less
/std::equal_to
/std::hash
to objects stored in your wrapper.
Here's a proof-of-concept for such a wrapper.
Notes:
You can specify whether or not you want the
class FancyFunction
to work withstd::less
,std::equal_to
andstd::hash
separetely, by adjusting a template argument.
If some of those is enabled, you'll be able to apply them toFancyFunction
.
Naturally, you'll be able to construct
FancyFunction
from a type only if they can be applied to that type.
There is a static assertion that fires when a type fails to provide
std::hash
if it's needed.
It seems to be impossible to SFINAE on availability ofstd::less
andstd::equal_to
, so I couldn't make similar assertions for those.
In theory, you could support types that don't work with
std::less
,std::equal_to
and/orstd::hash
by always considering all instances of one type equivalent, and usingtypeid(T).hash_code()
as a hash.
I'm not sure if that behavior is desirable or not, implementing it is left as an exercise to the reader.
(Lack of SFINAE forstd::less
andstd::equal_to
will make it harder to implement properly.)
Specifying custom replacements for
std::less
,std::equal_to
andstd::hash
is not supported, implementing that is also left as an exercise to the reader.
(This means that this implementation can only be used to put lambdas into a regular
std::set
, notstd::unordered_set
.)
When applied to
FancyFunction
,std::less
andstd::equal_to
will first compare types of stored functors.
If types are identical, they'll resort to calling
std::less
/std::equal_to
on underlying instances.
(Thus, for two arbitrary different functor types,
std::less
will always consider instances of one of them less than instances of the other one. The order is not stable between program invocations.)
Example usage:
// With `std::set`:
#include <iostream>
#include <set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator<(AddN a, AddN b) {return a.n < b.n;}
};
int main()
{
using func_t = FancyFunction<int(int), FunctionFlags::comparable_less>;
// Note that `std::less` can operate on stateless lambdas by converting them to function pointers first. Otherwise this wouldn't work.
auto square = (int x){return x*x;};
auto cube = (int x){return x*x*x;};
std::set<func_t> set;
set.insert(square);
set.insert(square); // Dupe.
set.insert(cube);
set.insert(AddN{100});
set.insert(AddN{200});
set.insert(AddN{200}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`, note that it appears only once.
* 2 -> 8 // `cube`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`, also appears once.
*/
set.erase(set.find(cube));
set.erase(set.find(AddN{100}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`
* 2 -> 202 // `AddN{200}`
* `cube` and `AddN{100}` were removed.
*/
}
// With `std::unordered_set`:
#include <iostream>
#include <unordered_set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator==(AddN a, AddN b) {return a.n == b.n;}
};
struct MulByN
{
int n;
int operator()(int x) const {return n * x;}
friend bool operator==(MulByN a, MulByN b) {return a.n == b.n;}
};
namespace std
{
template <> struct hash<AddN>
{
using argument_type = AddN;
using result_type = std::size_t;
size_t operator()(AddN f) const {return f.n;}
};
template <> struct hash<MulByN>
{
using argument_type = MulByN;
using result_type = std::size_t;
size_t operator()(MulByN f) const {return f.n;}
};
}
int main()
{
using hashable_func_t = FancyFunction<int(int), FunctionFlags::hashable | FunctionFlags::comparable_eq>;
std::unordered_set<hashable_func_t> set;
set.insert(AddN{100});
set.insert(AddN{100}); // Dupe.
set.insert(AddN{200});
set.insert(MulByN{10});
set.insert(MulByN{20});
set.insert(MulByN{20}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 40 // `MulByN{20}`
* 2 -> 20 // `MulByN{10}`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`
*/
set.erase(set.find(AddN{100}));
set.erase(set.find(MulByN{20}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 20 // `MulByN{10}`
* 2 -> 202 // `AddN{200}`
* `MulByN{20}` and `AddN{100}` were removed.
*/
}
Implementation:
#include <cstddef>
#include <functional>
#include <experimental/type_traits>
#include <utility>
enum class FunctionFlags
{
none = 0,
comparable_less = 0b1,
comparable_eq = 0b10,
hashable = 0b100,
};
constexpr FunctionFlags operator|(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) | int(b));}
constexpr FunctionFlags operator&(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) & int(b));}
template <typename T> using detect_hashable = decltype(std::hash<T>{}(std::declval<const T &>()));
template <typename T, FunctionFlags Flags = FunctionFlags::none>
class FancyFunction;
template <typename ReturnType, typename ...ParamTypes, FunctionFlags Flags>
class FancyFunction<ReturnType(ParamTypes...), Flags>
{
struct TypeDetails
{
int index = 0;
bool (*less)(const void *, const void *) = 0;
bool (*eq)(const void *, const void *) = 0;
std::size_t (*hash)(const void *) = 0;
inline static int index_counter = 0;
};
template <typename T> const TypeDetails *GetDetails()
{
static TypeDetails ret = ()
{
using type = std::remove_cv_t<std::remove_reference_t<T>>;
TypeDetails d;
d.index = TypeDetails::index_counter++;
if constexpr (comparable_less)
{
// We can't SFINAE on `std::less`.
d.less = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::less<type>{}(a, b);
};
}
if constexpr (comparable_eq)
{
// We can't SFINAE on `std::equal_to`.
d.eq = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::equal_to<type>{}(a, b);
};
}
if constexpr (hashable)
{
static_assert(std::experimental::is_detected_v<detect_hashable, type>, "This type is not hashable.");
d.hash = (const void *a_ptr) -> std::size_t
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
return std::hash<type>(a);
};
}
return d;
}();
return &ret;
}
std::function<ReturnType(ParamTypes...)> func;
const TypeDetails *details = 0;
public:
inline static constexpr bool
comparable_less = bool(Flags & FunctionFlags::comparable_less),
comparable_eq = bool(Flags & FunctionFlags::comparable_eq),
hashable = bool(Flags & FunctionFlags::hashable);
FancyFunction(decltype(nullptr) = nullptr) {}
template <typename T>
FancyFunction(T &&obj)
{
func = std::forward<T>(obj);
details = GetDetails<T>();
}
explicit operator bool() const
{
return bool(func);
}
ReturnType operator()(ParamTypes ... params) const
{
return ReturnType(func(std::forward<ParamTypes>(params)...));
}
bool less(const FancyFunction &other) const
{
static_assert(comparable_less, "This function is disabled.");
if (int delta = bool(details) - bool(other.details)) return delta < 0;
if (!details) return 0;
if (int delta = details->index - other.details->index) return delta < 0;
return details->less(this, &other);
}
bool equal_to(const FancyFunction &other) const
{
static_assert(comparable_eq, "This function is disabled.");
if (bool(details) != bool(other.details)) return 0;
if (!details) return 1;
if (details->index != other.details->index) return 0;
return details->eq(this, &other);
}
std::size_t hash() const
{
static_assert(hashable, "This function is disabled.");
if (!details) return 0;
return details->hash(this);
}
friend bool operator<(const FancyFunction &a, const FancyFunction &b) {return a.less(b);}
friend bool operator>(const FancyFunction &a, const FancyFunction &b) {return b.less(a);}
friend bool operator<=(const FancyFunction &a, const FancyFunction &b) {return !b.less(a);}
friend bool operator>=(const FancyFunction &a, const FancyFunction &b) {return !a.less(b);}
friend bool operator==(const FancyFunction &a, const FancyFunction &b) {return a.equal_to(b);}
friend bool operator!=(const FancyFunction &a, const FancyFunction &b) {return !a.equal_to(b);}
};
namespace std
{
template <typename T, FunctionFlags Flags> struct hash<FancyFunction<T, Flags>>
{
using argument_type = FancyFunction<T, Flags>;
using result_type = std::size_t;
size_t operator()(const FancyFunction<T, Flags> &f) const
{
return f.hash();
}
};
}
This is the most complete answer here. Thank you for taking the time! :)
– Qix
Nov 25 at 13:09
@HolyBlackCat That was really nice.
– JeJo
Nov 26 at 9:41
add a comment |
You can very well create an std::set
of functions. The problem is that sets require an absolute order to exist between the values of its elements. This order is defined by a comparator that is then used to sort the elements of a set, to check if an element already exists, and to find a specific element back.
Unfortunately, there doesn't exist an order between functions. Suppose, that you have two functions f1()
and f2()
, what would be the meaning of f1 < f2
?
Also equality is not really defined. For example, if you have
int fun1(int) { return 1; }
int fun2(int) { return 1; }
function<int(int)> f1=fun1, f2=fun2;
Should f1 and f2 be the same value if you'd insert them in a set (because it's always the same result), or is it something different (because it's different functions even though they have the same body) ?
Of course, you could trick the compiler in letting it believe that you have defined an order:
struct Comp {
using T = function<int(int)>;
bool operator()(const T &lhs, const T &rhs) const
{
return &lhs < &rhs;
}
};
set <function<int(int)>,Comp> s;
You could then insert functions in the set. But this will not work very well, because you take the address of the element, and if the same elements are swapped, the order is different.
I think that the best way to proceed, would be to use a wrapper with a member string that defines an id and use this id to sort the elements in the set (or to do the hashing in case of an unordered_set
)
add a comment |
Well, you can only check function-pointers for (in-)equality, not order. And whether two functions with the same behavior must compare differently is not quite as cut-and-dry as you might perhaps hope for.
Next, you might not only store function-pointers, but also other callables. There is no guarantee any random user-defined class has a strict weak ordering. As an example, lambdas don't.
And finally, how would you order callables of different types?
You can make the same Argument for hashing (needed for unordered containers) as for ordering (needed for ordered containers). Even the equality-comparison needed for unordered containers might not exist.
add a comment |
There is no meaningful equality operation for the general function, held by a std::function
.
- C++ functions aren't mathematical functions. What if the "function" holds state? And that state is different for different instances?
- To your suggestion of using the "entry point address": Again, consider state. A
std::function
can hold a bind of some function/method to some parameters. What is the "entry point address" of that? Ans: Some function/method in the "bind" package. And does then that "entry point address" uniquely identify that function? Ans: No. - Suppose you have two different functions (by "entry point address") that in fact are identical in the sense that they produce the same result for every parameter? They may even be the same source code - or machine code. Are those functions equal, or not? (If not, why not, if they're behaviorally identical and can't be distinguished by any caller?)
Your particular use case (for sticking std::function
in a set) may not be impacted by the above issues. In that case simply wrap the std::function
instance in a small struct of your own (either via direct containment or via indirection) (forwarding calls to the contained function object) and put those things in your set.
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53459693%2fwhy-cant-i-use-stdfunction-as-a-stdset-or-stdunordered-set-value-type%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
Why can't I have a
std::set
orstd::unordered_set
ofstd::function
s?
std::set
relies on a comparator, which is used to determine if one element is less than the other.
It uses std::less
by default, and std::less
doesn't work with std::function
s.
(Because there is no way to properly compare std::function
s.)
Similarly, std::unordered_set
relies on std::hash
and std::equal_to
(or custom replacements for them), which also don't operate on std::function
s.
Is there any way to get it to work anyway?
You can write a wrapper around (or a replacement for) std::function
that works with std::less
, std::equal_to
and/or std::hash
.
Via power of type erasure, you can forward std::less
/std::equal_to
/std::hash
to objects stored in your wrapper.
Here's a proof-of-concept for such a wrapper.
Notes:
You can specify whether or not you want the
class FancyFunction
to work withstd::less
,std::equal_to
andstd::hash
separetely, by adjusting a template argument.
If some of those is enabled, you'll be able to apply them toFancyFunction
.
Naturally, you'll be able to construct
FancyFunction
from a type only if they can be applied to that type.
There is a static assertion that fires when a type fails to provide
std::hash
if it's needed.
It seems to be impossible to SFINAE on availability ofstd::less
andstd::equal_to
, so I couldn't make similar assertions for those.
In theory, you could support types that don't work with
std::less
,std::equal_to
and/orstd::hash
by always considering all instances of one type equivalent, and usingtypeid(T).hash_code()
as a hash.
I'm not sure if that behavior is desirable or not, implementing it is left as an exercise to the reader.
(Lack of SFINAE forstd::less
andstd::equal_to
will make it harder to implement properly.)
Specifying custom replacements for
std::less
,std::equal_to
andstd::hash
is not supported, implementing that is also left as an exercise to the reader.
(This means that this implementation can only be used to put lambdas into a regular
std::set
, notstd::unordered_set
.)
When applied to
FancyFunction
,std::less
andstd::equal_to
will first compare types of stored functors.
If types are identical, they'll resort to calling
std::less
/std::equal_to
on underlying instances.
(Thus, for two arbitrary different functor types,
std::less
will always consider instances of one of them less than instances of the other one. The order is not stable between program invocations.)
Example usage:
// With `std::set`:
#include <iostream>
#include <set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator<(AddN a, AddN b) {return a.n < b.n;}
};
int main()
{
using func_t = FancyFunction<int(int), FunctionFlags::comparable_less>;
// Note that `std::less` can operate on stateless lambdas by converting them to function pointers first. Otherwise this wouldn't work.
auto square = (int x){return x*x;};
auto cube = (int x){return x*x*x;};
std::set<func_t> set;
set.insert(square);
set.insert(square); // Dupe.
set.insert(cube);
set.insert(AddN{100});
set.insert(AddN{200});
set.insert(AddN{200}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`, note that it appears only once.
* 2 -> 8 // `cube`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`, also appears once.
*/
set.erase(set.find(cube));
set.erase(set.find(AddN{100}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`
* 2 -> 202 // `AddN{200}`
* `cube` and `AddN{100}` were removed.
*/
}
// With `std::unordered_set`:
#include <iostream>
#include <unordered_set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator==(AddN a, AddN b) {return a.n == b.n;}
};
struct MulByN
{
int n;
int operator()(int x) const {return n * x;}
friend bool operator==(MulByN a, MulByN b) {return a.n == b.n;}
};
namespace std
{
template <> struct hash<AddN>
{
using argument_type = AddN;
using result_type = std::size_t;
size_t operator()(AddN f) const {return f.n;}
};
template <> struct hash<MulByN>
{
using argument_type = MulByN;
using result_type = std::size_t;
size_t operator()(MulByN f) const {return f.n;}
};
}
int main()
{
using hashable_func_t = FancyFunction<int(int), FunctionFlags::hashable | FunctionFlags::comparable_eq>;
std::unordered_set<hashable_func_t> set;
set.insert(AddN{100});
set.insert(AddN{100}); // Dupe.
set.insert(AddN{200});
set.insert(MulByN{10});
set.insert(MulByN{20});
set.insert(MulByN{20}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 40 // `MulByN{20}`
* 2 -> 20 // `MulByN{10}`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`
*/
set.erase(set.find(AddN{100}));
set.erase(set.find(MulByN{20}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 20 // `MulByN{10}`
* 2 -> 202 // `AddN{200}`
* `MulByN{20}` and `AddN{100}` were removed.
*/
}
Implementation:
#include <cstddef>
#include <functional>
#include <experimental/type_traits>
#include <utility>
enum class FunctionFlags
{
none = 0,
comparable_less = 0b1,
comparable_eq = 0b10,
hashable = 0b100,
};
constexpr FunctionFlags operator|(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) | int(b));}
constexpr FunctionFlags operator&(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) & int(b));}
template <typename T> using detect_hashable = decltype(std::hash<T>{}(std::declval<const T &>()));
template <typename T, FunctionFlags Flags = FunctionFlags::none>
class FancyFunction;
template <typename ReturnType, typename ...ParamTypes, FunctionFlags Flags>
class FancyFunction<ReturnType(ParamTypes...), Flags>
{
struct TypeDetails
{
int index = 0;
bool (*less)(const void *, const void *) = 0;
bool (*eq)(const void *, const void *) = 0;
std::size_t (*hash)(const void *) = 0;
inline static int index_counter = 0;
};
template <typename T> const TypeDetails *GetDetails()
{
static TypeDetails ret = ()
{
using type = std::remove_cv_t<std::remove_reference_t<T>>;
TypeDetails d;
d.index = TypeDetails::index_counter++;
if constexpr (comparable_less)
{
// We can't SFINAE on `std::less`.
d.less = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::less<type>{}(a, b);
};
}
if constexpr (comparable_eq)
{
// We can't SFINAE on `std::equal_to`.
d.eq = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::equal_to<type>{}(a, b);
};
}
if constexpr (hashable)
{
static_assert(std::experimental::is_detected_v<detect_hashable, type>, "This type is not hashable.");
d.hash = (const void *a_ptr) -> std::size_t
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
return std::hash<type>(a);
};
}
return d;
}();
return &ret;
}
std::function<ReturnType(ParamTypes...)> func;
const TypeDetails *details = 0;
public:
inline static constexpr bool
comparable_less = bool(Flags & FunctionFlags::comparable_less),
comparable_eq = bool(Flags & FunctionFlags::comparable_eq),
hashable = bool(Flags & FunctionFlags::hashable);
FancyFunction(decltype(nullptr) = nullptr) {}
template <typename T>
FancyFunction(T &&obj)
{
func = std::forward<T>(obj);
details = GetDetails<T>();
}
explicit operator bool() const
{
return bool(func);
}
ReturnType operator()(ParamTypes ... params) const
{
return ReturnType(func(std::forward<ParamTypes>(params)...));
}
bool less(const FancyFunction &other) const
{
static_assert(comparable_less, "This function is disabled.");
if (int delta = bool(details) - bool(other.details)) return delta < 0;
if (!details) return 0;
if (int delta = details->index - other.details->index) return delta < 0;
return details->less(this, &other);
}
bool equal_to(const FancyFunction &other) const
{
static_assert(comparable_eq, "This function is disabled.");
if (bool(details) != bool(other.details)) return 0;
if (!details) return 1;
if (details->index != other.details->index) return 0;
return details->eq(this, &other);
}
std::size_t hash() const
{
static_assert(hashable, "This function is disabled.");
if (!details) return 0;
return details->hash(this);
}
friend bool operator<(const FancyFunction &a, const FancyFunction &b) {return a.less(b);}
friend bool operator>(const FancyFunction &a, const FancyFunction &b) {return b.less(a);}
friend bool operator<=(const FancyFunction &a, const FancyFunction &b) {return !b.less(a);}
friend bool operator>=(const FancyFunction &a, const FancyFunction &b) {return !a.less(b);}
friend bool operator==(const FancyFunction &a, const FancyFunction &b) {return a.equal_to(b);}
friend bool operator!=(const FancyFunction &a, const FancyFunction &b) {return !a.equal_to(b);}
};
namespace std
{
template <typename T, FunctionFlags Flags> struct hash<FancyFunction<T, Flags>>
{
using argument_type = FancyFunction<T, Flags>;
using result_type = std::size_t;
size_t operator()(const FancyFunction<T, Flags> &f) const
{
return f.hash();
}
};
}
This is the most complete answer here. Thank you for taking the time! :)
– Qix
Nov 25 at 13:09
@HolyBlackCat That was really nice.
– JeJo
Nov 26 at 9:41
add a comment |
Why can't I have a
std::set
orstd::unordered_set
ofstd::function
s?
std::set
relies on a comparator, which is used to determine if one element is less than the other.
It uses std::less
by default, and std::less
doesn't work with std::function
s.
(Because there is no way to properly compare std::function
s.)
Similarly, std::unordered_set
relies on std::hash
and std::equal_to
(or custom replacements for them), which also don't operate on std::function
s.
Is there any way to get it to work anyway?
You can write a wrapper around (or a replacement for) std::function
that works with std::less
, std::equal_to
and/or std::hash
.
Via power of type erasure, you can forward std::less
/std::equal_to
/std::hash
to objects stored in your wrapper.
Here's a proof-of-concept for such a wrapper.
Notes:
You can specify whether or not you want the
class FancyFunction
to work withstd::less
,std::equal_to
andstd::hash
separetely, by adjusting a template argument.
If some of those is enabled, you'll be able to apply them toFancyFunction
.
Naturally, you'll be able to construct
FancyFunction
from a type only if they can be applied to that type.
There is a static assertion that fires when a type fails to provide
std::hash
if it's needed.
It seems to be impossible to SFINAE on availability ofstd::less
andstd::equal_to
, so I couldn't make similar assertions for those.
In theory, you could support types that don't work with
std::less
,std::equal_to
and/orstd::hash
by always considering all instances of one type equivalent, and usingtypeid(T).hash_code()
as a hash.
I'm not sure if that behavior is desirable or not, implementing it is left as an exercise to the reader.
(Lack of SFINAE forstd::less
andstd::equal_to
will make it harder to implement properly.)
Specifying custom replacements for
std::less
,std::equal_to
andstd::hash
is not supported, implementing that is also left as an exercise to the reader.
(This means that this implementation can only be used to put lambdas into a regular
std::set
, notstd::unordered_set
.)
When applied to
FancyFunction
,std::less
andstd::equal_to
will first compare types of stored functors.
If types are identical, they'll resort to calling
std::less
/std::equal_to
on underlying instances.
(Thus, for two arbitrary different functor types,
std::less
will always consider instances of one of them less than instances of the other one. The order is not stable between program invocations.)
Example usage:
// With `std::set`:
#include <iostream>
#include <set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator<(AddN a, AddN b) {return a.n < b.n;}
};
int main()
{
using func_t = FancyFunction<int(int), FunctionFlags::comparable_less>;
// Note that `std::less` can operate on stateless lambdas by converting them to function pointers first. Otherwise this wouldn't work.
auto square = (int x){return x*x;};
auto cube = (int x){return x*x*x;};
std::set<func_t> set;
set.insert(square);
set.insert(square); // Dupe.
set.insert(cube);
set.insert(AddN{100});
set.insert(AddN{200});
set.insert(AddN{200}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`, note that it appears only once.
* 2 -> 8 // `cube`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`, also appears once.
*/
set.erase(set.find(cube));
set.erase(set.find(AddN{100}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`
* 2 -> 202 // `AddN{200}`
* `cube` and `AddN{100}` were removed.
*/
}
// With `std::unordered_set`:
#include <iostream>
#include <unordered_set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator==(AddN a, AddN b) {return a.n == b.n;}
};
struct MulByN
{
int n;
int operator()(int x) const {return n * x;}
friend bool operator==(MulByN a, MulByN b) {return a.n == b.n;}
};
namespace std
{
template <> struct hash<AddN>
{
using argument_type = AddN;
using result_type = std::size_t;
size_t operator()(AddN f) const {return f.n;}
};
template <> struct hash<MulByN>
{
using argument_type = MulByN;
using result_type = std::size_t;
size_t operator()(MulByN f) const {return f.n;}
};
}
int main()
{
using hashable_func_t = FancyFunction<int(int), FunctionFlags::hashable | FunctionFlags::comparable_eq>;
std::unordered_set<hashable_func_t> set;
set.insert(AddN{100});
set.insert(AddN{100}); // Dupe.
set.insert(AddN{200});
set.insert(MulByN{10});
set.insert(MulByN{20});
set.insert(MulByN{20}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 40 // `MulByN{20}`
* 2 -> 20 // `MulByN{10}`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`
*/
set.erase(set.find(AddN{100}));
set.erase(set.find(MulByN{20}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 20 // `MulByN{10}`
* 2 -> 202 // `AddN{200}`
* `MulByN{20}` and `AddN{100}` were removed.
*/
}
Implementation:
#include <cstddef>
#include <functional>
#include <experimental/type_traits>
#include <utility>
enum class FunctionFlags
{
none = 0,
comparable_less = 0b1,
comparable_eq = 0b10,
hashable = 0b100,
};
constexpr FunctionFlags operator|(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) | int(b));}
constexpr FunctionFlags operator&(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) & int(b));}
template <typename T> using detect_hashable = decltype(std::hash<T>{}(std::declval<const T &>()));
template <typename T, FunctionFlags Flags = FunctionFlags::none>
class FancyFunction;
template <typename ReturnType, typename ...ParamTypes, FunctionFlags Flags>
class FancyFunction<ReturnType(ParamTypes...), Flags>
{
struct TypeDetails
{
int index = 0;
bool (*less)(const void *, const void *) = 0;
bool (*eq)(const void *, const void *) = 0;
std::size_t (*hash)(const void *) = 0;
inline static int index_counter = 0;
};
template <typename T> const TypeDetails *GetDetails()
{
static TypeDetails ret = ()
{
using type = std::remove_cv_t<std::remove_reference_t<T>>;
TypeDetails d;
d.index = TypeDetails::index_counter++;
if constexpr (comparable_less)
{
// We can't SFINAE on `std::less`.
d.less = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::less<type>{}(a, b);
};
}
if constexpr (comparable_eq)
{
// We can't SFINAE on `std::equal_to`.
d.eq = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::equal_to<type>{}(a, b);
};
}
if constexpr (hashable)
{
static_assert(std::experimental::is_detected_v<detect_hashable, type>, "This type is not hashable.");
d.hash = (const void *a_ptr) -> std::size_t
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
return std::hash<type>(a);
};
}
return d;
}();
return &ret;
}
std::function<ReturnType(ParamTypes...)> func;
const TypeDetails *details = 0;
public:
inline static constexpr bool
comparable_less = bool(Flags & FunctionFlags::comparable_less),
comparable_eq = bool(Flags & FunctionFlags::comparable_eq),
hashable = bool(Flags & FunctionFlags::hashable);
FancyFunction(decltype(nullptr) = nullptr) {}
template <typename T>
FancyFunction(T &&obj)
{
func = std::forward<T>(obj);
details = GetDetails<T>();
}
explicit operator bool() const
{
return bool(func);
}
ReturnType operator()(ParamTypes ... params) const
{
return ReturnType(func(std::forward<ParamTypes>(params)...));
}
bool less(const FancyFunction &other) const
{
static_assert(comparable_less, "This function is disabled.");
if (int delta = bool(details) - bool(other.details)) return delta < 0;
if (!details) return 0;
if (int delta = details->index - other.details->index) return delta < 0;
return details->less(this, &other);
}
bool equal_to(const FancyFunction &other) const
{
static_assert(comparable_eq, "This function is disabled.");
if (bool(details) != bool(other.details)) return 0;
if (!details) return 1;
if (details->index != other.details->index) return 0;
return details->eq(this, &other);
}
std::size_t hash() const
{
static_assert(hashable, "This function is disabled.");
if (!details) return 0;
return details->hash(this);
}
friend bool operator<(const FancyFunction &a, const FancyFunction &b) {return a.less(b);}
friend bool operator>(const FancyFunction &a, const FancyFunction &b) {return b.less(a);}
friend bool operator<=(const FancyFunction &a, const FancyFunction &b) {return !b.less(a);}
friend bool operator>=(const FancyFunction &a, const FancyFunction &b) {return !a.less(b);}
friend bool operator==(const FancyFunction &a, const FancyFunction &b) {return a.equal_to(b);}
friend bool operator!=(const FancyFunction &a, const FancyFunction &b) {return !a.equal_to(b);}
};
namespace std
{
template <typename T, FunctionFlags Flags> struct hash<FancyFunction<T, Flags>>
{
using argument_type = FancyFunction<T, Flags>;
using result_type = std::size_t;
size_t operator()(const FancyFunction<T, Flags> &f) const
{
return f.hash();
}
};
}
This is the most complete answer here. Thank you for taking the time! :)
– Qix
Nov 25 at 13:09
@HolyBlackCat That was really nice.
– JeJo
Nov 26 at 9:41
add a comment |
Why can't I have a
std::set
orstd::unordered_set
ofstd::function
s?
std::set
relies on a comparator, which is used to determine if one element is less than the other.
It uses std::less
by default, and std::less
doesn't work with std::function
s.
(Because there is no way to properly compare std::function
s.)
Similarly, std::unordered_set
relies on std::hash
and std::equal_to
(or custom replacements for them), which also don't operate on std::function
s.
Is there any way to get it to work anyway?
You can write a wrapper around (or a replacement for) std::function
that works with std::less
, std::equal_to
and/or std::hash
.
Via power of type erasure, you can forward std::less
/std::equal_to
/std::hash
to objects stored in your wrapper.
Here's a proof-of-concept for such a wrapper.
Notes:
You can specify whether or not you want the
class FancyFunction
to work withstd::less
,std::equal_to
andstd::hash
separetely, by adjusting a template argument.
If some of those is enabled, you'll be able to apply them toFancyFunction
.
Naturally, you'll be able to construct
FancyFunction
from a type only if they can be applied to that type.
There is a static assertion that fires when a type fails to provide
std::hash
if it's needed.
It seems to be impossible to SFINAE on availability ofstd::less
andstd::equal_to
, so I couldn't make similar assertions for those.
In theory, you could support types that don't work with
std::less
,std::equal_to
and/orstd::hash
by always considering all instances of one type equivalent, and usingtypeid(T).hash_code()
as a hash.
I'm not sure if that behavior is desirable or not, implementing it is left as an exercise to the reader.
(Lack of SFINAE forstd::less
andstd::equal_to
will make it harder to implement properly.)
Specifying custom replacements for
std::less
,std::equal_to
andstd::hash
is not supported, implementing that is also left as an exercise to the reader.
(This means that this implementation can only be used to put lambdas into a regular
std::set
, notstd::unordered_set
.)
When applied to
FancyFunction
,std::less
andstd::equal_to
will first compare types of stored functors.
If types are identical, they'll resort to calling
std::less
/std::equal_to
on underlying instances.
(Thus, for two arbitrary different functor types,
std::less
will always consider instances of one of them less than instances of the other one. The order is not stable between program invocations.)
Example usage:
// With `std::set`:
#include <iostream>
#include <set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator<(AddN a, AddN b) {return a.n < b.n;}
};
int main()
{
using func_t = FancyFunction<int(int), FunctionFlags::comparable_less>;
// Note that `std::less` can operate on stateless lambdas by converting them to function pointers first. Otherwise this wouldn't work.
auto square = (int x){return x*x;};
auto cube = (int x){return x*x*x;};
std::set<func_t> set;
set.insert(square);
set.insert(square); // Dupe.
set.insert(cube);
set.insert(AddN{100});
set.insert(AddN{200});
set.insert(AddN{200}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`, note that it appears only once.
* 2 -> 8 // `cube`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`, also appears once.
*/
set.erase(set.find(cube));
set.erase(set.find(AddN{100}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`
* 2 -> 202 // `AddN{200}`
* `cube` and `AddN{100}` were removed.
*/
}
// With `std::unordered_set`:
#include <iostream>
#include <unordered_set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator==(AddN a, AddN b) {return a.n == b.n;}
};
struct MulByN
{
int n;
int operator()(int x) const {return n * x;}
friend bool operator==(MulByN a, MulByN b) {return a.n == b.n;}
};
namespace std
{
template <> struct hash<AddN>
{
using argument_type = AddN;
using result_type = std::size_t;
size_t operator()(AddN f) const {return f.n;}
};
template <> struct hash<MulByN>
{
using argument_type = MulByN;
using result_type = std::size_t;
size_t operator()(MulByN f) const {return f.n;}
};
}
int main()
{
using hashable_func_t = FancyFunction<int(int), FunctionFlags::hashable | FunctionFlags::comparable_eq>;
std::unordered_set<hashable_func_t> set;
set.insert(AddN{100});
set.insert(AddN{100}); // Dupe.
set.insert(AddN{200});
set.insert(MulByN{10});
set.insert(MulByN{20});
set.insert(MulByN{20}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 40 // `MulByN{20}`
* 2 -> 20 // `MulByN{10}`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`
*/
set.erase(set.find(AddN{100}));
set.erase(set.find(MulByN{20}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 20 // `MulByN{10}`
* 2 -> 202 // `AddN{200}`
* `MulByN{20}` and `AddN{100}` were removed.
*/
}
Implementation:
#include <cstddef>
#include <functional>
#include <experimental/type_traits>
#include <utility>
enum class FunctionFlags
{
none = 0,
comparable_less = 0b1,
comparable_eq = 0b10,
hashable = 0b100,
};
constexpr FunctionFlags operator|(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) | int(b));}
constexpr FunctionFlags operator&(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) & int(b));}
template <typename T> using detect_hashable = decltype(std::hash<T>{}(std::declval<const T &>()));
template <typename T, FunctionFlags Flags = FunctionFlags::none>
class FancyFunction;
template <typename ReturnType, typename ...ParamTypes, FunctionFlags Flags>
class FancyFunction<ReturnType(ParamTypes...), Flags>
{
struct TypeDetails
{
int index = 0;
bool (*less)(const void *, const void *) = 0;
bool (*eq)(const void *, const void *) = 0;
std::size_t (*hash)(const void *) = 0;
inline static int index_counter = 0;
};
template <typename T> const TypeDetails *GetDetails()
{
static TypeDetails ret = ()
{
using type = std::remove_cv_t<std::remove_reference_t<T>>;
TypeDetails d;
d.index = TypeDetails::index_counter++;
if constexpr (comparable_less)
{
// We can't SFINAE on `std::less`.
d.less = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::less<type>{}(a, b);
};
}
if constexpr (comparable_eq)
{
// We can't SFINAE on `std::equal_to`.
d.eq = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::equal_to<type>{}(a, b);
};
}
if constexpr (hashable)
{
static_assert(std::experimental::is_detected_v<detect_hashable, type>, "This type is not hashable.");
d.hash = (const void *a_ptr) -> std::size_t
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
return std::hash<type>(a);
};
}
return d;
}();
return &ret;
}
std::function<ReturnType(ParamTypes...)> func;
const TypeDetails *details = 0;
public:
inline static constexpr bool
comparable_less = bool(Flags & FunctionFlags::comparable_less),
comparable_eq = bool(Flags & FunctionFlags::comparable_eq),
hashable = bool(Flags & FunctionFlags::hashable);
FancyFunction(decltype(nullptr) = nullptr) {}
template <typename T>
FancyFunction(T &&obj)
{
func = std::forward<T>(obj);
details = GetDetails<T>();
}
explicit operator bool() const
{
return bool(func);
}
ReturnType operator()(ParamTypes ... params) const
{
return ReturnType(func(std::forward<ParamTypes>(params)...));
}
bool less(const FancyFunction &other) const
{
static_assert(comparable_less, "This function is disabled.");
if (int delta = bool(details) - bool(other.details)) return delta < 0;
if (!details) return 0;
if (int delta = details->index - other.details->index) return delta < 0;
return details->less(this, &other);
}
bool equal_to(const FancyFunction &other) const
{
static_assert(comparable_eq, "This function is disabled.");
if (bool(details) != bool(other.details)) return 0;
if (!details) return 1;
if (details->index != other.details->index) return 0;
return details->eq(this, &other);
}
std::size_t hash() const
{
static_assert(hashable, "This function is disabled.");
if (!details) return 0;
return details->hash(this);
}
friend bool operator<(const FancyFunction &a, const FancyFunction &b) {return a.less(b);}
friend bool operator>(const FancyFunction &a, const FancyFunction &b) {return b.less(a);}
friend bool operator<=(const FancyFunction &a, const FancyFunction &b) {return !b.less(a);}
friend bool operator>=(const FancyFunction &a, const FancyFunction &b) {return !a.less(b);}
friend bool operator==(const FancyFunction &a, const FancyFunction &b) {return a.equal_to(b);}
friend bool operator!=(const FancyFunction &a, const FancyFunction &b) {return !a.equal_to(b);}
};
namespace std
{
template <typename T, FunctionFlags Flags> struct hash<FancyFunction<T, Flags>>
{
using argument_type = FancyFunction<T, Flags>;
using result_type = std::size_t;
size_t operator()(const FancyFunction<T, Flags> &f) const
{
return f.hash();
}
};
}
Why can't I have a
std::set
orstd::unordered_set
ofstd::function
s?
std::set
relies on a comparator, which is used to determine if one element is less than the other.
It uses std::less
by default, and std::less
doesn't work with std::function
s.
(Because there is no way to properly compare std::function
s.)
Similarly, std::unordered_set
relies on std::hash
and std::equal_to
(or custom replacements for them), which also don't operate on std::function
s.
Is there any way to get it to work anyway?
You can write a wrapper around (or a replacement for) std::function
that works with std::less
, std::equal_to
and/or std::hash
.
Via power of type erasure, you can forward std::less
/std::equal_to
/std::hash
to objects stored in your wrapper.
Here's a proof-of-concept for such a wrapper.
Notes:
You can specify whether or not you want the
class FancyFunction
to work withstd::less
,std::equal_to
andstd::hash
separetely, by adjusting a template argument.
If some of those is enabled, you'll be able to apply them toFancyFunction
.
Naturally, you'll be able to construct
FancyFunction
from a type only if they can be applied to that type.
There is a static assertion that fires when a type fails to provide
std::hash
if it's needed.
It seems to be impossible to SFINAE on availability ofstd::less
andstd::equal_to
, so I couldn't make similar assertions for those.
In theory, you could support types that don't work with
std::less
,std::equal_to
and/orstd::hash
by always considering all instances of one type equivalent, and usingtypeid(T).hash_code()
as a hash.
I'm not sure if that behavior is desirable or not, implementing it is left as an exercise to the reader.
(Lack of SFINAE forstd::less
andstd::equal_to
will make it harder to implement properly.)
Specifying custom replacements for
std::less
,std::equal_to
andstd::hash
is not supported, implementing that is also left as an exercise to the reader.
(This means that this implementation can only be used to put lambdas into a regular
std::set
, notstd::unordered_set
.)
When applied to
FancyFunction
,std::less
andstd::equal_to
will first compare types of stored functors.
If types are identical, they'll resort to calling
std::less
/std::equal_to
on underlying instances.
(Thus, for two arbitrary different functor types,
std::less
will always consider instances of one of them less than instances of the other one. The order is not stable between program invocations.)
Example usage:
// With `std::set`:
#include <iostream>
#include <set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator<(AddN a, AddN b) {return a.n < b.n;}
};
int main()
{
using func_t = FancyFunction<int(int), FunctionFlags::comparable_less>;
// Note that `std::less` can operate on stateless lambdas by converting them to function pointers first. Otherwise this wouldn't work.
auto square = (int x){return x*x;};
auto cube = (int x){return x*x*x;};
std::set<func_t> set;
set.insert(square);
set.insert(square); // Dupe.
set.insert(cube);
set.insert(AddN{100});
set.insert(AddN{200});
set.insert(AddN{200}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`, note that it appears only once.
* 2 -> 8 // `cube`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`, also appears once.
*/
set.erase(set.find(cube));
set.erase(set.find(AddN{100}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 4 // `square`
* 2 -> 202 // `AddN{200}`
* `cube` and `AddN{100}` were removed.
*/
}
// With `std::unordered_set`:
#include <iostream>
#include <unordered_set>
struct AddN
{
int n;
int operator()(int x) const {return n + x;}
friend bool operator==(AddN a, AddN b) {return a.n == b.n;}
};
struct MulByN
{
int n;
int operator()(int x) const {return n * x;}
friend bool operator==(MulByN a, MulByN b) {return a.n == b.n;}
};
namespace std
{
template <> struct hash<AddN>
{
using argument_type = AddN;
using result_type = std::size_t;
size_t operator()(AddN f) const {return f.n;}
};
template <> struct hash<MulByN>
{
using argument_type = MulByN;
using result_type = std::size_t;
size_t operator()(MulByN f) const {return f.n;}
};
}
int main()
{
using hashable_func_t = FancyFunction<int(int), FunctionFlags::hashable | FunctionFlags::comparable_eq>;
std::unordered_set<hashable_func_t> set;
set.insert(AddN{100});
set.insert(AddN{100}); // Dupe.
set.insert(AddN{200});
set.insert(MulByN{10});
set.insert(MulByN{20});
set.insert(MulByN{20}); // Dupe.
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 40 // `MulByN{20}`
* 2 -> 20 // `MulByN{10}`
* 2 -> 102 // `AddN{100}`
* 2 -> 202 // `AddN{200}`
*/
set.erase(set.find(AddN{100}));
set.erase(set.find(MulByN{20}));
for (const auto &it : set)
std::cout << "2 -> " << it(2) << 'n';
std::cout << 'n';
/* Prints:
* 2 -> 20 // `MulByN{10}`
* 2 -> 202 // `AddN{200}`
* `MulByN{20}` and `AddN{100}` were removed.
*/
}
Implementation:
#include <cstddef>
#include <functional>
#include <experimental/type_traits>
#include <utility>
enum class FunctionFlags
{
none = 0,
comparable_less = 0b1,
comparable_eq = 0b10,
hashable = 0b100,
};
constexpr FunctionFlags operator|(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) | int(b));}
constexpr FunctionFlags operator&(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) & int(b));}
template <typename T> using detect_hashable = decltype(std::hash<T>{}(std::declval<const T &>()));
template <typename T, FunctionFlags Flags = FunctionFlags::none>
class FancyFunction;
template <typename ReturnType, typename ...ParamTypes, FunctionFlags Flags>
class FancyFunction<ReturnType(ParamTypes...), Flags>
{
struct TypeDetails
{
int index = 0;
bool (*less)(const void *, const void *) = 0;
bool (*eq)(const void *, const void *) = 0;
std::size_t (*hash)(const void *) = 0;
inline static int index_counter = 0;
};
template <typename T> const TypeDetails *GetDetails()
{
static TypeDetails ret = ()
{
using type = std::remove_cv_t<std::remove_reference_t<T>>;
TypeDetails d;
d.index = TypeDetails::index_counter++;
if constexpr (comparable_less)
{
// We can't SFINAE on `std::less`.
d.less = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::less<type>{}(a, b);
};
}
if constexpr (comparable_eq)
{
// We can't SFINAE on `std::equal_to`.
d.eq = (const void *a_ptr, const void *b_ptr) -> bool
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
return std::equal_to<type>{}(a, b);
};
}
if constexpr (hashable)
{
static_assert(std::experimental::is_detected_v<detect_hashable, type>, "This type is not hashable.");
d.hash = (const void *a_ptr) -> std::size_t
{
const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
return std::hash<type>(a);
};
}
return d;
}();
return &ret;
}
std::function<ReturnType(ParamTypes...)> func;
const TypeDetails *details = 0;
public:
inline static constexpr bool
comparable_less = bool(Flags & FunctionFlags::comparable_less),
comparable_eq = bool(Flags & FunctionFlags::comparable_eq),
hashable = bool(Flags & FunctionFlags::hashable);
FancyFunction(decltype(nullptr) = nullptr) {}
template <typename T>
FancyFunction(T &&obj)
{
func = std::forward<T>(obj);
details = GetDetails<T>();
}
explicit operator bool() const
{
return bool(func);
}
ReturnType operator()(ParamTypes ... params) const
{
return ReturnType(func(std::forward<ParamTypes>(params)...));
}
bool less(const FancyFunction &other) const
{
static_assert(comparable_less, "This function is disabled.");
if (int delta = bool(details) - bool(other.details)) return delta < 0;
if (!details) return 0;
if (int delta = details->index - other.details->index) return delta < 0;
return details->less(this, &other);
}
bool equal_to(const FancyFunction &other) const
{
static_assert(comparable_eq, "This function is disabled.");
if (bool(details) != bool(other.details)) return 0;
if (!details) return 1;
if (details->index != other.details->index) return 0;
return details->eq(this, &other);
}
std::size_t hash() const
{
static_assert(hashable, "This function is disabled.");
if (!details) return 0;
return details->hash(this);
}
friend bool operator<(const FancyFunction &a, const FancyFunction &b) {return a.less(b);}
friend bool operator>(const FancyFunction &a, const FancyFunction &b) {return b.less(a);}
friend bool operator<=(const FancyFunction &a, const FancyFunction &b) {return !b.less(a);}
friend bool operator>=(const FancyFunction &a, const FancyFunction &b) {return !a.less(b);}
friend bool operator==(const FancyFunction &a, const FancyFunction &b) {return a.equal_to(b);}
friend bool operator!=(const FancyFunction &a, const FancyFunction &b) {return !a.equal_to(b);}
};
namespace std
{
template <typename T, FunctionFlags Flags> struct hash<FancyFunction<T, Flags>>
{
using argument_type = FancyFunction<T, Flags>;
using result_type = std::size_t;
size_t operator()(const FancyFunction<T, Flags> &f) const
{
return f.hash();
}
};
}
edited Nov 25 at 14:26
answered Nov 24 at 20:27
HolyBlackCat
15.3k23362
15.3k23362
This is the most complete answer here. Thank you for taking the time! :)
– Qix
Nov 25 at 13:09
@HolyBlackCat That was really nice.
– JeJo
Nov 26 at 9:41
add a comment |
This is the most complete answer here. Thank you for taking the time! :)
– Qix
Nov 25 at 13:09
@HolyBlackCat That was really nice.
– JeJo
Nov 26 at 9:41
This is the most complete answer here. Thank you for taking the time! :)
– Qix
Nov 25 at 13:09
This is the most complete answer here. Thank you for taking the time! :)
– Qix
Nov 25 at 13:09
@HolyBlackCat That was really nice.
– JeJo
Nov 26 at 9:41
@HolyBlackCat That was really nice.
– JeJo
Nov 26 at 9:41
add a comment |
You can very well create an std::set
of functions. The problem is that sets require an absolute order to exist between the values of its elements. This order is defined by a comparator that is then used to sort the elements of a set, to check if an element already exists, and to find a specific element back.
Unfortunately, there doesn't exist an order between functions. Suppose, that you have two functions f1()
and f2()
, what would be the meaning of f1 < f2
?
Also equality is not really defined. For example, if you have
int fun1(int) { return 1; }
int fun2(int) { return 1; }
function<int(int)> f1=fun1, f2=fun2;
Should f1 and f2 be the same value if you'd insert them in a set (because it's always the same result), or is it something different (because it's different functions even though they have the same body) ?
Of course, you could trick the compiler in letting it believe that you have defined an order:
struct Comp {
using T = function<int(int)>;
bool operator()(const T &lhs, const T &rhs) const
{
return &lhs < &rhs;
}
};
set <function<int(int)>,Comp> s;
You could then insert functions in the set. But this will not work very well, because you take the address of the element, and if the same elements are swapped, the order is different.
I think that the best way to proceed, would be to use a wrapper with a member string that defines an id and use this id to sort the elements in the set (or to do the hashing in case of an unordered_set
)
add a comment |
You can very well create an std::set
of functions. The problem is that sets require an absolute order to exist between the values of its elements. This order is defined by a comparator that is then used to sort the elements of a set, to check if an element already exists, and to find a specific element back.
Unfortunately, there doesn't exist an order between functions. Suppose, that you have two functions f1()
and f2()
, what would be the meaning of f1 < f2
?
Also equality is not really defined. For example, if you have
int fun1(int) { return 1; }
int fun2(int) { return 1; }
function<int(int)> f1=fun1, f2=fun2;
Should f1 and f2 be the same value if you'd insert them in a set (because it's always the same result), or is it something different (because it's different functions even though they have the same body) ?
Of course, you could trick the compiler in letting it believe that you have defined an order:
struct Comp {
using T = function<int(int)>;
bool operator()(const T &lhs, const T &rhs) const
{
return &lhs < &rhs;
}
};
set <function<int(int)>,Comp> s;
You could then insert functions in the set. But this will not work very well, because you take the address of the element, and if the same elements are swapped, the order is different.
I think that the best way to proceed, would be to use a wrapper with a member string that defines an id and use this id to sort the elements in the set (or to do the hashing in case of an unordered_set
)
add a comment |
You can very well create an std::set
of functions. The problem is that sets require an absolute order to exist between the values of its elements. This order is defined by a comparator that is then used to sort the elements of a set, to check if an element already exists, and to find a specific element back.
Unfortunately, there doesn't exist an order between functions. Suppose, that you have two functions f1()
and f2()
, what would be the meaning of f1 < f2
?
Also equality is not really defined. For example, if you have
int fun1(int) { return 1; }
int fun2(int) { return 1; }
function<int(int)> f1=fun1, f2=fun2;
Should f1 and f2 be the same value if you'd insert them in a set (because it's always the same result), or is it something different (because it's different functions even though they have the same body) ?
Of course, you could trick the compiler in letting it believe that you have defined an order:
struct Comp {
using T = function<int(int)>;
bool operator()(const T &lhs, const T &rhs) const
{
return &lhs < &rhs;
}
};
set <function<int(int)>,Comp> s;
You could then insert functions in the set. But this will not work very well, because you take the address of the element, and if the same elements are swapped, the order is different.
I think that the best way to proceed, would be to use a wrapper with a member string that defines an id and use this id to sort the elements in the set (or to do the hashing in case of an unordered_set
)
You can very well create an std::set
of functions. The problem is that sets require an absolute order to exist between the values of its elements. This order is defined by a comparator that is then used to sort the elements of a set, to check if an element already exists, and to find a specific element back.
Unfortunately, there doesn't exist an order between functions. Suppose, that you have two functions f1()
and f2()
, what would be the meaning of f1 < f2
?
Also equality is not really defined. For example, if you have
int fun1(int) { return 1; }
int fun2(int) { return 1; }
function<int(int)> f1=fun1, f2=fun2;
Should f1 and f2 be the same value if you'd insert them in a set (because it's always the same result), or is it something different (because it's different functions even though they have the same body) ?
Of course, you could trick the compiler in letting it believe that you have defined an order:
struct Comp {
using T = function<int(int)>;
bool operator()(const T &lhs, const T &rhs) const
{
return &lhs < &rhs;
}
};
set <function<int(int)>,Comp> s;
You could then insert functions in the set. But this will not work very well, because you take the address of the element, and if the same elements are swapped, the order is different.
I think that the best way to proceed, would be to use a wrapper with a member string that defines an id and use this id to sort the elements in the set (or to do the hashing in case of an unordered_set
)
edited Nov 24 at 20:56
Rakete1111
34k980117
34k980117
answered Nov 24 at 17:08
Christophe
38.9k43474
38.9k43474
add a comment |
add a comment |
Well, you can only check function-pointers for (in-)equality, not order. And whether two functions with the same behavior must compare differently is not quite as cut-and-dry as you might perhaps hope for.
Next, you might not only store function-pointers, but also other callables. There is no guarantee any random user-defined class has a strict weak ordering. As an example, lambdas don't.
And finally, how would you order callables of different types?
You can make the same Argument for hashing (needed for unordered containers) as for ordering (needed for ordered containers). Even the equality-comparison needed for unordered containers might not exist.
add a comment |
Well, you can only check function-pointers for (in-)equality, not order. And whether two functions with the same behavior must compare differently is not quite as cut-and-dry as you might perhaps hope for.
Next, you might not only store function-pointers, but also other callables. There is no guarantee any random user-defined class has a strict weak ordering. As an example, lambdas don't.
And finally, how would you order callables of different types?
You can make the same Argument for hashing (needed for unordered containers) as for ordering (needed for ordered containers). Even the equality-comparison needed for unordered containers might not exist.
add a comment |
Well, you can only check function-pointers for (in-)equality, not order. And whether two functions with the same behavior must compare differently is not quite as cut-and-dry as you might perhaps hope for.
Next, you might not only store function-pointers, but also other callables. There is no guarantee any random user-defined class has a strict weak ordering. As an example, lambdas don't.
And finally, how would you order callables of different types?
You can make the same Argument for hashing (needed for unordered containers) as for ordering (needed for ordered containers). Even the equality-comparison needed for unordered containers might not exist.
Well, you can only check function-pointers for (in-)equality, not order. And whether two functions with the same behavior must compare differently is not quite as cut-and-dry as you might perhaps hope for.
Next, you might not only store function-pointers, but also other callables. There is no guarantee any random user-defined class has a strict weak ordering. As an example, lambdas don't.
And finally, how would you order callables of different types?
You can make the same Argument for hashing (needed for unordered containers) as for ordering (needed for ordered containers). Even the equality-comparison needed for unordered containers might not exist.
answered Nov 24 at 17:28
Deduplicator
34k64787
34k64787
add a comment |
add a comment |
There is no meaningful equality operation for the general function, held by a std::function
.
- C++ functions aren't mathematical functions. What if the "function" holds state? And that state is different for different instances?
- To your suggestion of using the "entry point address": Again, consider state. A
std::function
can hold a bind of some function/method to some parameters. What is the "entry point address" of that? Ans: Some function/method in the "bind" package. And does then that "entry point address" uniquely identify that function? Ans: No. - Suppose you have two different functions (by "entry point address") that in fact are identical in the sense that they produce the same result for every parameter? They may even be the same source code - or machine code. Are those functions equal, or not? (If not, why not, if they're behaviorally identical and can't be distinguished by any caller?)
Your particular use case (for sticking std::function
in a set) may not be impacted by the above issues. In that case simply wrap the std::function
instance in a small struct of your own (either via direct containment or via indirection) (forwarding calls to the contained function object) and put those things in your set.
add a comment |
There is no meaningful equality operation for the general function, held by a std::function
.
- C++ functions aren't mathematical functions. What if the "function" holds state? And that state is different for different instances?
- To your suggestion of using the "entry point address": Again, consider state. A
std::function
can hold a bind of some function/method to some parameters. What is the "entry point address" of that? Ans: Some function/method in the "bind" package. And does then that "entry point address" uniquely identify that function? Ans: No. - Suppose you have two different functions (by "entry point address") that in fact are identical in the sense that they produce the same result for every parameter? They may even be the same source code - or machine code. Are those functions equal, or not? (If not, why not, if they're behaviorally identical and can't be distinguished by any caller?)
Your particular use case (for sticking std::function
in a set) may not be impacted by the above issues. In that case simply wrap the std::function
instance in a small struct of your own (either via direct containment or via indirection) (forwarding calls to the contained function object) and put those things in your set.
add a comment |
There is no meaningful equality operation for the general function, held by a std::function
.
- C++ functions aren't mathematical functions. What if the "function" holds state? And that state is different for different instances?
- To your suggestion of using the "entry point address": Again, consider state. A
std::function
can hold a bind of some function/method to some parameters. What is the "entry point address" of that? Ans: Some function/method in the "bind" package. And does then that "entry point address" uniquely identify that function? Ans: No. - Suppose you have two different functions (by "entry point address") that in fact are identical in the sense that they produce the same result for every parameter? They may even be the same source code - or machine code. Are those functions equal, or not? (If not, why not, if they're behaviorally identical and can't be distinguished by any caller?)
Your particular use case (for sticking std::function
in a set) may not be impacted by the above issues. In that case simply wrap the std::function
instance in a small struct of your own (either via direct containment or via indirection) (forwarding calls to the contained function object) and put those things in your set.
There is no meaningful equality operation for the general function, held by a std::function
.
- C++ functions aren't mathematical functions. What if the "function" holds state? And that state is different for different instances?
- To your suggestion of using the "entry point address": Again, consider state. A
std::function
can hold a bind of some function/method to some parameters. What is the "entry point address" of that? Ans: Some function/method in the "bind" package. And does then that "entry point address" uniquely identify that function? Ans: No. - Suppose you have two different functions (by "entry point address") that in fact are identical in the sense that they produce the same result for every parameter? They may even be the same source code - or machine code. Are those functions equal, or not? (If not, why not, if they're behaviorally identical and can't be distinguished by any caller?)
Your particular use case (for sticking std::function
in a set) may not be impacted by the above issues. In that case simply wrap the std::function
instance in a small struct of your own (either via direct containment or via indirection) (forwarding calls to the contained function object) and put those things in your set.
edited Nov 24 at 17:09
answered Nov 24 at 17:02
davidbak
2,36221833
2,36221833
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53459693%2fwhy-cant-i-use-stdfunction-as-a-stdset-or-stdunordered-set-value-type%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
What do you mean with doesn't work?
– JVApen
Nov 24 at 15:35
6
Because you can't apply
std::less
(needed bystd::set
) norstd::hash
andstd::equal_to
(needed bystd::unordered_set
) to it.– HolyBlackCat
Nov 24 at 15:37
1
@Qix: compile errors would really be useful!
– JVApen
Nov 24 at 15:41
4
@Qix Take the case for
std::set
. What makes one function "less than" another? What would be the criteria?– PaulMcKenzie
Nov 24 at 15:42
3
What are you trying to achieve by using a set? If your
std::function
has state, then you might never get the same key/hash value thus making a set useless. Why not use a vector? If you want to identifying functions, then a map with incremental ID as the key might be more appropriate. You would keep the id as a reference to the actual function.– Phil1970
Nov 24 at 16:01