Topic: bitset operator[]


Author: AllanW@my-dejanews.com
Date: 1999/01/19
Raw View
In article <36A2B6CC.4108CE24@wizard.net>,
  James Kuyper <kuyper@wizard.net> wrote:
>
> Jonathan H Lundquist wrote:
> >
> > re:
> > bitset<N>::reference bitset<N>::operator[](size_t pos)
> >
> > Should this throw out_of_range for an invalid pos?  The standard is
> > strangely silent on the question.
>
> If you want checked access, use the set(pos,val) or test(pos) members,
> each of which throw out_of_range when passed an invalid value for pos.
> operator[] is for when you want the greater efficience of unchecked
> access.

I think the answer depends on whether Jonathan is asking as a language
user, or as a language (or library) implementor. For a language user,
your answer seems to be correct. To back this up, we have both prior
art and precedents for similar situations within the standard. For
instance, basic_string provides at(n), which throws out_of_range if
n>=size(), and operator[n], which is undefined if n>=size(). (Except
when the string is const and n==size(), in which case the operator
returns charT().) Since bitset provides test(n) and operator[n],
we can surmise that there is a parallel.

For a language implementor, the description above simply isn't
adequate. We have to consider both what the user will expect and
what the standard requires. (Fortunately these two things only
rarely conflict.) But the standard seems to have a defect! Look
at the fixed-font text in 23.3.5, before paragraph 1 and in
paragraph 1. These two areas list all the public members of class
bitset. Now loook at sections 23.3.5.3, 23.3.5.1, and 23.3.5.2 --
in that order. Every one of those public members are discussed
EXCEPT for operator[] and the nested class bitset<N>::reference!

[Not the best name, IMHO -- bitset<N>::reference is too similar
to bitset<N>& for my taste. It does NOt parallel
Allocator<T>::reference which at least is a reference to T.]

As Jonathan H Lundquist wrote, the standard is strangely silent,
not only on whether operator[] can throw an exception, but about
almost everything else about the operator. The text at 23.3.5 p1
clearly shows that operator[] is supposed to return a reference
object, but nothing is given about that object's state. Does the
reference object even HAVE a state, other than constructed or not?
The object has no data members (at least no public ones) and no
normative semantics, save for the tiny comments shown on
reference's operators:

    reference& operator=(bool x);             // for b[i] = x;
    reference& operator=(const reference&);   // for b[i] = b[j];
    bool operator~() const;                   // flips the bit
    operator bool() const;                    // for x = b[i];
    reference& flip();                        // for b[i].flip();

Consider code of the form:

    void x(bitset<32>&b) {
        bool notbit5 = ~(b[5]);
    }

Does calling this affect any of the bits in b? Probably not, but
you can't prove it. The only normative text about operator~ in
that setting is:
    "flips the bit"
which is vague at best. Flips what bit? In this case it flips bit
number 5 -- but does it flip a copy, or the original?

Also, the reference object is public. Does it make sense for user
code to construct a bitset<32>::reference object? There's nothing
in the standard to suggest that this is a bad idea; in fact, the
reference object even has a default constructor! (But no copy
constructor... hmmm...)

But at the beginning of section 23, there are some requirements
for all containers, right? The tables have lots of requirements that
apply to all containers and reversible containers. Table 68 (in
23.1.1) mentions operator[], including it's operational semantics.
Doesn't this apply to bitset as well?

Not by my reading. I would say that text in (hypothetical) section
99.5 would apply to 99.5.1 and 99.5.2, but not neccesarily to 99.6.
Further, the standard usually doesn't leave things like this to be
assumed, but states it explicitly. For instance, from the description
of deque<T> in 23.2.1 p2:

  2 A deque satisfies all of the requirements of a container and of a
    reversible container (given in tables in 23.1) and of a sequence,
    including the optional sequence requirements (23.1.1). Descriptions
    are provided here only for operations on deque that are not
    described in one of these tables or for operations where there is
    additional semantic information.

(There's an oxymoron: optional requirements?)

But there is no such paragraph in or near 23.3.5, nor in 23.3 ...

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]






Author: sbnaran@fermi.ceg.uiuc.edu (Siemel Naran)
Date: 1999/01/19
Raw View
On 19 Jan 1999 19:42:39 GMT, AllanW@my-dejanews.com

>I think the answer depends on whether Jonathan is asking as a language
>user, or as a language (or library) implementor. For a language user,
>your answer seems to be correct. To back this up, we have both prior
>art and precedents for similar situations within the standard. For
>instance, basic_string provides at(n), which throws out_of_range if
>n>=size(), and operator[n], which is undefined if n>=size(). (Except
>when the string is const and n==size(), in which case the operator
>returns charT().) Since bitset provides test(n) and operator[n],
>we can surmise that there is a parallel.

You've pointed out that string::operator[](size_type) is undefined
if size_type>size.  The same is said of valarray and builtin arrays.


Author: AllanW@my-dejanews.com
Date: 1999/01/21
Raw View
In article <slrn7a9r7t.e79.sbnaran@fermi.ceg.uiuc.edu>,
  sbnaran@KILL.uiuc.edu wrote:
> You've pointed out that string::operator[](size_type) is undefined
> if size_type>size.  The same is said of valarray and builtin arrays.
> From the fact that the behaviour is "undefined", it follows that the
> compiler may do anything, including anything reasonable.

Exactly. Which means that high-quality implementations may do
something if appropriate, but programmers must never assume
that it will do so.

> So a compiler could do runtime array bounds checking, at least when
> you compile in debugging mode.  This completely eliminates the need
> for the at() function.

Yes, but high-quality implementations should do so only in
debugging mode. There is at least a small overhead associated
with bounds checking; a programmer can expect that operator[]
won't pay this price for release builds.

> Besides, changing commands like "s.at(n)"
> to "s[N]" is very tedious, so rather the compiler do it automatically.
> I think that GHS does runtime arrays bound checking for builtin
> arrays when you compile in debug mode.

It is tedious; that's why, in my opinion, the programmer ought to
use the correct function in the correct place.

There are at least a few textbooks with example code such as this:

    template <class T>
    class CheckedVector : public std::vector<T> {
        // ... ctors omitted ...
    #ifdef BOUNDS_CHECK
        T&operator[](int i) { return (*this).at(i); }
        // Likewise for const
    #endif
    };

Personally, I think this is a reasonable way to explain derived
classes and code reuse, but a terrible way to deal with bounds
checking. Code should use at() when bounds checking is appropriate,
and operator[] when it isn't.

> Furthermore, if the compiler can detect an out of bounds violation
> at compile time, it can issue a warning, or possibly even an error.

I suspect that this case is relatively rare. Not only is the
index typically a variable (so difficult run-time analysis
might be needed to determine it's value), but the size of the
vector is often unknown and rarely constant.

> This runtime checking might be difficult for the implementor to
> implement, but it's possible, within the standard, and invaluable
> to language users.

Runtime bounds checking is trivial to implement, once you
decide WHAT you are going to do. at() must always verify the
range, and throw an exception if appropriate. operator[] never
NEEDS to verify the range, but it may do so. High quality C++
implementations should make operator[] as quick as possible in
release builds, but they ought to check the range for debug builds.

But what should operator[] DO if it finds an invalid range? It
shouldn't simply throw out_of_range, as at() would do; failing
an assert would be a much better choice. To see why, consider
that exceptions do not always indicate exceptions.

    // Returns index of item in vec.
    // Throws out_of_range if item is not in vec.
    template<class T>
    int myFind(vector<T>&vec, T item) throw(out_of_range) {
        for (int i=0; vec[i]!=item; ++i) // *** ERROR ***
            continue;
        return i;
    }

The programmer should have used vec.at(i) instead of vec[i]. If
debug builds have vec[i] throw out_of_range, then this program
works correctly on debug builds but fails on release builds.

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]





Author: "Jonathan H Lundquist" <fluxsmith@fluxsmith.com>
Date: 1999/01/21
Raw View
I was asking from the perspective of a library implementor.  My bitset class
is available at www.fluxsmith.com.  Based on input from this thread, my
decision was to use ASSERT if it is defined, and assume in-range (which will
lead to an access violation on derefence) otherwise.

I also added:
bool operator[](size_t pos) const throw();

If there is a reason this is not included in the standard, it escapes me.

I asked in another post whether my interpretation that the standard requires
the string passed to the string constructor to be checked beyond the
significant length used for initialization is correct.  I haven't had any
takers on that one yet ????

<AllanW@my-dejanews.com> wrote in message
news:782h6k$5gj$1@nnrp2.dejanews.com...
>
>I think the answer depends on whether Jonathan is asking as a language
>user, or as a language (or library) implementor. For a language user,
>your answer seems to be correct. To back this up, we have both prior
>art and precedents for similar situations within the standard. For
>instance, basic_string provides at(n), which throws out_of_range if
>n>=size(), and operator[n], which is undefined if n>=size(). (Except
>when the string is const and n==size(), in which case the operator
>returns charT().) Since bitset provides test(n) and operator[n],
>we can surmise that there is a parallel.



[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]






Author: sbnaran@localhost.localdomain.COM (Siemel Naran)
Date: 1999/01/21
Raw View
On 21 Jan 99 04:31:54 GMT, AllanW@my-dejanews.com
>  sbnaran@KILL.uiuc.edu wrote:

>> Furthermore, if the compiler can detect an out of bounds violation
>> at compile time, it can issue a warning, or possibly even an error.
>
>I suspect that this case is relatively rare. Not only is the
>index typically a variable (so difficult run-time analysis
>might be needed to determine it's value), but the size of the
>vector is often unknown and rarely constant.

It is conceivable for containers whose sizes are known at compile
time, such as builtin arrays, bitset<N>.  Eg,
   std::bitset<8> bits;
   for (int i=0; i<9; i++) { // warning possible
      bits[i]=true;
   }
It might not be worthwhile to implement this.


>The programmer should have used vec.at(i) instead of vec[i]. If
>debug builds have vec[i] throw out_of_range, then this program
>works correctly on debug builds but fails on release builds.

Good.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]






Author: fjh@cs.mu.OZ.AU (Fergus Henderson)
Date: 1999/01/21
Raw View
"Jonathan H Lundquist" <fluxsmith@fluxsmith.com> writes:

>I was asking from the perspective of a library implementor.  My bitset class
>is available at www.fluxsmith.com.  Based on input from this thread, my
>decision was to use ASSERT if it is defined, and assume in-range (which will
>lead to an access violation on derefence) otherwise.

Since this is comp.std.c++:

Beware that if one compilation unit defines the macro, and another
compilation unit doesn't, and both #include the conditional definition
of the `operator []' function, then the program violates the one
definition rule and so the behaviour is undefined.

In practice, the behaviour will typically be exactly what you would
expect, but this is not guaranteed by the standard.

--
Fergus Henderson <fjh@cs.mu.oz.au>  |  "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"
PGP: finger fjh@128.250.37.3        |     -- leaked Microsoft memo.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]





Author: AllanW@my-dejanews.com
Date: 1999/01/21
Raw View
In article <78537s$hpd$1@nnrp1.dejanews.com>,
  AllanW@my-dejanews.com wrote:
> But what should operator[] DO if it finds an invalid range? It
> shouldn't simply throw out_of_range, as at() would do; failing
> an assert would be a much better choice. To see why, consider
> that exceptions do not always indicate exceptions.

What I meant to say is, exceptions do not always indicate errors.
Please excuse the mistake.

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]





Author: James Kuyper <kuyper@wizard.net>
Date: 1999/01/18
Raw View
Jonathan H Lundquist wrote:
>
> re:
> bitset<N>::reference bitset<N>::operator[](size_t pos)
>
> Should this throw out_of_range for an invalid pos?  The standard is
> strangely silent on the question.

If you want checked access, use the set(pos,val) or test(pos) members,
each of which throw out_of_range when passed an invalid value for pos.
operator[] is for when you want the greater efficience of unchecked
access.


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]






Author: jshiva@bigfoot.com
Date: 1999/01/18
Raw View
In article <slrn7a3529.lim.sbnaran@localhost.localdomain>,
  sbnaran@uiuc.edu wrote:
> On 17 Jan 99 02:48:29 GMT, Jonathan H Lundquist <fluxsmith@fluxsmith.com>
wrote:
>
> >bitset<N>::reference bitset<N>::operator[](size_t pos)
> >
> >Should this throw out_of_range for an invalid pos?  The standard is
> >strangely silent on the question.
>
> My guess is NO, this should not throw an out_of_range.  This

Stroustrup in Section 14.10 & Section 17.5.3.2 says that it does throw an
out_of_range exception. i.e. the operator provides checked access.

cheers,
Shiva
comp.lang.c++ FAQ :http://www.cerfnet.com/~mpcline/c++-faq-lite/
http://members.xoom.com

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]






Author: "Jonathan H Lundquist" <fluxsmith@fluxsmith.com>
Date: 1999/01/17
Raw View
re:
bitset<N>::reference bitset<N>::operator[](size_t pos)

Should this throw out_of_range for an invalid pos?  The standard is
strangely silent on the question.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]





Author: sbnaran@localhost.localdomain (Siemel Naran)
Date: 1999/01/18
Raw View
On 17 Jan 99 02:48:29 GMT, Jonathan H Lundquist <fluxsmith@fluxsmith.com> wrote:

>bitset<N>::reference bitset<N>::operator[](size_t pos)
>
>Should this throw out_of_range for an invalid pos?  The standard is
>strangely silent on the question.

My guess is NO, this should not throw an out_of_range.  This
state of affairs is similiar to class std::vector<T>, where
vector<T>operator[](size_type) provides unchecked access and
vector<T>::at(size_type) provides checked access.  The intent
is that one uses the at(...) function while debugging, but
in the final version, one replaces the calls to at(...) with
calls to operator[](...).  This idea is important as it
eliminates the overhead of checked access once we know our
code is correct.

But class std::bitset<N> does not have an at(...) function.
But because of the efficiency argument above, I would
expect operator[] to do no checking.

But if the compiler can determine at compile time that you
access a std::bitset<N>, or even a fixed size array for that
matter, out of range, then it may issue a warning.  Possibly
the compiler may refuse to compile the program, although,
strictly speaking, this is probably non-conforming.

What I'm in favor of is this.  Allow the compiler to do run
time array bounds checking for container::operator[].
Incidentally, this eliminates the need for the at(...)
function.  Here's how implementors use the idea.  When
you compile the program with debugging or no optimization,
the compiler puts in the runtime checks into operator[].
When you compile with optimization, the compiler removes
the runtime checks in operator[].

These runtime checks seem to be conforming.  The standard
says that accessing a builtin array or a valarray out of
bounds is undefined.  This means that the implementation
can do anything it wants.  This includes anything
reasonable -- namely those runtime checks when compiling
in debug mode.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]





Author: Matt Austern <austern@sgi.com>
Date: 1999/01/18
Raw View
"Jonathan H Lundquist" <fluxsmith@fluxsmith.com> writes:

> re:
> bitset<N>::reference bitset<N>::operator[](size_t pos)
>
> Should this throw out_of_range for an invalid pos?  The standard is
> strangely silent on the question.

This is an open issue.  My own preferance, in analogy to vector<>,
deque<>, and string<>, where the at() member function performs range
checking and operator[] does not, is that bitset<>::operator[] should
not be required to throw an out_of_range exception.  But, as you say,
the standard does not give a definite answer.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]