Order of objects are changed for different runs of program?

Question

1.80/5 (2 votes)

See more:

Iam using stl set container class for storing pointers to objects. While reading from the stl sets, for different runs of the program, the order of objects are getting changed because of dynamic allocation of memory (address) to object.

Lets say objects are A,B,C and their addresses in first run are 10,16,12. So when I insert these objects into set and retrieve them, I will get output as A C B (b'caz 10<12<16). Now if in the next run the addresses alloted are 14, 10, 8, I would get the output as C B A (8<10<14).

Is there any way that I can get output in perticular order?

Overloading comparator (custom comparator) can solve the problem, but in that case I have to pass it as a template parameter, which leads to modifying code at many places. Is there any way of avoiding modifying my code, still able to write custome comparator?

Posted 26-May-14 19:14pm

Vinay Ch

Add a Solution

Comments

Sergey Alexandrovich Kryukov 27-May-14 1:34am

What exactly container do you use? Do you use threads? TPL? How do you know that it is because of sorting by address?
—SA

Vinay Ch 27-May-14 4:16am

What is TPL?
I have not used threads. I know that and I made sure that it is because of storing addresses. My container is set<node *=""> where Node is a struct having some memebers..

Sergey Alexandrovich Kryukov 27-May-14 11:10am

Parallel Task Library. What is the container, exactly. Even if the problem is as you described it, the solution is way to easy: use some unsorted container, then the order will be by order of operations. Or just don't sort if you do. Or define your own comparison.
—SA

3 solutions

Solution 3

In addition to Solution 1: please read this detailed and useful article:
Matt Austern, Why you shouldn't use set (and what you should use instead).

No, you should, but in more rarer cases…

—SA

Posted 27-May-14 5:22am

Sergey Alexandrovich Kryukov

Comments

[no name] 27-May-14 12:24pm

I need to read it first before voting. At the Moment I'm very disappointed not to use set in future, because I'm a fan of set Theorie ;)

After reading:
Ok I've only flown over the article. And there are most probably good arguments not to use set...I never used it e.g. in performance critical situations(I used it only for convinience, because I'm Little bit lazy)...and that is maybe an argument.

Where I'm completely do not agree in the article is to mention "set" and more or less in the same time "sort". "set" and "sort" for me are "not compatible". Only a noob's meening. I stay neutral this time and don't vote.

Stefan_Lang 28-May-14 2:46am

std::set is not quite the same *internally* as the mathematical concept of set:. Mathematically, sets really only provide very few functions: insert, remove, or check containedness of an element, and a few binary operations between sets. For the implementation that means that the internal data structure must be built in such a way, that insertion and finding elements are fast. To be faster than O(N), the internal data structure must be ordered in some way. And that's where the sorting comes in: You can't implement a set in an efficient way without also sorting the elements! It's true that the mathematical definition of a set does not imply any kind of order, but for the implementatiion of a set to make sense it must be ordered!

Sergey Alexandrovich Kryukov 28-May-14 3:05am

I know it's not the same. However, conceptually, it is rather intended to model the functionality of the set. (It's not "containedness", it's the relationship "being an element of", which is fundamentally different :-)
Again, "for implementation" part is mostly the performance. Unfortunately, there is unavoidable order of traversing of all elements, which is not so usual set operation. Conceptually, it is assumed that the order should be ignored as nothing really guarantees it.
—SA

Stefan_Lang 28-May-14 3:16am

"(It's not "containedness", it's the relationship "being an element of","

Actually, according to the dictionary I consulted, containedness(math) is the mathematical term describing the property of being element of - so we're talking of the same thing here. ;-)

Stefan_Lang 28-May-14 2:33am

Great article! If that doesn't answer the question, I don't know what will.
5ed

Sergey Alexandrovich Kryukov 28-May-14 3:06am

Thank you, Stefan. I'm glad I found this article...
—SA

Solution 1

Why do you use a set at all? What do you expect the container to behave?

Sets are ordered containers, so of course if your entry to the set changes (like memory adresses in different runs) the order of the single entries changes as well.

If you dont want an ordered container use for example a vector[^] or an unordered_set[^] or somehing else.

Posted 26-May-14 20:49pm

Legor

Comments

Stefan_Lang 27-May-14 5:12am

These suggestions defeat the purpose of not having to fix existing uses of the type - if that were an option, the OP already knows that he could just pass a custom comparator to fix the behaviour.

Fixing the ordering is possible without changing the type definition - see my solution.

Sergey Alexandrovich Kryukov 27-May-14 11:24am

No, this is a good suggestion. What do you thing they defeat, exactly? I don't see that OP consciously chosen the set...
Also, please see my Solution 3, with the link on the topic.
I voted 5 for the answer.
—SA

Stefan_Lang 28-May-14 2:03am

Yes it is a good suggestion, but the OP clearly indicated that he didn't want to change the type.

After all that's been written in the meantime however, I agree that the chosen type is definitely inappropriate, and I even reponded as much to the related question he posted.

Sergey Alexandrovich Kryukov 28-May-14 2:19am

I'm not sure this is a mature decision to be taken into account. It's better to assume that if someone has a problem, the use of certain facility is undecided. Did you see the article I referenced in my answer? Pretty reasonable explanation.

Now, from my point of view, there is another reason not to use set. It is a collection really representing mathematical set. If one uses set, the order of elements should be irrelevant. The set is ordered only for the performance reason. Many also criticize this implementation and suggest to use alternative hash-based solution (with buckets...). Anyway, as soon as someone starts to concern about order of elements is set, this is a clear indication that the container should not be set. Isn't it logical?

More general, help can only be effective if you are not taking "I want" or "this is a requirement" for granted. Those "requirements" are exactly the same potential source of the problem as any other mistakes which led to asking for an advice.

—SA

Stefan_Lang 28-May-14 2:32am

I do agree, but sometimes I prefer sticking to the exact wording of a question in order to provoke a clarification. I've found that inquiries for more specific information often get ignored, and suggestions that ignore the original requirements too!

If the question implies facts that hint at better solutions, I'll go along with those, but in this case there was no implication (at first) that there was no good reason to use set. Also, the author put up a closely related question (that now seems to be gone, probably because it was considered a duplicate), where he specifically stated that sticking to the given type was imperative!

Ironically, CPallini and I both strongly suggested to drop that requirement and go with vector instead. Now that you even posted a well researched article suggesting the same, I hope that closes the matter!

Stefan_Lang 28-May-14 3:22am

P.S.: I've found the related question that I was refering to - it wasn't removed after all, I just was still too much asleep to spot it ;-)

http://www.codeproject.com/Questions/778525/Reading-elements-from-STL-SET-on-the-basis-of-orde?arn=6

Vinay Ch 27-May-14 5:13am

@Legor: I have used set because of its advantages in performing insertion and searching. I want to have O(log(n)) insertion and searching capability and be able to read elements in the order we inserted into it..

Stefan_Lang 27-May-14 6:49am

std::vector also has O(log(n)) insertion, and if you have an idea about how many elements you are going to insert beforehand, you can even make it O(1)! std::list has O(1) insertion out of the box. As has been pointed out, order of insertion is not preserved in std::set, but it is in both std::vector and std::list. As for searching, I don't see why std::set should be any faster than other container types, and std::hash_set would almost certainly be faster.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Stefan_Lang · Accepted Answer · 2014-05-26T23:08:00

Solution 2

You can override the default comparator by specializing std::less like this:

C++

struct mytype {
   int x;
};
template <>
struct std::less<mytype*>
   : public binary_function<mytype*, mytype*, bool>
{   // functor for operator<
   bool operator()(const mytype* _Left, const mytype* _Right) const
   {    // apply operator< to operands
      return (_Left->x < _Right->x);
   }
};

I've tested this successfully using this code:

C++

void foo() {
   std::set<mytype*> s;
   mytype arr[3];
   arr[0].x = 3;
   arr[1].x = 1;
   arr[2].x = 2;
   s.insert(&arr[2]); // 2
   s.insert(&arr[0]); // 3
   s.insert(&arr[1]); // 1
   std::for_each(s.begin(), s.end(), [](const mytype* p) {
      std::cout << p->x << std::endl;
   });
}

The output is "1,2,3." As you can see, neither the order of elements by address, nor the order of input corresponds to that output, instead it's the less override.

Posted 26-May-14 23:08pm

Stefan_Lang

Comments

Vinay Ch 27-May-14 5:34am

Thank you very much @Stefan_Lang. Here in your mytype structure, only one integer element is there so the specialised std::less<mytype*> will exaclty behave as std::less (i,e only 1 comparision is required). In my case, I have several elements and inorder to resolve ambiguity(if any in case of two mytype* have same x value), I may need to do many comparisions. This will happen each time I insert some element. In my case I am inserting huge no. of elements, which will lead to a very long run time. So is there any way of iterating through SET on the basis of order of insertion into set?, in this case we need not to specialize comparator, so run time will not increase.

Stefan_Lang 27-May-14 6:07am

No, the standard implementation of std::less would just compare pointer addresses rather than the stored member variable x! Without the specialization, the output would be "3,1,2"! Check it out: use the code with the specialization, then remove the specialization and run it again.

In the definition of std::less<mytype*>::operator()(const mytype*,const mytype*) you can d a lot more than just compare one member variable, if you like. For instance if you have entries for day, month and year, you could compare all three and order the output by date!

As for order of insertion - no, there are plenty of other types that preserve order of insertion. set is not one of them. If that is so important to you, why did you choose set in the first place? It is an unusal (and inefficient) container to use!

Sergey Alexandrovich Kryukov 27-May-14 11:12am

Why using set in this case?! Just to give it some unpredictable sorting? Why using anything sorted at all and then having problem with unpredictable order? It's first of all the matter or using suitable container class, and only then the comparison...
Actually, this is already explained in Solution 1.
—SA

Stefan_Lang 28-May-14 3:04am

To quote the OP:
"Overloading comparator (custom comparator) can solve the problem, but in that case I have to pass it as a template parameter, which leads to modifying code at many places. Is there any way of avoiding modifying my code, still able to write custome comparator? "

I've answered to that request, because it is a legitimate question, and others looking for an answer to a similar problem might want to learn whether and how this is possible.

As pointed out elsewhere, I do realize that the assertion that the type may not be changed might have been inappropriate, and that choosing a different type may approach this particular problem better. but I could only be sure of that after the OP responded to this suggestion in the negative. After his response of course, it was obvious that he shouldn't use set at all.

Sergey Alexandrovich Kryukov 28-May-14 3:08am

...and that is a good reason for me to up-vote your answer with 5. :-)
—SA

Stefan_Lang 28-May-14 3:22am

Thank you Sergey - always nice discussing with you :-)

Sergey Alexandrovich Kryukov 28-May-14 11:21am

And thank you for this discussion.
—SA