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

Biblatex bibliography style without URLs when DOI exists (in Overleaf with Zotero bibliography)

Image
2 2 I have a Zotero bibliography in Overleaf. I use biblatex . usepackage[backend=biber,citestyle=authoryear]{biblatex} addbibresource{zoteroALH.bib} Bibliography entries look like: @book{de_saint-gervais_uniformization_2016, title = {Uniformization of {Riemann} {Surfaces}}, isbn = {978-3-03719-145-3}, url = {https://www.ems-ph.org/books/book.php?proj_nr=198&srch=series%7Chem}, urldate = {2019-02-03}, author = {de Saint-Gervais, Paul Henri}, year = {2016}, doi = {10.4171/145} } In the bibliography down the paper the reference shows like this: There is the DOI, great, but also the URL which is unnecessary when the DOI is there. How can I remove the URL when the DOI is present? biblatex bibliographies overleaf zote
Read more

ComboBox Display Member on multiple fields

Image
2 I'm trying to set the .DisplayMember property of a ComboBox in C#, but I want to bind it to multiple columns in the .DataSouce . My SQL looks like this: SELECT PersNbr, PersFirstName, PersMiddleName, PersLastName FROM Pers WHERE PersNbr = :persNbr; I'm saving this query in a DataTable so each column selected has it's own column in the Datatable . I want to make the .DisplayMember a combination of PersFirstName + PersMiddleName + PersLastName so their full name appears like this: comboBox.DisplayMemeber = "PersFirstName" + "PersMiddleName" + "PersLastName" I know I can just to this on the query: SELECT PersNbr, (PersFirstName || PersMiddleName || PersLastName) PersName and then just do this: comboBox.DisplayMember = "PersName"; but I
Read more

Is it possible to collect Nectar points via Trainline?

Image
2 Since I am not eligible for any Railcard, the only available discount/bonus scheme is Nectar Card for me. GWR, SWR, LNER and Virgin Trains allow to collect Nectar points and I have already linked a card to my GWR account. A friend suggested me to use Trainline App, because it can search for bus tickets either. I had a look at the application, but could not see any option for Nectar. Is there a way to collect Nectar points when I buy tickets via Trainline? uk trains loyalty-programs trainline share | improve this question asked Dec 2 '18 at 15:50 ahmedus 3,224 5 19 49
Read more