CODEWITHSUNDEEP
c++for-loopinsertiteratorset
Jonathan Mee
Jonathan Mee

Reputation: 38919

Inserting to set in a "Fixed" Size Loop

So I wanted to insert the double of all the elements in my set back into the set. But obviously I need to grab the end iterator so that I don't keep iterating over new elements. (Don't worry, I checked, set::insert doesn't invalidate iterators: http://www.cplusplus.com/reference/set/set/insert/#validity) So given the input, set<int> foo = { 1, 2, 3 }, here's what I did:

for(auto it = begin(foo), finish = end(foo); it != finish; ++it) {
    foo.insert(*it * 2);
}

I expected my set to contain:

1, 2, 3, 4, 6

Surprise! It contains:

-2147483648, -1073741824, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 786432, 1048576, 1572864, 2097152, 3145728, 4194304, 6291456, 8388608, 12582912, 16777216, 25165824, 33554432, 50331648, 67108864, 100663296, 134217728, 201326592, 268435456, 402653184, 536870912, 805306368, 1073741824, 1610612736

Live Example

Clearly end(foo) doesn't work as I thought it did. So... if I want to save the loops size and count to that?

Upvotes: 5

Views: 1524

Answers (5)

Jonathan Mee
Jonathan Mee

Reputation: 38919

I believe that your assumption is that a set is allocated into a contiguous container with the presumption that it initially had enough space that reallocation of the contiguous container was not necessary; in this assumed case I would also expect to see your behavior. (It should be noted though that even in a situation where this were a contiguous container, the container's capacity would need to be validated for this assumption to avoid undefined behavior.)

But even in your question you point out that insert doesn't invalidate iterators, which means that the container cannot be contiguous. In fact sets:

Are typically implemented as binary search trees

Understanding this you're really just continuing your loop till your iterator ends pointing to the last leaf node. Your compilers set implementation caused that to happen when you inserted the -2147483648 element, but that's implementation dependent, and thus may behave differently on another compiler.

You're looking for a behavior that is defined and compiler independent. Depending upon you're knowledge of the set contents you could reverse iterate over the set:

for(auto it = rbegin(foo); it != rend(foo); ++it) {
    foo.insert(*it * 2);
}

This is only a good solution if the insertion creates elements that are sorted after those being iterated over. For example if foo contains negative numbers this won't work. You could evaluate this by checking: if(*cbegin(foo) < 0) in the else-block you could do the reverse iteration loop suggested above, but in the otherwise you'd need to do a temporary set allocation described in The Quantum Physicist's answer.

Upvotes: 0

P0W
P0W

Reputation: 47784

Iterators are still valid, but as a std::set is a node-based container, the elements are always sorted, using std::less<Key> by default

See how iterators are jumping to lower values, making it to struggle for finish

Code snippet:

    for(  ; it != finish; ++it)
    {
        auto t = *it  ;
        std::cout << "At " << t  << "\n";
        foo.insert( t * 2  ) ;
        std::cout << "Inserted " << t*2  << "\n";
    }

At 1
Inserted 2
At 2
Inserted 4           <----+
At 3                      |
Inserted 6                | <---+ 
At 4  // jumped back -----+     |
Inserted 8                      |
At 6  // Jumped back -----------+
Inserted 12
At 8
.....

Upvotes: 2

The Quantum Physicist
The Quantum Physicist

Reputation: 26256

This is obviously circular. The size is increasing in every step, making the loop never reach the end.

It's like saying: Take this list, start from the first element, and keep doing this for every element, and when you're done, add one more element to the same list.

Why would this ever end?

EDIT:

Answering: "So... if I want to save the loops size and count to that?":

int size = foo.size();
std::set<int> bar;
for(auto it = begin(foo); it != end(foo); ++it) {
    bar.insert(*it * 2);
}
foo.insert(bar.begin(), bar.end());

Upvotes: 1

Tim
Tim

Reputation: 1286

If you truly want to save the loops size and count to that, you can do something like this:

set<int> foo = { 1, 2, 3 };

int setSize = foo.size();
auto it = foo.begin();

for(int i = 0; i < setSize; ++i) {
    foo.insert(*it * 2);
    ++it;
}

copy(cbegin(foo), cend(foo), ostream_iterator<int>(cout, " "));

This will give you the output: 1 2 3 4 6

Upvotes: 1

Baldrickk
Baldrickk

Reputation: 4409

A typical method of doing this would be to iterate through your source set, and perform your function on each value, adding the result into a second set. Once you are finished with the iteration process and have fully generated the second set, union the two sets together.

Upvotes: 1

Related Questions