* Charles: missing vector iterators @ 2002-11-13 17:15 Victor Porton 2002-11-14 9:22 ` Preben Randhol ` (4 more replies) 0 siblings, 5 replies; 10+ messages in thread From: Victor Porton @ 2002-11-13 17:15 UTC (permalink / raw) Why in Charles.Vectors iterators are missing even despite it is modelled after STL? Iterators are good for many things, including reliability: In enclosed loops: for i in ... loop for j in ... loop ... end loop; end loop; personally I often mess I and J. Probability to mess iterators is lesser than to mess natural number indexes because iterators are more type-safe. Please add these. BTW, may be put Chrles on SourceForge or something that if e.g. I will want to submit a patch it would become simpler? ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-13 17:15 Charles: missing vector iterators Victor Porton @ 2002-11-14 9:22 ` Preben Randhol 2002-11-14 12:10 ` Marc A. Criley ` (3 subsequent siblings) 4 siblings, 0 replies; 10+ messages in thread From: Preben Randhol @ 2002-11-14 9:22 UTC (permalink / raw) Victor Porton wrote: > personally I often mess I and J. Why don't you use propper variable names? -- Preben Randhol ------------------------ http://www.pvv.org/~randhol/ -- �There are three things you can do to a woman. You can love her, suffer for her, or turn her into literature.� - Justine, by Lawrence Durrell ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-13 17:15 Charles: missing vector iterators Victor Porton 2002-11-14 9:22 ` Preben Randhol @ 2002-11-14 12:10 ` Marc A. Criley 2002-11-14 15:30 ` Preben Randhol 2002-11-14 16:04 ` Matthew Heaney ` (2 subsequent siblings) 4 siblings, 1 reply; 10+ messages in thread From: Marc A. Criley @ 2002-11-14 12:10 UTC (permalink / raw) Victor Porton wrote: > > In enclosed loops: > > for i in ... loop > for j in ... loop > ... > end loop; > end loop; > > personally I often mess I and J. Probability to mess iterators is > lesser than to mess natural number indexes because iterators are more > type-safe. You can't mess with I and J inside a loop like this. They're effectively constants as far as the enclosed statements are concerned. Marc A. Criley Quadrus Corporation www.quadruscorp.com ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-14 12:10 ` Marc A. Criley @ 2002-11-14 15:30 ` Preben Randhol 0 siblings, 0 replies; 10+ messages in thread From: Preben Randhol @ 2002-11-14 15:30 UTC (permalink / raw) Marc A. Criley wrote: > You can't mess with I and J inside a loop like this. They're > effectively constants as far as the enclosed statements are concerned. I think he meant writing : A (J,I) in stead of A (I,J) -- Preben Randhol ------------------------ http://www.pvv.org/~randhol/ -- �There are three things you can do to a woman. You can love her, suffer for her, or turn her into literature.� - Justine, by Lawrence Durrell ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-13 17:15 Charles: missing vector iterators Victor Porton 2002-11-14 9:22 ` Preben Randhol 2002-11-14 12:10 ` Marc A. Criley @ 2002-11-14 16:04 ` Matthew Heaney 2002-11-15 7:10 ` Victor Porton 2002-11-15 7:27 ` Victor Porton 4 siblings, 0 replies; 10+ messages in thread From: Matthew Heaney @ 2002-11-14 16:04 UTC (permalink / raw) porton@ex-code.com (Victor Porton) wrote in message news:<3dd29387$0$303$bed64819@news.gradwell.net>... > Why in Charles.Vectors iterators are missing even despite it is > modelled after STL? Because iterators for vectors are too fragile. An unbounded vector automatically grows as necessary during insertions. This works by deallocating the existing internal array, reallocating a new (longer) array, and copying the existing elements onto the new array. The issue is that an iterator designates the old array, which gets deallocated. It's too easy for forget this fact, which means dangling references occur. The whole problem goes away by simply using the index subtype to refer to elements in the vector, instead of an iterator. Realize that the iterator exists in the STL because of the nature of template expansion in C++. In Ada, a separate iterator is not necessary because the generic actual subprogram only needs to match the signature of the generic formal, not its name (which is not the case in C++). Remember that Charles is *modelled* on the STL, but it is not a literal port of the STL. Charles is first and foremost an Ada library, and it takes advantage of specific features of the Ada language, specifically nested subprograms. > Iterators are good for many things, including reliability: Just the opposite. A vector iterator is very UNreliable. >Probability to mess iterators is > lesser than to mess natural number indexes because iterators are more > type-safe. Wrong for vectors. I don't know what would ever motivate you to think this, when iteration over a scalar range is so high level in Ada: for I in I_Subtype loop for J in J_Subtype loop ... This is hard to get wrong. > Please add these. Your suggestion is noted, and rejected. > BTW, may be put Chrles on SourceForge or something that if e.g. I will > want to submit a patch it would become simpler? You can get more immediate feedback by sending me email directly. CLA is probably not the most suitable forum for discussing Charles features. mheaney at on2 dot com ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-13 17:15 Charles: missing vector iterators Victor Porton ` (2 preceding siblings ...) 2002-11-14 16:04 ` Matthew Heaney @ 2002-11-15 7:10 ` Victor Porton 2002-11-15 9:36 ` Preben Randhol 2002-11-15 9:37 ` Preben Randhol 2002-11-15 7:27 ` Victor Porton 4 siblings, 2 replies; 10+ messages in thread From: Victor Porton @ 2002-11-15 7:10 UTC (permalink / raw) In article <slrnat7gbr.473.randhol+news@kiuk0152.chembio.ntnu.no>, Preben Randhol <randhol+news@pvv.org> writes: > Marc A. Criley wrote: >> You can't mess with I and J inside a loop like this. They're >> effectively constants as far as the enclosed statements are concerned. > > I think he meant writing : A (J,I) in stead of A (I,J)> I meant A(j) messed with A(i). ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-15 7:10 ` Victor Porton @ 2002-11-15 9:36 ` Preben Randhol 2002-11-15 9:37 ` Preben Randhol 1 sibling, 0 replies; 10+ messages in thread From: Preben Randhol @ 2002-11-15 9:36 UTC (permalink / raw) Victor Porton wrote: > I meant A(j) messed with A(i). Thought so. So they you rather call them Outer and Inner. Using i and j like this is considered error-prone. -- Preben Randhol ------------------------ http://www.pvv.org/~randhol/ -- �There are three things you can do to a woman. You can love her, suffer for her, or turn her into literature.� - Justine, by Lawrence Durrell ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-15 7:10 ` Victor Porton 2002-11-15 9:36 ` Preben Randhol @ 2002-11-15 9:37 ` Preben Randhol 1 sibling, 0 replies; 10+ messages in thread From: Preben Randhol @ 2002-11-15 9:37 UTC (permalink / raw) Victor Porton wrote: > I meant A(j) messed with A(i). Thought so. Call them Outer and Inner in stead. Using i and j like this is considered error-prone. -- Preben Randhol ------------------------ http://www.pvv.org/~randhol/ -- �There are three things you can do to a woman. You can love her, suffer for her, or turn her into literature.� - Justine, by Lawrence Durrell ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-13 17:15 Charles: missing vector iterators Victor Porton ` (3 preceding siblings ...) 2002-11-15 7:10 ` Victor Porton @ 2002-11-15 7:27 ` Victor Porton 2002-11-16 0:10 ` Matthew Heaney 4 siblings, 1 reply; 10+ messages in thread From: Victor Porton @ 2002-11-15 7:27 UTC (permalink / raw) In article <1ec946d1.0211140804.42621077@posting.google.com>, mheaney@on2.com (Matthew Heaney) writes: > porton@ex-code.com (Victor Porton) wrote in message news:<3dd29387$0$303$bed64819@news.gradwell.net>... >> Why in Charles.Vectors iterators are missing even despite it is >> modelled after STL? > > Because iterators for vectors are too fragile. > > An unbounded vector automatically grows as necessary during > insertions. This works by deallocating the existing internal array, > reallocating a new (longer) array, and copying the existing elements > onto the new array. > > The issue is that an iterator designates the old array, which gets > deallocated. It's too easy for forget this fact, which means dangling > references occur. type Iterator_Type is private; ... type Iterator_Type is record Contaner: Container_Access; Index: Index_Type; end record; It is probably space inefficient but otherwise good. With a good compiler we seemingly can even live without space inefficiency using my previously posted to c.l.a idea of per container instance iterators: type Iterator_Type(Contaner: Container_Access) is record Index: Index_Type; end record; Now we can introduce a space efficient Range_Type (if compiler well optimized records with discriminants for space): type Range_Type(Contaner: Container_Access) is record First, Last: Iterator_Type(Container); end record; With a good compiler (if these exist) here it will be optimized to keep only one value of Container_Access for Range_Type variables. Well, may be someday I will write my own containers library with features like this container-specific Range_Type. BTW, for conveniency ranges should be transfered not as two separate values, but as records with two components. > The whole problem goes away by simply using the index subtype to refer > to elements in the vector, instead of an iterator. [Skipped because we define the term "iterator" differently: I mean fat iterators (which can be dereferenced without supplying containers; while Matthew Heaney means "something based on pointers".] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Charles: missing vector iterators 2002-11-15 7:27 ` Victor Porton @ 2002-11-16 0:10 ` Matthew Heaney 0 siblings, 0 replies; 10+ messages in thread From: Matthew Heaney @ 2002-11-16 0:10 UTC (permalink / raw) porton@ex-code.com (Victor Porton) wrote in message news:<3dd4baae$0$304$bed64819@news.gradwell.net>... > > type Iterator_Type is > record > Contaner: Container_Access; > Index: Index_Type; > end record; > > It is probably space inefficient but otherwise good. Well that is the whole point. A vector iterator doesn't add any power to the abstraction, it merely changes the syntax of vector manipulation. It would be simple enough for a user to add an "iterator layer" on top of the existing vector, or add another package, e.g. with Charles.Vectors.Unbounded; generic with package Vector_Types is new Charles.Vectors.Unbounded (<>); package Generic_Vector_Iterators is type Iterator_Type is private; function First (V : Vector_Subtype) return Iterator_Type; ... end Generic_Vector_Iterators; > [Skipped because we define the term "iterator" differently: > I mean fat iterators (which can be dereferenced without > supplying containers; while Matthew Heaney means > "something based on pointers".] I use the term "fat" per the GNAT user's guide (or was it the reference manual?). It means whether the representation of the iterator object requires one pointer or two pointers. (In GNAT, an access type that designates an unconstrained array is by default implemented as a pair of pointers, hence the term "fat.") All iterators can always be dereferenced without also supplying a container. That's practically the meaning of "iterator." It's not clear why you think I meant otherwise. An early version of the library did in fact have vector iterators, implemented as: type Iterator_Type is record Elements : Element_Array_Access; Index : Index_Subtype'Base; end record; The problem with your implementation, like this: type Iterator_Type is record Container : Container_Access; Index : Index_Subtype'Base; end record; is that you either have to 1) pay a syntactic penalty to stay in safe RM territory; or 2) avoid the syntactic penalty by playing Chap13 tricks. In the first case, you would need to implement operations this way: function First (Container : access Container_Type) return Iterator_Type; and then declare vector container objects as aliased: Vector : aliased Vector_Subtype; ... Iterator : Iterator_Type := First (Vector'Access); This will cause further headaches if you only have a constant view of the vector, ie procedure Print (V : Vector_Subtype) is Iterator : Iterator_Type := First (V'Access); --won't compile begin There are ways around this, but they involve Chap13 tricks. In the second case, you have a similar problem: function First (Container : Container_Type) return Iterator_Type is Result : Iterator_Type; begin Result.Container := Container'Access; --won't compile To work around this you have to play the same Chap13 tricks. Note also that your implementation won't work with a swap. If I do this: V1 : Vector_Subtype; Iter : Iterator_Type := First (V1); V2 : Vector_Subtype; Swap (V1, V2); E := Element (Iter); This *should* return the element that was in V1, and is now in V2. (Iterators always designate elements, not containers.) But in your formulation Iter designates some element in V1. This is incorrect. This error is especially pernicious, because V1 and V2 may have different lengths and sizes, which means you'll end up deferencing garbage. I personally find it much simpler to implement the iterator as a pointer to the internal array, rather than the container. This works, but the problem is that that iterator is very fragile, and is very susceptable to dangling reference problems because of automatic reallocation. All of these problems go away if you simply don't have a vector iterator. You have random access, so just use an index, which does the job equally well. If this syntax offends you: E : Element_Type := Element (Vector, Iterator); then you can just write a local subprogram to take out the vector param: V : Vector_Subtype; ... function Element (Iterator : Iterator_Type) return Element_Type is begin return Element (V, Iterator); end; and now all is well. Your suggestion is noted, and rejected. ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2002-11-16 0:10 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2002-11-13 17:15 Charles: missing vector iterators Victor Porton 2002-11-14 9:22 ` Preben Randhol 2002-11-14 12:10 ` Marc A. Criley 2002-11-14 15:30 ` Preben Randhol 2002-11-14 16:04 ` Matthew Heaney 2002-11-15 7:10 ` Victor Porton 2002-11-15 9:36 ` Preben Randhol 2002-11-15 9:37 ` Preben Randhol 2002-11-15 7:27 ` Victor Porton 2002-11-16 0:10 ` Matthew Heaney
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox