Is it possible to force STL set to reevaluate predicate?












21














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







share|improve this question




















  • 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






  • 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, 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


















21














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







share|improve this question




















  • 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






  • 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, 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
















21












21








21


3





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







share|improve this question















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 20 at 19:19

























asked Nov 20 at 8:22









merlin2011

43.1k25117216




43.1k25117216








  • 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






  • 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, 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
















  • 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






  • 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, 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










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














1 Answer
1






active

oldest

votes


















34














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.






share|improve this answer



















  • 4




    @anatolyg You literally extract it.
    – 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











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
});


}
});














draft saved

draft discarded


















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

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









34














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.






share|improve this answer



















  • 4




    @anatolyg You literally extract it.
    – 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
















34














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.






share|improve this answer



















  • 4




    @anatolyg You literally extract it.
    – 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














34












34








34






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.






share|improve this answer














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.







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 20 at 10:30









anatolyg

16.9k44590




16.9k44590










answered Nov 20 at 8:28









T.C.

106k13216321




106k13216321








  • 4




    @anatolyg You literally extract it.
    – 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














  • 4




    @anatolyg You literally extract it.
    – 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








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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

How to change which sound is reproduced for terminal bell?

Image
3 Recently upgrade to 18.10 from 18.04, and using the terminal is becoming annoying: the new alert sound is a drip ( /usr/share/sounds/gnome/default/alerts/drip.ogg ), and the previous one is still located at ( /usr/share/sounds/ubuntu/stereo/bell.ogg ). My issue is that at the gnome-terminal, when autocompleting or pressing left BOTH sounds are reproduced, at the same time. I want to just have ubuntu/stereo/bell.ogg active, not both . At the moment I have been only able to reduce the volume of the alerts (but still both are played), or turn the alerts down (but I dislike both "solutions"). gnome-terminal 18.10 teminal-bell share | improve this question ...
Read more

Can I use Tabulator js library in my java Spring + Thymeleaf project?

Image
0 I want to add Tabulator js to my java project. I added tabulator.min.js, tabulator.min.css to resources folder. After that added to my html page these dependencies as recommending in readme.md. <link rel="stylesheet" th:href="@{/css/tabulator.min.css}"> <script type="text/javascript" th:src="@{/js/tabulator.min.js}"></script> Now my tables view all elements, that I have in the html page, but not correct. In the documentation of Tabulator is example how to create header and table, var table = new Tabulator("#example-table", { columns:[ {title:"Name", field:"name", sorter:"string", width:200, editor:true}, {title:"Age", field:"age", sorter:"...
Read more

Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

Image
up vote 5 down vote favorite 2 I would like to make it so that the vertical space below the title of each chapter is the same when using the Bjornstrup package (i.e. so that the descenders do not affect the spacing - as shown by the red arrow in the picture below). I think I'm fairly happy with the spacing around "A chapter", so I'd really like titles without descenders (e.g. "Contents") to have the same vertical spacing as "A chapter" below the title. I would also like to remove the large "0" in the contents title. Any help appreciated, as always. documentclass[11pt,a4paper]{book} % Packages[![enter image description here][1]][1] usepackage[left=3.5cm, right=3.5cm, top=4.3cm, bottom=4.25cm]{geometry} usepackage[utf8]{inputenc} usepackage{libertine} usepackage[libertine]{newtx...
Read more