newbie question: insert a vector to itself at end

[anhongl...@gmail.com]

Recently I found this is not working....
I am trying to insert a vector itself to its end.

Here people even complains that v.push_back(p.front()) won't work!
https://www.reddit.com/r/cpp/comments/vog1p/a_commonly_unknown_stdvector_pitfall/


I tried, the v.push_back(v.front()) for my gcc8 works.
But the following code doesn't

Experts, why this is implemented as NOT WORKING?
It's for me as can't understand.

Thanks,
Anhong



#include <vector>
#include <string>

int main()
{
std::vector<std::string> v
{
"1",
"2",
"3",
};

v.push_back(v.front());

for(int i = 0; i < 2; ++i){
v.insert(v.end(), v.begin(), v.begin() + 3);
}

return 0;
}

[Alf P. Steinbach]

On 11.05.2019 08:49, anhongl...@gmail.com wrote:
> Recently I found this is not working....
> I am trying to insert a vector itself to its end.
>
> Here people even complains that v.push_back(p.front()) won't work!
> https://www.reddit.com/r/cpp/comments/vog1p/a_commonly_unknown_stdvector_pitfall/

That's incorrect, as also noted by Stephan T. Lavavej (the person in
charge of STL maintenance at Microsoft) in a comment there.

> I tried, the v.push_back(v.front()) for my gcc8 works.
> But the following code doesn't
>
> Experts, why this is implemented as NOT WORKING?
> It's for me as can't understand.
>
> Thanks,
> Anhong
>
>
>
> #include <vector>
> #include <string>
>
> int main()
> {
> std::vector<std::string> v
> {
> "1",
> "2",
> "3",
> };
>
> v.push_back(v.front());
>
> for(int i = 0; i < 2; ++i){
> v.insert(v.end(), v.begin(), v.begin() + 3);
> }
>
> return 0;
> }

Works for me with both Visual C++ 2017 and MinGW g++ 8.2 compilers.

And I don't see any practical reason why it shouldn't work, since the
vector code can easily detect copying from self and ensure a
sufficiently large new buffer if necessary.

Can you provide an example, with the compiler version & invocation,
where it doesn't work according to your expectations?


Cheers!,

- Alf

[Bonita Montero]

> Works for me with both Visual C++ 2017 and MinGW g++ 8.2 compilers.

LOL.

[Manfred]

On 5/11/19 9:37 AM, Alf P. Steinbach wrote:
> On 11.05.2019 08:49, anhongl...@gmail.com wrote:
>> Recently I found this is not working....
>> I am trying to insert a vector itself to its end.
>>
>> Here people even complains that v.push_back(p.front()) won't work!
>> https://www.reddit.com/r/cpp/comments/vog1p/a_commonly_unknown_stdvector_pitfall/
>>
>
> That's incorrect, as also noted by Stephan T. Lavavej (the person in
> charge of STL maintenance at Microsoft) in a comment there.
>

The comments refers to:
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526
Which says:
"vector::insert(iter, value) is required to work because the standard
doesn't give permission for it not to work."

Which is obvious if value is an actual value, and 23.2.3 p4 describes
a.insert(p,t) where "t denotes an lvalue or a const rvalue of
X::value_type" (p3), but:
23.3.6.1 says the signature of front is:
const_reference front() const;
23.3.6.5 specifies:
iterator insert(const_iterator position, const T& x);
that takes a const reference, and specifies:
"Causes reallocation if the new size is greater than the old capacity" (p1)
and 23.3.6.3 (vector capacity) clarifies that:
"Reallocation invalidates all the references, pointers, and iterators
referring to the elements in the sequence" (p6)

So, I am most probably missing something, because to me there is some
unclarity between "lvalue or const rvalue of X:value_type" of 23.2.3
(requirements for sequence containers) and "const reference to T" of
23.3.6 (vector member signatures).

Anyway, since defect 526 has been closed as "not a defect" by the
committee, it can probably be trusted to work, and in fact it works for
gcc 8.3

>
>> I tried, the v.push_back(v.front()) for my gcc8 works.
>> But the following code doesn't
>>
>> Experts, why this is implemented as NOT WORKING?
>> It's for me as can't understand.
>>
>> Thanks,
>> Anhong
>>
>>
>>
>> #include <vector>
>> #include <string>
>>
>> int main()
>> {
>>      std::vector<std::string> v
>>      {
>>          "1",
>>          "2",
>>          "3",
>>      };
>>
>>      v.push_back(v.front());
>>
>>      for(int i = 0; i < 2; ++i){
>>          v.insert(v.end(), v.begin(), v.begin() + 3);
>>      }
>>
>>      return 0;
>> }
>
> Works for me with both Visual C++ 2017 and MinGW g++ 8.2 compilers.

It doesn't work with gcc 8.3

>
> And I don't see any practical reason why it shouldn't work, since the
> vector code can easily detect copying from self and ensure a
> sufficiently large new buffer if necessary.

No, 23.2.3 p4 clearly states the pre-condition for
a.insert(p, i, j)
"i and j are not iterators into a."

And in fact i and j are invalidated by insert if a reallocation occurs.

[Alf P. Steinbach]

On 11.05.2019 19:31, Manfred wrote:
> On 5/11/19 9:37 AM, Alf P. Steinbach wrote:
>> On 11.05.2019 08:49, anhongl...@gmail.com wrote:

>>> [snip]

>>>
>>> #include <vector>
>>> #include <string>
>>>
>>> int main()
>>> {
>>>      std::vector<std::string> v
>>>      {
>>>          "1",
>>>          "2",
>>>          "3",
>>>      };
>>>
>>>      v.push_back(v.front());
>>>
>>>      for(int i = 0; i < 2; ++i){
>>>          v.insert(v.end(), v.begin(), v.begin() + 3);
>>>      }
>>>
>>>      return 0;
>>> }
>>
>> Works for me with both Visual C++ 2017 and MinGW g++ 8.2 compilers.
>
> It doesn't work with gcc 8.3

Oh.

>> And I don't see any practical reason why it shouldn't work, since the
>> vector code can easily detect copying from self and ensure a
>> sufficiently large new buffer if necessary.
>
> No, 23.2.3 p4 clearly states the pre-condition for
> a.insert(p, i, j)
> "i and j are not iterators into a."

I overlooked that one, thanks!

In C++17 it's in table 87 in §25.2.3/4, a.k.a. §sequence.reqmts/4.

Thinking about it, it's probably due to the design where the iterators
are general /input iterators/, which I didn't notice either. So one
could define some custom stream like iterators that read from a vector,
and try to use those to insert into the same vector, and wham bang. It
seems the wording covers that, by excluding “iterators into a”.

I didn't think of that.

But now that I do, I still don't see any practical reason for it. One
could change the design to have the general input iterator based insert
called `insert_input`, add a random iterator based `insert`, and allow
the former to be optimized by deferring to the latter when iterator
traits say the iterators are actually random access. The random iterator
based `insert` can easily check for self-referencing iterators by using
`std::less` (say, because total ordering) on the item pointers.

Then the no-self-ref requirement would be only on `insert_input`.

> And in fact i and j are invalidated by insert if a reallocation occurs.

Yes but as I see it, considering not just how conceptually easy this is
to implement (though it would be some coding work to do it) but that at
least two such implementations apparently exist, that's irrelevant. The
iterators are then valid before the operation, and invalid after, but
that's all that one can say. One cannot conclude anything about the
operation's success or well-defined-ness from that, as I see it.


Cheers!,

- Alf

[Alf P. Steinbach]

Here's how I envision a `std::vector` design without the self reference
trap, like (the just sufficient for the OP's example) `my::Vec` below:


-----------------------------------------------------------------------
#include <vector>
#include <string>
#include <functional> // std::(less_or_equal)
#include <iterator> // std::iterator_traits
#include <memory> // std::addressof
#include <type_traits> // std::is_same_v
#include <utility> // std::(enable_if_t, move)

namespace my{
using std::addressof, std::move, std::random_access_iterator_tag;

template< bool condition >
using Enable_if_ = std::enable_if_t<condition>;

template< class A, class B >
constexpr bool is_same_type_ = std::is_same_v<A, B>;

template< class T >
using It_category_ = typename
std::iterator_traits<T>::iterator_category;

template< class Item >
class Vec:
private std::vector<Item>
{
using Base = std::vector<Item>;
public:
using iterator = typename Base::iterator;
using const_iterator = typename Base::const_iterator;
using Index = typename Base::difference_type;

using Base::begin;
using Base::cbegin;
using Base::data;
using Base::end;
using Base::front;
using Base::push_back;
using Base::reserve;
using Base::size;

template<
class Rnd_it,
class = Enable_if_<is_same_type_<
It_category_<Rnd_it>,
random_access_iterator_tag
> >
>
auto insert(
const const_iterator position,
const Rnd_it first,
const Rnd_it last )
-> iterator
{
const Index i_position = position - cbegin();
iterator pos = begin() + i_position;
if( first == last ) {
return pos;
}

const auto p_first = addressof( *first );
constexpr auto less_or_equal = std::less_equal<const Item*>();

if( less_or_equal( data(), p_first ) and
less_or_equal( p_first, data() + size() ) ) {
Vec copies( first, last );
reserve( size() + (last - first) );
for( Item& item: copies ) {
pos = Base::insert( pos, move( item ) );
}
return pos;
}

return Base::insert( position, first, last );
}

template< class Input_it>
auto insert_input(
const const_iterator position,
const Input_it first,
const Input_it last
) -> iterator
{
using Rnd_tag = random_access_iterator_tag;
if constexpr( is_same_type_<It_category_<Input_it>,
Rnd_tag> ) {
return insert( position, first, last );
} else {
return Base::insert( position, first, last );
}
}

using Base::Base;
};

} // namespace my

auto main()
-> int
{
my::Vec<std::string> v

{
"1",
"2",
"3",
};

v.push_back(v.front());

for( int i = 0; i < 2; ++i ) {

v.insert( v.end(), v.begin(), v.begin() + 3 );
}

return v.size();
}
-----------------------------------------------------------------------


> [snip]

Cheers!,

- Alf

[Alf P. Steinbach]

On 12.05.2019 00:25, Alf P. Steinbach wrote:
> [code with a 2 little bugs]

Strange that I should introduce bugs in something so simple. But then
it's late in the day, and I'm an old man (sort of). So it's not
guaranteed that this fixed code is entirely bug-free either.


#include <assert.h>

if( first == last ) {

return begin() + i_position;

}

const auto p_first = addressof( *first );
constexpr auto less_or_equal = std::less_equal<const Item*>();

if( less_or_equal( data(), p_first ) and
less_or_equal( p_first, data() + size() ) ) {
Vec copies( first, last );
reserve( size() + (last - first) );

iterator pos = begin() + i_position;

for( Item& item: copies ) {

Base::insert( pos, move( item ) );

++pos;

Cheers!,

- Alf

[Alf P. Steinbach]

On 12.05.2019 00:53, Alf P. Steinbach wrote:
> On 12.05.2019 00:25, Alf P. Steinbach wrote:
>> [code with a 2 little bugs]
>
> Strange that I should introduce bugs in something so simple. But then
> it's late in the day, and I'm an old man (sort of). So it's not
> guaranteed that this fixed code is entirely bug-free either.
>

Yup, just two seconds after pressing “Send” in Thunderbird, I noticed
that an assignment was missing.

for( Item& item: copies ) {

pos = Base::insert( pos, move( item ) );
++pos;
}


So.


Cheers!,

- ALf

[Alf P. Steinbach]

And just after that, well maybe some minutes, I noticed that the above
has quadratic time.

The requirement is for linear time.

So, ...

#include <assert.h>
#include <vector>
#include <string>
#include <functional> // std::(less_or_equal)
#include <iterator> // std::iterator_traits
#include <memory> // std::addressof
#include <type_traits> // std::is_same_v

#include <utility> // std::(enable_if_t, move, swap)

namespace my{
using std::addressof, std::move, std::random_access_iterator_tag,
std::swap;

template< bool condition >
using Enable_if_ = std::enable_if_t<condition>;

template< class A, class B >
constexpr bool is_same_type_ = std::is_same_v<A, B>;

template< class T >
using It_category_ = typename
std::iterator_traits<T>::iterator_category;

template< class Item >
class Vec:
private std::vector<Item>
{
using Base = std::vector<Item>;
public:
using iterator = typename Base::iterator;
using const_iterator = typename Base::const_iterator;
using Index = typename Base::difference_type;

using Size = Index;

using Base::begin;
using Base::cbegin;
using Base::data;
using Base::end;
using Base::front;
using Base::push_back;
using Base::reserve;
using Base::size;

auto ssize() const -> Size { return size(); }

template<
class Rnd_it,
class = Enable_if_<is_same_type_<
It_category_<Rnd_it>,
random_access_iterator_tag
> >
>
auto insert(
const const_iterator position,
const Rnd_it first,
const Rnd_it last )
-> iterator
{
const Index i_position = position - cbegin();
if( first == last ) {
return begin() + i_position;
}

const auto p_first = addressof( *first );
constexpr auto less_or_equal = std::less_equal<const Item*>();

if( less_or_equal( data(), p_first ) and
less_or_equal( p_first, data() + size() ) ) {
Vec copies( first, last );

reserve( ssize() + (last - first) );

iterator pos = begin() + i_position;

Vec tail_items;
tail_items.reserve( ssize() - i_position );
for( Index i = i_position; i < ssize(); ++i ) {
tail_items.push_back( move( operator[]( i ) ) );
}
resize( i_position );

for( Item& item: copies ) {

push_back( move( item ) );
}
for( Item& item: tail_items ) {
push_back( move( item ) );
}
return begin() + i_position;
}

return Base::insert( position, first, last );
}

template< class Input_it>
auto insert_input(
const const_iterator position,
const Input_it first,
const Input_it last
) -> iterator
{
using Rnd_tag = random_access_iterator_tag;
if constexpr( is_same_type_<It_category_<Input_it>,
Rnd_tag> ) {
return insert( position, first, last );
} else {
return Base::insert( position, first, last );
}
}

using Base::Base;
};

} // namespace my

#include <iostream>

auto main()
-> int
{
my::Vec<std::string> v
{
"1",
"2",
"3",
};

v.push_back(v.front());

for( int i = 0; i < 2; ++i ) {
v.insert( v.end(), v.begin(), v.begin() + 3 );
}

using namespace std;
for( const string& s: v ) { cout << s << ' '; } cout << endl;
return v.size();
}


Cheers!,

- Alf (in a late monologue with himself, evidently, and now quite tired
so no correctness guarantees...)

[Bonita Montero]

> "Reallocation invalidates all the references, pointers, and
> iterators referring to the elements in the sequence" (p6)

I wondered why no one saw this possible reallocation for
half a day. My "Lol" was because of Alf's "Works for me ..."
because of that.

[Bonita Montero]

> #include <vector>
> #include <string>
>
> int main()
> {
> std::vector<std::string> v
> {
> "1",
> "2",
> "3",
> };

v.reserve( 3 + 1 + 2 * 3 );

[Alf P. Steinbach]

I believe everyone that replied, were very much aware of that. However,
I failed to see notice the general sequence container requirements that
forbids `insert` of a part of the container itself, and Manfred pointed
that out. I also failed to see, originally, the lack of discrimination
on iterator kind, the non-existence of an `insert` for random access.

When all that's known or assumed about the iterators is that they're
general input iterators, as opposed to at least having a distinct case
for random access iterators, the vector implementation can't check
whether the iterators refer to itself. Of course, a `std::list` can't do
that anyway without embedding instance id's into the iterators, which
would be a cost for a feature that's seldom if ever used. But since a
vector has a guaranteed contiguous buffer it can check.

So, it's not reallocation and invalidation itself that's problematic,
it's a design where all insertion from sequence is shoehorned into a
single function whose iterators are only assumed to be input iterators.

It's a weird design.

I still fail to see any practical reason for it other then /easing the
work of library implementors/, even after Manfred implicitly pointed out
the issue with iterator kind assumptions that I had failed to see.


Cheers!,

- Alf

[Bonita Montero]

> So, it's not reallocation and invalidation itself ...

No, it is.

> It's a weird design.
> I still fail to see any practical reason for it other then /easing the
> work of library implementors/, even after Manfred implicitly pointed out
> the issue with iterator kind assumptions that I had failed to see.

It's a design made for performance.

[Alf P. Steinbach]

On 12.05.2019 15:03, Bonita Montero wrote:
>> So, it's not reallocation and invalidation itself ...
>
> No, it is.

Are you talking baby-talk to me? What?

>> It's a weird design.
>> I still fail to see any practical reason for it other then /easing the
>> work of library implementors/, even after Manfred implicitly pointed
>> out the issue with iterator kind assumptions that I had failed to see.
>
> It's a design made for performance.

There's nothing performant about having to copy out a subsequence before
copying it back into the same vector.

The vector itself could do it much more efficiently, avoiding at least
one dynamic allocation.

It's just that /by design/ it can't, and I think that's pretty weird for
a C++ thing.


Cheers & hth.,

- Alf

[Bonita Montero]

>>> It's a weird design.
>>> I still fail to see any practical reason for it other then /easing
>>> the work of library implementors/, even after Manfred implicitly
>>> pointed out the issue with iterator kind assumptions that I had
>>> failed to see.

>> It's a design made for performance.

> There's nothing performant about having to copy out a subsequence before
> copying it back into the same vector.

The problem is that the vector can't be grown in-place of the capacity
isn't high enough. So the iterators must be invalid.

[Alf P. Steinbach]

You can look at the code I posted late-night (for me) in this thread for
a direct counter-example to your assertion regarded as an in-context
argument. The iterators are invalid after the operation, not at the
beginning of it. Keeping things correct during the operation is not
entirely trivial, but it's not difficult either, just typical coding.

That code isn't as efficient as if the vector itself had done it,
because the vector has access to uninitialized parts of its own buffer
and that code instead needs to use a separate vector for temp storage,
but it demonstrates that modulo performance there's no problem.

The performance is why ideally the vector itself should do it.

[Bonita Montero]

> You can look at the code I posted late-night (for me) in this thread
> for a direct counter-example to your assertion regarded as an in-context
> argument. The iterators are invalid after the operation, not at the
> beginning of it. Keeping things correct during the operation is not
> entirely trivial, but it's not difficult either, just typical coding.

This implementation doesn't fit with the C++-paradigm o a minimal
overhead.

[Alf P. Steinbach]

Prove it, and why that would still hold if the vector did it itself.

As far as I'm concerned it's just a nonsense assertion, but there could
always be something I didn't think of.


Cheers!,

- Alf

[Bonita Montero]

>> This implementation doesn't fit with the C++-paradigm o a minimal
>> overhead.

> Prove it, ...

Have a look at my fix of the OP's code.
There's only _one_ additional reserve().

[Alf P. Steinbach]

That has nothing to do with your assertion or proof of it.

As it happens your in-practice fix of the OP's code is formally invalid,
because the standard (in table 87 in §25.2.3/4, a.k.a.
§sequence.reqmts/4.) requires that iterators passed to `insert` do not
refer to that container, and that's why I didn't do things that way.

If it had been formally valid, say due to the standard having a special
case for random access iterators, then it would not be a /general/ fix
for that case because it requires reserve first, then obtaining
iterators. A fix of that secondary problem, so that one can start out
with the iterators for the range to be inserted, is to check whether the
iterators refer to the vector, and if so transform the iterators into
indices, reserve, then obtain iterators corresponding to the indices.

And that's half of what goes on in the code I posted.

The rest of that code was about conforming to the (C++17 table 87)
prohibition on passing iterators to the vector itself, to `insert`.


Cheers & hth.

- Alf

[Bonita Montero]

> As it happens your in-practice fix of the OP's code is formally invalid,
> because the standard (in table 87 in §25.2.3/4, a.k.a.
> §sequence.reqmts/4.) requires that iterators passed to `insert` do not
> refer to that container, and that's why I didn't do things that way.

Pure theory ...

[Alf P. Steinbach]

Oh look, here's a link to the corresponding place in the current draft,

<url:
http://eel.is/c++draft/sequence.reqmts#tab:containers.sequence.requirements>.

Quote:
“Neither i nor j are iterators into a”, where `i` and `j` are the two
iterators denoting the range to be inserted by `insert`.

[Bonita Montero]

>> Pure theory ...
>
> Oh look, here's a link to the corresponding place in the current draft,
> <url:
> http://eel.is/c++draft/sequence.reqmts#tab:containers.sequence.requirements>.
> Quote:
> “Neither i nor j are iterators into a”, where `i` and `j` are the two
> iterators denoting the range to be inserted by `insert`.
> Cheers & hth.,

Pure theory!

[Manfred]

On 5/12/19 8:01 PM, Alf P. Steinbach wrote:
> On 12.05.2019 18:01, Bonita Montero wrote:
>>>> This implementation doesn't fit with the C++-paradigm o a minimal
>>>> overhead.
>>
>>> Prove it, ...
>>
>> Have a look at my fix of the OP's code.
>> There's only _one_ additional reserve().
>
> That has nothing to do with your assertion or proof of it.
>
> As it happens your in-practice fix of the OP's code is formally invalid,
> because the standard (in table 87 in §25.2.3/4, a.k.a.
> §sequence.reqmts/4.) requires that iterators passed to `insert` do not
> refer to that container,

Indeed.

and that's why I didn't do things that way.
>
> If it had been formally valid, say due to the standard having a special
> case for random access iterators, then it would not be a /general/ fix
> for that case because it requires reserve first, then obtaining
> iterators. A fix of that secondary problem, so that one can start out
> with the iterators for the range to be inserted, is to check whether the
> iterators refer to the vector, and if so transform the iterators into
> indices, reserve, then obtain iterators corresponding to the indices.

I didn't look into your code (too late here for me now), but if the
intention is to solve the prohibition of §sequence.reqmts/4 by
reimplementing a suitable vector, then there should be no need to
convert from iterator to indices and then iterators.
The steroided vector could do the following:

if a reallocation is needed, then:
- allocate new storage.
- copy the elements to be inserted from old storage to new storage in
their target positions.
- move all elements from old storage to new storage into their target
positions; since this is an insert() operation there is no overlap.
- free the old storage and rebase the vector on the new storage.
end

Iterators pointing into the original vector were valid when entering
insert(), and are invalid upon exit from insert()

I guess this is what happens with insert(pos, const T&), i.e. insert a
single element, even if it is a reference into the current vector.

[Alf P. Steinbach]

Not sure exactly what you mean, but the "target position" of the
sequence to be inserted is an iterator into the original storage.

To get that position in the new storage one needs an index.

That said the logic you sketch, checking if reallocation is needed, is
more elegant than what evolved out of my coding. :-)

> Iterators pointing into the original vector were valid when entering
> insert(), and are invalid upon exit from insert()
>
> I guess this is what happens with insert(pos, const T&), i.e. insert a
> single element, even if it is a reference into the current vector.
>
>>
>> And that's half of what goes on in the code I posted.
>>
>> The rest of that code was about conforming to the (C++17 table 87)
>> prohibition on passing iterators to the vector itself, to `insert`.

Cheers!,

- Alf

[Paavo Helde]

On 13.05.2019 4:39, Alf P. Steinbach wrote:
> On 13.05.2019 00:52, Manfred wrote:
>>
>> I didn't look into your code (too late here for me now), but if the
>> intention is to solve the prohibition of §sequence.reqmts/4 by
>> reimplementing a suitable vector, then there should be no need to
>> convert from iterator to indices and then iterators.
>> The steroided vector could do the following:
>>
>> if a reallocation is needed, then:
>> - allocate new storage.
>> - copy the elements to be inserted from old storage to new storage
>> in their target positions.
>> - move all elements from old storage to new storage into their
>> target positions; since this is an insert() operation there is no
>> overlap.
>> - free the old storage and rebase the vector on the new storage.
>> end
>
> Not sure exactly what you mean, but the "target position" of the
> sequence to be inserted is an iterator into the original storage.
>
> To get that position in the new storage one needs an index.

That's the same as with the regular insert() whenever there is a
reallocation. That's not an issue to be debated.

[Juha Nieminen]

anhongl...@gmail.com wrote:
> Experts, why this is implemented as NOT WORKING?
> It's for me as can't understand.

Because you are using iterators that are being invalidated while new
elements are being added to the vector.

If you do a reserve() call with the final size before the insertion,
it should work.

Note, however, that constantly calling reserve() with the new expected
size can actually make std::vector very inefficient.

How so? Because most common std::vector implementations will allocate
*exactly* the specified amount of space, if the value you give is
larger than the current capacity.

This means that if you do eg. v.reserve(v.size()+1) before each
v.push_back(), those insertions will become linear-time rather
than constant-time. Thus this should be used carefully.

[Manfred]

Not really, a regular insert can proceed entirely with iterators only,
the problem for a self-referencing insert is that this results in
copying some elements that have already been move()d from.

That's not an issue to be debated.

Probably so, if performance is at all affected, it's a matter of
nanoseconds. Effect on code is only a matter of style.
>

[Ike Naar]

On 2019-05-11, Stefan Ram <r...@zedat.fu-berlin.de> wrote:
> r...@zedat.fu-berlin.de (Stefan Ram) writes:
>>(circular! (list 1 2 3))
>>( 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ... )
>
> Lurkers told my in e-mail that this is not C++.
>
> So, here is my attempt to use a circular list in C++
> using std-containers. The code "works" but I don't
> know whether this behaviour is guaranteed by the
> standard or just showing under my implementation!
>
> main.cpp
>
> #include <iostream>
> #include <list>
>
> int main()
> { ::std::list< int >l;
> l.push_back( 2 );
> l.push_back( 4 );
> l.push_front( 7 );
> int c {};
> for( auto i = l.begin();; ++i )
> { if( i != l.end() )::std::cout << *i << '\n';
> if( c++ > 20 )break; }}

Is ++i, when i equals l.end(), a well-defined operation ?

[Bonita Montero]

> If you do a reserve() call with the final size before the insertion,
> it should work.

_Theoretically_ the first and last iterators of shouldn't "point" into
*this. But that's pure theory and I think the writers of the standard
were just to lazy to refine this statement with the cases where this
should actually work with any STL-implementation, i.e. when the capacity
is large enough and first and last are before the point where the insert
takes place.

[Öö Tiib]

AFAIK dereferencing or incrementing it is undefined
behavior always.
Decrementing it is well-defined operation when the
list is not empty.

[james...@alumni.caltech.edu]

On Monday, May 13, 2019 at 10:34:35 AM UTC-4, Bonita Montero wrote:
...

> _Theoretically_ the first and last iterators of shouldn't "point" into
> *this. But that's pure theory and I think the writers of the standard
> were just to lazy to refine this statement with the cases where this
> should actually work with any STL-implementation, i.e. when the capacity
> is large enough and first and last are before the point where the insert
> takes place.

It is not particularly unusual for the committee to notice a problematic situation, and then to write a rule to avoid/fix that situation that
covers not only the problematic case, but other unproblematic cases. The
reason for this is not laziness, but avoiding making the rule too
complex. A simpler rule makes it easier for developers or automated code
checkers to check whether a particular program violates the rule. It
also makes it easier for implementors to determine whether or not a
possible implementation will be OK, so long as the rule is not violated.

Writing a more general, simpler rule has consequences. Because
implementors will be relying upon the simpler rule rather than the more
complicated one, there's a possibility an implementation might end up
containing code that doesn't work when the simpler rule is violated,
even in situations that wouldn't violate the more complicated one. In
other words, they might discover an optimization opportunity that wasn't
part of the motivation for the simpler rule, but ends up motivating
keeping the rule simple. And because of that possibility, it's not safe
to assume that the more complicated rule correctly identifies which
uses are safe.