Reproducing random std::set order

Question

I have a test randomly failing, I suspect due to order of objects in a std::set ordered on pointers values. However, on my current exe, the test always passes. Is there a way I can "mix" the pointers creations so the order of object in my set is different between two runs ?

In other words, is the "sorted order" (p1 < p2) of pointers deterministic for a given C++ code, or does different compilations or different runs can have different sorted orders ?

For example in this code, adding "p1b.reset(nullptr)" between p1 and p2 creation will invert p1 / p2 "sorted order" . Is there any other way to influence this order, without changing the source code ?

int main(void)
{
    std::unique_ptr< MyClass > p1b(new MyClass());

    //Lot of code, with memory allocated/deallocated

    std::unique_ptr< MyClass > p1(new MyClass());

    //p1b.reset(nullptr);

    //Lot of code, with memory allocated/deallocated

    std::unique_ptr< MyClass > p2(new MyClass());

    std::cout << "p1: " << p1.get() << std::endl;
    std::cout << "p2: " << p2.get() << std::endl;
}

Gives:

p1: 0x171c030
p2: 0x171c050

With "p1b.reset(nullptr)" commented out:

p1: 0x21f9030
p2: 0x21f9010

Can you elaborate further? Provide a working code snippet perhaps? — WhiZTiM, May 04 '16 at 12:31

score 2 · Answer 1 · edited May 23 '17 at 11:59

EDIT 2: based on your edit: https://stackoverflow.com/revisions/37027675/3

In other words, is the "sorted order" (p1 < p2) of pointers deterministic for a given C++ code, or does different compilations or different runs can have different sorted orders ?

Yes, they can have different orders because - when you are allocating on heap, the "order of succession" of pointer addresses returned by the memory allocator is NOT guaranteed, so, yes, that can change anytime. Read the remaining part of the answer.

EDIT 1: based on your edit: https://stackoverflow.com/revisions/37027675/2

For example in this code, adding p1b.reset(nullptr) between p1 and p2 creation will invert p1 / p2 order. Is there any other way to influence this order ?

No, it doesn't "invert" the creation order, you destroyed p1 and created another object(perhaps equal) and had it take the place of p1. Read the initial answer..

Initial Answer

Is there a way I can "mix" the pointers creations so the order of object in my set is different between two runs ?

Chances are that, your memory allocator allocates memory in a successive fashion, so if you allocate elements successively in a single threaded program, they will likely be in a succession of memory addresses. But if it is with regards to absolute pointer addresses, they will likely be at "different" absolute offsets on each run of your program due to Address space layout randomization

If you want the memory addresses of successive elements to be random, or in a specific order, you will have to create it in that random fashion or simply in the order you want it created...

For a random fashion... ...Off the top of my head: Perhaps, generate a std::vector of indices to the objects you want to create; randomize (or shuffle) the vector then run through the elements of the vector creating your objects.

My answer above is based on your stated suspicion. But again, I am uncomfortable with this:

I have a test randomly failing, I suspect due to order of objects in a std::set ordered on pointers values. However, on my current exe, the test always passes.

Check for Undefined Behaviors and also run memory tools and static analyzers through your code.

This is what I observe on a simple program. However, in my real life example I have different results for different compilations. I was wondering if I can dynamically influence this order to try to reproduce the different behaviors. — MickaëlG, May 04 '16 at 12:44
@MickaëlG, Ok... but can you post a minimal code snippet that explains what exactly you did, what are your results and what you are trying to achieve? — WhiZTiM, May 04 '16 at 12:50
About p1/p2 order: of course it does not invert the creation order, but only the "sorted" order of p1 and p2. If the objects where added to a set, and the set iterated, p1 and p2 would have been inverted. Is the "sorted order" of pointers deterministic for a given C++ code, or does different compilations or different run can have different sorted orders ? — MickaëlG, May 04 '16 at 13:07
The "sorted order" is deterministic and guaranteed. most implementations implements `std::set` as a RB-tree ... I think your main problem is the `order` of creation of pointers: - and when you are allocating on heap, the "order" of pointer addresses returned by the memory allocator is NOT guaranteed, so, yes, that *can* change anytime — WhiZTiM, May 04 '16 at 13:16
@WhiWTiM, "the order of pointer addresses returned by the memory allocator is NOT guaranteed, so, yes, that can change anytime" => Ok. So my question is: can I do something between two consecutive run to influence it and make it different than previous run. — MickaëlG, May 04 '16 at 13:23
@MickaëlG, Yes, Its easier for you to create the elements in a random fashion as described in my answer, doing that `will (randomize)` make it different from the previous run. However, you can write your own `T` specific memory allocator to allocate memory at random for you from a memory pool (using random locations in the pool) — WhiZTiM, May 04 '16 at 13:30
The easiest way to randomize your set or map is to add a custom comparator. Have a `map grmap`, populate with `(pointer, somerandomint)` pairs and use `grmap[pointer]` in the comparator. — n. m. could be an AI, May 04 '16 at 14:30

score -2 · Answer 2 · answered May 04 '16 at 12:26

The order you allocate objects on heap is totally up to you. BTW, you do remember that std::set when destroyed only calls its contents destructors, which in case of pointers means pointers are simply not there, while the objects they pointed to remain in the heap and probably have become dangling references, right? If you store plain pointers in std containers do not forget to delete them manually.

Reproducing random std::set order

2 Answers2