Is it possible to force STL set to reevaluate predicate?
Clash Royale CLAN TAG#URR8PPP
up vote
17
down vote
favorite
Consider the following data structures and code.
struct Sentence
std::string words;
int frequency;
Sentence(std::string words, int frequency) : words(words), frequency(frequency)
;
struct SentencePCompare
bool operator() (const Sentence* lhs, const Sentence* rhs) const
if (lhs->frequency != rhs->frequency)
return lhs->frequency > rhs->frequency;
return lhs->words.compare(rhs->words) < 0;
;
std::set<Sentence*, SentencePCompare> sentencesByFrequency;
int main()
Sentence* foo = new Sentence("foo", 1);
Sentence* bar = new Sentence("bar", 2);
sentencesByFrequency.insert(foo);
sentencesByFrequency.insert(bar);
for (Sentence* sp : sentencesByFrequency)
std::cout << sp->words << std::endl;
foo->frequency = 5;
for (Sentence* sp : sentencesByFrequency)
std::cout << sp->words << std::endl;
The output of the above code is the following.
bar
foo
bar
foo
As we might expect, when an object pointed to by the pointer in the set is updated, the set does not automatically re-evaluate the predicate, even though the predicate orders the pointers based on the objects they point at.
Is there a way to force the std::set to re-evaluate the predicates, so that the order is correct again?
c++ c++11 stdset
asked Nov 20 at 8:22
merlin2011
42.7k24115215
add a comment |
up vote
17
down vote
favorite
Consider the following data structures and code.
struct Sentence
std::string words;
int frequency;
Sentence(std::string words, int frequency) : words(words), frequency(frequency)
;
struct SentencePCompare
bool operator() (const Sentence* lhs, const Sentence* rhs) const
if (lhs->frequency != rhs->frequency)
return lhs->frequency > rhs->frequency;
return lhs->words.compare(rhs->words) < 0;
;
std::set<Sentence*, SentencePCompare> sentencesByFrequency;
int main()
Sentence* foo = new Sentence("foo", 1);
Sentence* bar = new Sentence("bar", 2);
sentencesByFrequency.insert(foo);
sentencesByFrequency.insert(bar);
for (Sentence* sp : sentencesByFrequency)
std::cout << sp->words << std::endl;
foo->frequency = 5;
for (Sentence* sp : sentencesByFrequency)
std::cout << sp->words << std::endl;
The output of the above code is the following.
bar
foo
bar
foo
As we might expect, when an object pointed to by the pointer in the set is updated, the set does not automatically re-evaluate the predicate, even though the predicate orders the pointers based on the objects they point at.
Is there a way to force the std::set to re-evaluate the predicates, so that the order is correct again?
c++ c++11 stdset
asked Nov 20 at 8:22
merlin2011
42.7k24115215
10
Perhapsstd::setisn't the right container type for your use-case? Since keys are supposed to be constant there's no need for any reordering.
– Some programmer dude
Nov 20 at 8:27
1
If the set isn't accessed very often, or if the modifications are reasonably well-separated from reads even though they can happen again later, it might make sense to leave it unordered and represented by e.g. avector, then sort it immediately before using it, each time you use it.
– Leushenko
Nov 20 at 9:57
@Someprogrammerdude, Do you have a recommendation for another data structure?
– merlin2011
Nov 20 at 18:37
Also,SentencePCompareisn't a proper order. Return type ofcomparecast toboolis code smell.
– Yakk - Adam Nevraumont
Nov 20 at 19:09
@Yakk-AdamNevraumont, That was actually a bug I just discovered lol. I have just fixed it in the code above.
– merlin2011
Nov 20 at 19:19
add a comment |
up vote
17
down vote
favorite
up vote
17
down vote
favorite
Consider the following data structures and code.
struct Sentence
std::string words;
int frequency;
Sentence(std::string words, int frequency) : words(words), frequency(frequency)
;
struct SentencePCompare
bool operator() (const Sentence* lhs, const Sentence* rhs) const
if (lhs->frequency != rhs->frequency)
return lhs->frequency > rhs->frequency;
return lhs->words.compare(rhs->words) < 0;
;
std::set<Sentence*, SentencePCompare> sentencesByFrequency;
int main()
Sentence* foo = new Sentence("foo", 1);
Sentence* bar = new Sentence("bar", 2);
sentencesByFrequency.insert(foo);
sentencesByFrequency.insert(bar);
for (Sentence* sp : sentencesByFrequency)
std::cout << sp->words << std::endl;
foo->frequency = 5;
for (Sentence* sp : sentencesByFrequency)
std::cout << sp->words << std::endl;
The output of the above code is the following.
bar
foo
bar
foo
As we might expect, when an object pointed to by the pointer in the set is updated, the set does not automatically re-evaluate the predicate, even though the predicate orders the pointers based on the objects they point at.
Is there a way to force the std::set to re-evaluate the predicates, so that the order is correct again?
c++ c++11 stdset
asked Nov 20 at 8:22
merlin2011
42.7k24115215
Consider the following data structures and code.
struct Sentence
std::string words;
int frequency;
Sentence(std::string words, int frequency) : words(words), frequency(frequency)
;
struct SentencePCompare
bool operator() (const Sentence* lhs, const Sentence* rhs) const
if (lhs->frequency != rhs->frequency)
return lhs->frequency > rhs->frequency;
return lhs->words.compare(rhs->words) < 0;
;
std::set<Sentence*, SentencePCompare> sentencesByFrequency;
int main()
Sentence* foo = new Sentence("foo", 1);
Sentence* bar = new Sentence("bar", 2);
sentencesByFrequency.insert(foo);
sentencesByFrequency.insert(bar);
for (Sentence* sp : sentencesByFrequency)
std::cout << sp->words << std::endl;
foo->frequency = 5;
for (Sentence* sp : sentencesByFrequency)
std::cout << sp->words << std::endl;
The output of the above code is the following.
bar
foo
bar
foo
As we might expect, when an object pointed to by the pointer in the set is updated, the set does not automatically re-evaluate the predicate, even though the predicate orders the pointers based on the objects they point at.
Is there a way to force the std::set to re-evaluate the predicates, so that the order is correct again?
c++ c++11 stdset
c++ c++11 stdset
asked Nov 20 at 8:22
merlin2011
42.7k24115215
asked Nov 20 at 8:22
merlin2011
42.7k24115215
edited Nov 20 at 19:19
asked Nov 20 at 8:22
merlin2011
42.7k24115215
asked Nov 20 at 8:22
merlin2011
42.7k24115215
asked Nov 20 at 8:22
merlin2011
42.7k24115215
42.7k24115215
10
Perhapsstd::setisn't the right container type for your use-case? Since keys are supposed to be constant there's no need for any reordering.
– Some programmer dude
Nov 20 at 8:27
1
If the set isn't accessed very often, or if the modifications are reasonably well-separated from reads even though they can happen again later, it might make sense to leave it unordered and represented by e.g. avector, then sort it immediately before using it, each time you use it.
– Leushenko
Nov 20 at 9:57
@Someprogrammerdude, Do you have a recommendation for another data structure?
– merlin2011
Nov 20 at 18:37
Also,SentencePCompareisn't a proper order. Return type ofcomparecast toboolis code smell.
– Yakk - Adam Nevraumont
Nov 20 at 19:09
@Yakk-AdamNevraumont, That was actually a bug I just discovered lol. I have just fixed it in the code above.
– merlin2011
Nov 20 at 19:19
add a comment |
10
Perhapsstd::setisn't the right container type for your use-case? Since keys are supposed to be constant there's no need for any reordering.
– Some programmer dude
Nov 20 at 8:27
1
If the set isn't accessed very often, or if the modifications are reasonably well-separated from reads even though they can happen again later, it might make sense to leave it unordered and represented by e.g. avector, then sort it immediately before using it, each time you use it.
– Leushenko
Nov 20 at 9:57
@Someprogrammerdude, Do you have a recommendation for another data structure?
– merlin2011
Nov 20 at 18:37
Also,SentencePCompareisn't a proper order. Return type ofcomparecast toboolis code smell.
– Yakk - Adam Nevraumont
Nov 20 at 19:09
@Yakk-AdamNevraumont, That was actually a bug I just discovered lol. I have just fixed it in the code above.
– merlin2011
Nov 20 at 19:19
10
10
Perhaps
std::set isn't the right container type for your use-case? Since keys are supposed to be constant there's no need for any reordering.– Some programmer dude
Nov 20 at 8:27
Perhaps
std::set isn't the right container type for your use-case? Since keys are supposed to be constant there's no need for any reordering.– Some programmer dude
Nov 20 at 8:27
1
1
If the set isn't accessed very often, or if the modifications are reasonably well-separated from reads even though they can happen again later, it might make sense to leave it unordered and represented by e.g. a
vector, then sort it immediately before using it, each time you use it.– Leushenko
Nov 20 at 9:57
If the set isn't accessed very often, or if the modifications are reasonably well-separated from reads even though they can happen again later, it might make sense to leave it unordered and represented by e.g. a
vector, then sort it immediately before using it, each time you use it.– Leushenko
Nov 20 at 9:57
@Someprogrammerdude, Do you have a recommendation for another data structure?
– merlin2011
Nov 20 at 18:37
@Someprogrammerdude, Do you have a recommendation for another data structure?
– merlin2011
Nov 20 at 18:37
Also,
SentencePCompare isn't a proper order. Return type of compare cast to bool is code smell.– Yakk - Adam Nevraumont
Nov 20 at 19:09
Also,
SentencePCompare isn't a proper order. Return type of compare cast to bool is code smell.– Yakk - Adam Nevraumont
Nov 20 at 19:09
@Yakk-AdamNevraumont, That was actually a bug I just discovered lol. I have just fixed it in the code above.
– merlin2011
Nov 20 at 19:19
@Yakk-AdamNevraumont, That was actually a bug I just discovered lol. I have just fixed it in the code above.
– merlin2011
Nov 20 at 19:19
add a comment |
1 Answer
1
active
oldest
votes
up vote
34
down vote
accepted
No.
There's a reason why set only allows const access to its elements. If you sneak past that by using shallow-const pointers and custom predicates and then destroy the invariant by modifying the pointee in a way that affects ordering, you'll pay the price in the form of nasal demons.
Before C++17, you need to erase and insert again, which incurs a key copy plus node deallocation and allocation. After, you can extract the node, modify it, and reinsert it, which is free.
edited Nov 20 at 10:30
anatolyg
16.8k44589
answered Nov 20 at 8:28
T.C.
104k13212317
Maybe show how to "extract" the node without erasing it? I think it's on topic here (if not, I'll post it as a separate question).
– anatolyg
Nov 20 at 10:26
4
@anatolyg You literallyextractit.
– T.C.
Nov 20 at 10:26
4
Not really free, it avoids the cost of reallocating the node, but it's still necessary to recompute where the new node should be at, which takes about logarithmic time.
– user202729
Nov 20 at 15:01
1
Well yes, that's the baseline cost of maintaining the invariant that you need to pay whatever you do if you want a coherent data structure.
– T.C.
Nov 20 at 20:16
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
34
down vote
accepted
No.
There's a reason why set only allows const access to its elements. If you sneak past that by using shallow-const pointers and custom predicates and then destroy the invariant by modifying the pointee in a way that affects ordering, you'll pay the price in the form of nasal demons.
Before C++17, you need to erase and insert again, which incurs a key copy plus node deallocation and allocation. After, you can extract the node, modify it, and reinsert it, which is free.
edited Nov 20 at 10:30
anatolyg
16.8k44589
answered Nov 20 at 8:28
T.C.
104k13212317
Maybe show how to "extract" the node without erasing it? I think it's on topic here (if not, I'll post it as a separate question).
– anatolyg
Nov 20 at 10:26
4
@anatolyg You literallyextractit.
– T.C.
Nov 20 at 10:26
4
Not really free, it avoids the cost of reallocating the node, but it's still necessary to recompute where the new node should be at, which takes about logarithmic time.
– user202729
Nov 20 at 15:01
1
Well yes, that's the baseline cost of maintaining the invariant that you need to pay whatever you do if you want a coherent data structure.
– T.C.
Nov 20 at 20:16
add a comment |
up vote
34
down vote
accepted
No.
There's a reason why set only allows const access to its elements. If you sneak past that by using shallow-const pointers and custom predicates and then destroy the invariant by modifying the pointee in a way that affects ordering, you'll pay the price in the form of nasal demons.
Before C++17, you need to erase and insert again, which incurs a key copy plus node deallocation and allocation. After, you can extract the node, modify it, and reinsert it, which is free.
edited Nov 20 at 10:30
anatolyg
16.8k44589
answered Nov 20 at 8:28
T.C.
104k13212317
Maybe show how to "extract" the node without erasing it? I think it's on topic here (if not, I'll post it as a separate question).
– anatolyg
Nov 20 at 10:26
4
@anatolyg You literallyextractit.
– T.C.
Nov 20 at 10:26
4
Not really free, it avoids the cost of reallocating the node, but it's still necessary to recompute where the new node should be at, which takes about logarithmic time.
– user202729
Nov 20 at 15:01
1
Well yes, that's the baseline cost of maintaining the invariant that you need to pay whatever you do if you want a coherent data structure.
– T.C.
Nov 20 at 20:16
add a comment |
up vote
34
down vote
accepted
up vote
34
down vote
accepted
No.
There's a reason why set only allows const access to its elements. If you sneak past that by using shallow-const pointers and custom predicates and then destroy the invariant by modifying the pointee in a way that affects ordering, you'll pay the price in the form of nasal demons.
Before C++17, you need to erase and insert again, which incurs a key copy plus node deallocation and allocation. After, you can extract the node, modify it, and reinsert it, which is free.
edited Nov 20 at 10:30
anatolyg
16.8k44589
answered Nov 20 at 8:28
T.C.
104k13212317
No.
There's a reason why set only allows const access to its elements. If you sneak past that by using shallow-const pointers and custom predicates and then destroy the invariant by modifying the pointee in a way that affects ordering, you'll pay the price in the form of nasal demons.
Before C++17, you need to erase and insert again, which incurs a key copy plus node deallocation and allocation. After, you can extract the node, modify it, and reinsert it, which is free.
edited Nov 20 at 10:30
anatolyg
16.8k44589
answered Nov 20 at 8:28
T.C.
104k13212317
edited Nov 20 at 10:30
anatolyg
16.8k44589
edited Nov 20 at 10:30
anatolyg
16.8k44589
edited Nov 20 at 10:30
anatolyg
16.8k44589
16.8k44589
answered Nov 20 at 8:28
T.C.
104k13212317
answered Nov 20 at 8:28
T.C.
104k13212317
answered Nov 20 at 8:28
T.C.
104k13212317
104k13212317
Maybe show how to "extract" the node without erasing it? I think it's on topic here (if not, I'll post it as a separate question).
– anatolyg
Nov 20 at 10:26
4
@anatolyg You literallyextractit.
– T.C.
Nov 20 at 10:26
4
Not really free, it avoids the cost of reallocating the node, but it's still necessary to recompute where the new node should be at, which takes about logarithmic time.
– user202729
Nov 20 at 15:01
1
Well yes, that's the baseline cost of maintaining the invariant that you need to pay whatever you do if you want a coherent data structure.
– T.C.
Nov 20 at 20:16
add a comment |
Maybe show how to "extract" the node without erasing it? I think it's on topic here (if not, I'll post it as a separate question).
– anatolyg
Nov 20 at 10:26
4
@anatolyg You literallyextractit.
– T.C.
Nov 20 at 10:26
4
Not really free, it avoids the cost of reallocating the node, but it's still necessary to recompute where the new node should be at, which takes about logarithmic time.
– user202729
Nov 20 at 15:01
1
Well yes, that's the baseline cost of maintaining the invariant that you need to pay whatever you do if you want a coherent data structure.
– T.C.
Nov 20 at 20:16
Maybe show how to "extract" the node without erasing it? I think it's on topic here (if not, I'll post it as a separate question).
– anatolyg
Nov 20 at 10:26
Maybe show how to "extract" the node without erasing it? I think it's on topic here (if not, I'll post it as a separate question).
– anatolyg
Nov 20 at 10:26
4
4
@anatolyg You literally
extract it.– T.C.
Nov 20 at 10:26
@anatolyg You literally
extract it.– T.C.
Nov 20 at 10:26
4
4
Not really free, it avoids the cost of reallocating the node, but it's still necessary to recompute where the new node should be at, which takes about logarithmic time.
– user202729
Nov 20 at 15:01
Not really free, it avoids the cost of reallocating the node, but it's still necessary to recompute where the new node should be at, which takes about logarithmic time.
– user202729
Nov 20 at 15:01
1
1
Well yes, that's the baseline cost of maintaining the invariant that you need to pay whatever you do if you want a coherent data structure.
– T.C.
Nov 20 at 20:16
Well yes, that's the baseline cost of maintaining the invariant that you need to pay whatever you do if you want a coherent data structure.
– T.C.
Nov 20 at 20:16
add a comment |
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%2f53388846%2fis-it-possible-to-force-stl-set-to-reevaluate-predicate%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
10
Perhaps
std::setisn't the right container type for your use-case? Since keys are supposed to be constant there's no need for any reordering.– Some programmer dude
Nov 20 at 8:27
1
If the set isn't accessed very often, or if the modifications are reasonably well-separated from reads even though they can happen again later, it might make sense to leave it unordered and represented by e.g. a
vector, then sort it immediately before using it, each time you use it.– Leushenko
Nov 20 at 9:57
@Someprogrammerdude, Do you have a recommendation for another data structure?
– merlin2011
Nov 20 at 18:37
Also,
SentencePCompareisn't a proper order. Return type ofcomparecast toboolis code smell.– Yakk - Adam Nevraumont
Nov 20 at 19:09
@Yakk-AdamNevraumont, That was actually a bug I just discovered lol. I have just fixed it in the code above.
– merlin2011
Nov 20 at 19:19