 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
John Perks and Sarah Moun
Guest
|
 Posted: Mon Apr 18, 2005 5:48 pm Post subject: Precise requirements for STL container and iterator concepts |
 |
|
Are the definitive requirements for Container and Iterator concepts
available online without having to trawl through (and pay for) the
Standard itself? For instance, are those at http://www.sgi.com/tech/stl/
up-to-date and accurate? And, to complement that, is there a list of
gotchas that
occur in practice (subtly non-conforming compilers etc)?
The reason I ask is that I am investigating how much of the STL can be
brought to bear on objects "pointed to" by opaque handles (as the GC may
move them around in memory; compare managed vs unmanaged pointers in
..NET). For instance, an array iterator could be composed of a handle to
the GC-tracked array object, and an integer offset. As such I am
interested in determining which expressions:
(a) have to _act_ like real pointers and/or references (and to what
extent)
(b) be _convertible_ to ptrs or refs
(c) actually _be_ ptrs or refs.
to determine whether portable code can be written that models a
container type that does not visibly use ptrs and refs.
If this is not possible within the letter of the STL, what is the
rationale for this i.e. generalising the notion of pointers into
iterators, but inisting that some of their behaviour yield real pointers
after all? And is the notion of iterators due to be expanded (possibly
along the lines proposed by Boost) in C++0x?
Thanks
John
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
 |
kuyper@wizard.net
Guest
|
| Posted: Tue Apr 19, 2005 4:04 pm Post subject: Re: Precise requirements for STL container and iterator conc |
|
|
John Perks and Sarah Mount wrote:
| Quote: | Are the definitive requirements for Container and Iterator concepts
available online without having to trawl through (and pay for) the
Standard itself? For instance, are those at
http://www.sgi.com/tech/stl/
up-to-date and accurate?
|
No; that web page has a copyright date of 1994; the C++ standard that
was approved in 1998 contained the STL as an addition to the standard
library, but with significant modifications from the version described
on that web page. You're going to have to pay for it if you want the
real thing. You'll spend a lot more time reading the standard than you
will earning the money to pay for it.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
kuyper@wizard.net
Guest
|
| Posted: Wed Apr 20, 2005 6:46 am Post subject: Re: Precise requirements for STL container and iterator conc |
|
|
My first answer to your message, while correct, wasn't very responsive.
I'll try to address your concerns more directly.
John Perks and Sarah Mount wrote:
..
| Quote: | the GC-tracked array object, and an integer offset. As such I am
interested in determining which expressions:
(a) have to _act_ like real pointers and/or references (and to what
extent)
|
There's no answer to that which is signficantly shorter than the
complete set of iterator requirements. I won't attempt that.
However, the other two questions are more easily answerable. For the
purposes of the following answers, X is an iterator type, and T is its
value type. 'm' is a member of type T, and U is the type of m. 'n' is
an expression with the difference type of the iterator. Assume that the
following declarations are in scope and have been suitably initialized:
X a, u, &r;
| Quote: | (b) be _convertible_ to ptrs or refs
|
Output iterators:
r++ must be convertible to const X&
Bidirectional iterators:
r-- must be convertible to const X&
| Quote: | (c) actually _be_ ptrs or refs.
|
Input Iterators:
u=a must have the type X&
++r must have the type X&
Forward Iterators:
*a must have type T&
a->m must have type U&
*r++ must have type T&
Bidirectional Iterators:
--r must have type X&
Random Access Iterators:
r+=n and r-=n must both have type X&
Allocators:
reference is required to be T&
const_reference is required to be T const&
According to 20.1.4p5, std::Container<T,Allocator is permitted to
be implemented in such a way that it assumes that Allocator<T>::pointer
is "T*:", and Allocator<T>::const_pointer is "const T*". In paragraph 6
the standard encourages Implementors to implement standard containers
in ways that don't depend upon that assumption, but portable code can't
count on that.
Indirectly, this means that std::Container<T,Allocator::pointer
and const_pointer are also required to be T* and const T*,
respectively.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Beman Dawes
Guest
|
| Posted: Wed Apr 20, 2005 10:49 pm Post subject: Re: Precise requirements for STL container and iterator conc |
|
|
"John Perks and Sarah Mount" <johnandsarah (AT) estragon (DOT) freeserve.co.uk> wrote
in message news:d3rpml$l53$1 (AT) newsg1 (DOT) svr.pol.co.uk...
| Quote: |
... And is the notion of iterators due to be expanded (possibly
along the lines proposed by Boost) in C++0x?
|
Possibly. Iterator improvements along the lines proposed by the Boost folks
are high priority on the LWG's task list. But it is difficult to improve
iterator categorization while maintaining backward compatibility, and to do
so without adding a great deal of complexity.
--Beman
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Gabriel Dos Reis
Guest
|
| Posted: Sat Apr 23, 2005 1:20 am Post subject: Re: Precise requirements for STL container and iterator conc |
|
|
[email]kuyper (AT) wizard (DOT) net[/email] writes:
| Quote: | X a, u, &r;
(b) be _convertible_ to ptrs or refs
Output iterators:
r++ must be convertible to const X&
Bidirectional iterators:
r-- must be convertible to const X&
(c) actually _be_ ptrs or refs.
Input Iterators:
u=a must have the type X&
++r must have the type X&
|
Expressing the requirements in terms of types is an interesting
exercise, as it is full of traps. Odd enough, the standard library
itself got profoundly into those traps. Expressions in C++ do not
have reference types. They may be lvalues of type T (object or
function types), under no circumstances do they have reference types.
--
Gabriel Dos Reis
[email]gdr (AT) cs (DOT) tamu.edu[/email]
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
John Nagle
Guest
|
| Posted: Mon Apr 25, 2005 3:17 pm Post subject: Re: Precise requirements for STL container and iterator conc |
|
|
Gabriel Dos Reis wrote:
| Quote: | kuyper (AT) wizard (DOT) net writes:
|
"r++ must be convertible to const X&"
Always?
Consider
vector<int> tab;
tab.push_back(1); // tab now has one entry
vector<int>::iterator r = tab.begin();
r++; // r is now equal to tab.end();
const int& n = *r; // undefined behavior?
John Nagle
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Gabriel Dos Reis
Guest
|
| Posted: Tue Apr 26, 2005 8:54 pm Post subject: Re: Precise requirements for STL container and iterator conc |
|
|
[email]nagle (AT) animats (DOT) com[/email] (John Nagle) writes:
| Quote: | Gabriel Dos Reis wrote:
[email]kuyper (AT) wizard (DOT) net[/email] writes:
"r++ must be convertible to const X&"
Always?
Consider
vector<int> tab;
tab.push_back(1); // tab now has one entry
vector<int>::iterator r = tab.begin();
r++; // r is now equal to tab.end();
const int& n = *r; // undefined behavior?
John Nagle
|
I do not understand the relation between your quote and the code
snippet you gave.
--
Gabriel Dos Reis
[email]gdr (AT) cs (DOT) tamu.edu[/email]
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
kuyper@wizard.net
Guest
|
| Posted: Tue Apr 26, 2005 9:58 pm Post subject: Re: Precise requirements for STL container and iterator conc |
|
|
John Nagle wrote:
| Quote: | Gabriel Dos Reis wrote:
[email]kuyper (AT) wizard (DOT) net[/email] writes:
"r++ must be convertible to const X&"
Always?
Consider
vector<int> tab;
tab.push_back(1); // tab now has one entry
vector<int>::iterator r = tab.begin();
r++; // r is now equal to tab.end();
const int& n = *r; // undefined behavior?
|
Yes, that line has undefined behavior. It also has nothing to do with
what I was saying.
In table 73 of the standard, X is the iterator type itself, not the
value type of the iterator. And it's the value of r++ that must be
convertible to const X&, not the value of *r after r++ is completed. To
test this requirement, replace that last two lines our your code
fragment with:
const vector<int>::iterator &q = r++;
// At this point q == tab.begin() and r == tab.end()
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
