- newbie question: insert a vector to itself at end - 16 Updates
- Posting code leads to an improvement. - 2 Updates
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: May 12 01:34AM +0200 On 12.05.2019 01:01, Alf P. Steinbach wrote: > ++pos; > } > So. 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 <Bonita.Montero@gmail.com>: May 12 08:57AM +0200 > "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 <Bonita.Montero@gmail.com>: May 12 09:11AM +0200 > "2", > "3", > }; v.reserve( 3 + 1 + 2 * 3 ); |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: May 12 11:34AM +0200 On 12.05.2019 08:57, Bonita Montero wrote: > 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. 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 <Bonita.Montero@gmail.com>: May 12 03:03PM +0200 > So, it's not reallocation and invalidation itself ... No, it is. > 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" <alf.p.steinbach+usenet@gmail.com>: May 12 04:59PM +0200 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? >> 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 <Bonita.Montero@gmail.com>: May 12 05:04PM +0200 >> 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" <alf.p.steinbach+usenet@gmail.com>: May 12 05:25PM +0200 On 12.05.2019 17:04, Bonita Montero wrote: >> 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. 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. Cheers & hth., - Alf |
| Bonita Montero <Bonita.Montero@gmail.com>: May 12 05:44PM +0200 > 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" <alf.p.steinbach+usenet@gmail.com>: May 12 05:46PM +0200 On 12.05.2019 17:44, Bonita Montero wrote: >> typical coding. > This implementation doesn't fit with the C++-paradigm o a minimal > overhead. 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 <Bonita.Montero@gmail.com>: May 12 06:01PM +0200 >> 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" <alf.p.steinbach+usenet@gmail.com>: May 12 08:01PM +0200 On 12.05.2019 18:01, Bonita Montero wrote: >> 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, 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 <Bonita.Montero@gmail.com>: May 12 08:03PM +0200 > 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" <alf.p.steinbach+usenet@gmail.com>: May 12 08:09PM +0200 On 12.05.2019 20:03, Bonita Montero wrote: >> §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 ... 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., - Alf |
| Bonita Montero <Bonita.Montero@gmail.com>: May 12 08:27PM +0200 > "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 <noname@invalid.add>: May 13 12:52AM +0200 On 5/12/19 8:01 PM, Alf P. Steinbach wrote: > 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. > 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. |
| Sir Gaygory's Owner's Owner 🐶笛 <root@127.0.0.1>: May 12 04:36PM -0500 On Wed, 10 Apr 2019 22:10:58 -0700 (Seattle), LO AND BEHOLD; Jeff-Relf.Me @. determined that the following was of great importance and subsequently decided to freely share it with us in <Jeff-Relf.Me@Apr.10--10.10pm.Seattle.2019>: ✡✡✡✡✡✡✡✡✡✡✡ Oops, it should be: ✡✡✡✡✡✡✡✡✡✡✡ ✡✡✡✡✡✡✡✡✡✡✡ PageUp ? ( --PP < BB ? PP = EE : 0 ) : PageDwn ? ++PP > EE ? PP = BB : ✡✡✡✡✡✡✡✡✡✡✡ 0 : 0, iFolder = PP - BB, rFolders = EE - PP ; ✡✡✡✡✡✡✡✡✡✡✡ ✡✡✡✡✡✡✡✡✡✡✡ Often, posting code leads to an improvement. ✡✡✡✡✡✡✡✡✡✡✡ using meaningful variable names to make your code actually readable, unless you're trying to win an obfuscated coding contest. -- [THIS POAST HAS PASSED TRIMCHECK® VALIDATION] THIS SPACE FOR RENT https://www.youtube.com/watch?v=iB6B8jGSdLA "Thanks to muzzies and their apologist-enablers like puppy whistle, this seems to be the new norm in the world. It's spreading like a cancer, and it's time we admit we're at war with pure evil. We need to put an end to this muzzie plague, or life on Earth is going to become pure hell everywhere. We need to get these people out of every civilized country, and there's only one way to do it. IOW, we have to become like them, with an emphasis on expediency over cruelty." - Checkmate (of alt.checkmate) "Pussy Willow has just proven that Trump's crackdown on previously unenforced immigration policies is working. We'll deal with the domestic terrorists as needed, but we don't need to be letting the muzzie terrorists get a foothold in our country too. One need only look at what they're doing in Europe right now to know we're doing the right thing by keeping them out, which is our right and our duty. - Checkmate (#1 pussy willow fan) - "You just made puppy whistle's sig line longer." - Janithor - "If I have a complaint about the (Southern Poverty) Law Center's description (of the alt-right movement), it is the phrase "heavy use of social media," which implies the alt-right is a real-world movement which uses a lot of social media. This is backwards: it is an online movement which occasionally appears in the real world. Where it gets punched." - Jason Rhode - "I think we should destroy every last fucking mosque in America." - "Checkmate, DoW #1" <Lunatic.Fringe@The.Edge> proves for us that white males are violent in Message-ID: <MPG.32c5bfefd18c9a698f0a8@news.altopia.com> - Golden Killfile, June 2005 KOTM, November 2006 Bob Allisat Memorial Hook, Line & Sinker, November 2006 Special Ops Cody Memorial Purple Heart, November 2006 Special Ops Cody Memorial Purple Heart, September 2007 Tony Sidaway Memorial "Drama Queen" Award, November 2006 Busted Urinal Award, April 2007 Order of the Holey Sockpuppet, September 2007 Barbara Woodhouse Memorial Dog Whistle, September 2006 Barbara Woodhouse Memorial Dog Whistle, April 2008 Tinfoil Sombrero, February 2007 AUK Mascot, September 2007 Putting the Awards Out of Order to Screw With the OCD Fuckheads, March 2016 |
| % <persent@gmail.com>: May 12 02:38PM -0700 On 2019-05-12 2:36 p.m., Sir Gaygory's Owner's Owner 🐶笛 wrote: > ✡✡✡✡✡✡✡✡✡✡✡ Often, posting code leads to an improvement. > ✡✡✡✡✡✡✡✡✡✡✡ > using meaningful variable names to make your code actually readable, unless you're trying to win an obfuscated coding contest. i take vitamin c when i get a code |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment