473,231 Members | 1,790 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,231 software developers and data experts.

Invalidating iterators after insertion/removal


If I insert/remove an element in a set, will an iterator to this set
automatically become invalid? Does the position of the iterator before the
insertion/removal matter?

How are vectors and lists affected?
Jun 6 '07 #1
6 2297
"barcaroller" <ba*********@music.netwrote in
news:f4**********@aioe.org:
>
If I insert/remove an element in a set, will an iterator to this set
automatically become invalid? Does the position of the iterator
before the insertion/removal matter?
Insertion doesn't invalidate iterators into a set, deletion will invalidate
iterators (and pointers and references) to that element only.
How are vectors and lists affected?
Lists have the same rules as set. For vectors, insertion may invalidate
_all_ iterators into the vector if the insertion requires a reallocation.
(Hadn't thought about it, but it would invalidate all iterators at the
point of insertion and beyond in all cases. Then again, vectors are most
frequently added to at the end of the container, so there's normally
nothing to invalidate.) Deletion from a vector invalidates that iterator
and all iterators past it.
Jun 6 '07 #2
Andre Kostur wrote:
"barcaroller" <ba*********@music.netwrote in
news:f4**********@aioe.org:
>If I insert/remove an element in a set, will an iterator to this set
automatically become invalid? Does the position of the iterator
before the insertion/removal matter?

Insertion doesn't invalidate iterators into a set, deletion will invalidate
iterators (and pointers and references) to that element only.
>How are vectors and lists affected?

Lists have the same rules as set. For vectors, insertion may invalidate
_all_ iterators into the vector if the insertion requires a reallocation.
(Hadn't thought about it, but it would invalidate all iterators at the
point of insertion and beyond in all cases. Then again, vectors are most
frequently added to at the end of the container, so there's normally
nothing to invalidate.) Deletion from a vector invalidates that iterator
and all iterators past it.
How is a vector implemented? I know that set and map are just
abstractions of a red-black tree, but what about vectors?
Jun 7 '07 #3
On 7 Juni, 09:58, desktop <f...@sss.comwrote:
Andre Kostur wrote:
"barcaroller" <barcarol...@music.netwrote in
news:f4**********@aioe.org:
If I insert/remove an element in a set, will an iterator to this set
automatically become invalid? Does the position of the iterator
before the insertion/removal matter?
Insertion doesn't invalidate iterators into a set, deletion will invalidate
iterators (and pointers and references) to that element only.
How are vectors and lists affected?
Lists have the same rules as set. For vectors, insertion may invalidate
_all_ iterators into the vector if the insertion requires a reallocation.
(Hadn't thought about it, but it would invalidate all iterators at the
point of insertion and beyond in all cases. Then again, vectors are most
frequently added to at the end of the container, so there's normally
nothing to invalidate.) Deletion from a vector invalidates that iterator
and all iterators past it.

How is a vector implemented? I know that set and map are just
abstractions of a red-black tree, but what about vectors?
Since all elements must be stored in contiguous memory it is usually
implemented with an array.

--
Erik Wikström

Jun 7 '07 #4
Erik Wikström wrote:
Since all elements must be stored in contiguous memory it is usually
implemented with an array.
Usually? You mean there are other ways?
Jun 7 '07 #5
On 7 Juni, 12:59, Juha Nieminen <nos...@thanks.invalidwrote:
Erik Wikström wrote:
Since all elements must be stored in contiguous memory it is usually
implemented with an array.

Usually? You mean there are other ways?
Well, it's implementation dependent and there might be some
implementer that does something else (perhaps using malloc to reserve
a piece of memory and then use placement new or something). The point
is that it is not defined in the standard so it can be done however
you wish as long as it's compliant, however an array is probably the
easiest and best way to do it.

--
Erik Wikström

Jun 7 '07 #6
On Jun 7, 2:07 pm, Erik Wikström <eri...@student.chalmers.sewrote:
On 7 Juni, 12:59, Juha Nieminen <nos...@thanks.invalidwrote:
Erik Wikström wrote:
Since all elements must be stored in contiguous memory it is usually
implemented with an array.
Usually? You mean there are other ways?
Well, it's implementation dependent and there might be some
implementer that does something else (perhaps using malloc to reserve
a piece of memory and then use placement new or something). The point
is that it is not defined in the standard so it can be done however
you wish as long as it's compliant, however an array is probably the
easiest and best way to do it.
The standard requires that the memory be contiguous, i.e. that
&vect[i]+1 == &vect[i+1], for all valid i. Which pretty much
limits the choices in the implementation. The standard also has
pretty strict requirements concerning when constructors of
vector elements are called, and when iterators, pointers and
references are invalidated, which ultimately more or less
require that allocation and initialization be separated, i.e.
that placement new be used for construction. The standard also
requires that all dynamic memory used be allocated by the global
operator new() function (at least when the default allocator is
used). Given all this, an implementation really doesn't have
much freedom. A typical implementation will use three pointers:
one to the start, one to the end of the initialized values, and
one to the end of the raw memory---it may replace the latter two
with integral values, and it may add extra data for error
checking (i.e. a list of active iterators), but that's about it.

Note that vector<Tcannot be implemented using new T[]. It
must separate allocation and initialization.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jun 8 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

9
by: Jess Austin | last post by:
hi, I like the way that Python does lists, and I love the way it does iterators. But I've decided I don't like what it does with iterators of lists. Lists are supposed to be mutable sequences,...
0
by: Viper99 | last post by:
Need to detect (receive notification) for the insertion/removal of PCMCIA devices on Windows 2000/XP in a C# .Net application. Was able to do this in ATL COM app using CWnd::OnDeviceChange().
1
by: bartek | last post by:
Hi, I'm sorry for asking such a simple question. I just would like to know what's the standard-defined behaviour when doing a push_back() on a std::deque. TIA, b
19
by: John | last post by:
In STL's map implementation, the distance between two iterators it1, it2 takes O(K) to compute where K is the actual distance between the two iterators. In theory, a red black tree can do this...
13
by: prasadmpatil | last post by:
I am new STL programming. I have a query regarding vectors. If I am iterating over a vector using a iterator, but do some operations that modify the size of the vector. Will the iterator recognize...
0
by: subramanian100in | last post by:
Suppose I have vector<intc; for (int i = 0; i < 10; ++i) c.push_back(i); vector<int>::iterator it = find(c.begin(), c.end(), 5); If I do, c.insert(c.begin(), 10);
6
by: elizabeth1986 | last post by:
Hello, Is it possible to detect the insertion and removal of Plug and play devices (for example : keyboard , mouse etc) while the computer is still ON. We wanted to do the above in C#. We...
2
by: subramanian100in | last post by:
In ISO/IEC 14882:2003 document, in the section '23.2.1.3 deque modifiers', the following is mentioned: iterator insert(iterator position, const T& x); void insert(iterator position, size_type...
5
by: Leon | last post by:
using multimap<int,int>::iterator itlow = pq.lower_bound (x); multimap<int,int>::iterator itup = pq.upper_bound (y); I obtain lower and upper bound from the multimap, and having these two...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.