lvalue/rvalue, non-const/const
Daniel Hempel
Hello,
I ran in a problem when declaring an index operator for sparse arrays ... :
Think about a class for arrays and especially a class for long arrays with
a lot of zeros in it (sparse array). There is a book-keeping mechanism in the
class for the non-zero entries. Thus you don't need and use memory for the
zeros.
Now we want to define the index operators for the sparse-array class and we will
get a problem:
---------------------------------------------------------------
double I_AM_ZERO = 0.0;
class SparseArray
{
public:
....
// const index-operator: (no-problem!)
double opertor [] (int i) const
{
return (entry_exists(i) ? data(i) : 0.0;
}
// non-const index-operator: (problem!)
double & operator [] (int i)
{
if(entry_exists(i))
return data(i); // no-problem
else // problem:
{
// code variante 1:
return 0.0; // error: const value will be returned when
// non-const reference is expected.
// code variante 2:
return I_AM_ZERO; // ok: But everybody may change the variable
// I_AM_ZERO.
// code variante 3:
cerr << "ERROR: Indexing is not possible!" << endl;
exit(EXIT_FAILURE); // Is this what we want to do?
}
}
};
int main()
{
SparseArray x;
...
double y;
y = x[i]; // x is not constant. Thus the non-constant index operator
// is used. Only "code variante 2" will do the right thing.
...
x[i] = 1.5; // Only "code variante 3" would be correct.
}
----------------------------------------------------------------
Comment: The problem is, that I am just able to differ between const and
non-const cases. What I would need here, is to differ between lvalue
and rvalue-cases, which is not the same.
Question: Is there an elegant way to do this in C++ ... or is it a
wrong design of the index operator.
Thank you for your time
Daniel Hempel
Institut f"ur Angewandte Mathematik
Universit"at Hamburg
Bundesstr. 55
20146 Hamburg
Germany
e-mail: dan...@math.uni-hamburg.de
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Wil Evers
Daniel Hempel <dan...@math.uni-hamburg.de> wrote in article
<5jfvq7$l...@netlab.cs.rpi.edu>...
> I ran in a problem when declaring an index operator for sparse arrays ...
:
[example compressed]
> class SparseArray
> {
> public:
> // const index-operator: (no-problem!)
> double opertor [] (int i) const
> {
> return (entry_exists(i) ? data(i) : 0.0;
> }
>
> // non-const index-operator: (problem!)
> double & operator [] (int i)
> {
> if(entry_exists(i))
> return data(i); // no-problem
> else // problem:
> }
> };
>
> The problem is, that I am just able to differ between const and
> non-const cases. What I would need here, is to differ between lvalue
> and rvalue-cases, which is not the same.
A common technique you could use here is to have the index operator return
a temporary object of a class carrying a pointer to the array and the index
to be used. The temporary has a conversion to double (use as rvalue) and
an assignment operator taking a double (use as lvalue):
class SparseArray;
class SparseArrayIndex {
SparseArray *s;
int i;
public :
SparseArrayIndex(SparseArray& sa, int index)
: s(&sa), i(index)
{ }
operator double() const; // use as rvalue
void operator=(double value) const; // use as lvalue
};
class SparseArray {
public :
double get(int i) const;
// returns value of element if it exists,
// 0.0 otherwise
void set(int i, double value);
// creates element if it does not exist,
// then assigns to it
double operator[](int i) const
{ return get(i); }
SparseArrayIndex operator[](int i)
{ return SparseArrayIndex(*this, i); }
};
inline SparseArrayIndex::operator double() const
{
return s->get(i);
}
inline void SparseArrayIndex::operator=(double value) const
{
s->set(i, value);
}
Because the member functions of SparseArrayIndex are all inline, an
optimizing compiler should be able to complete eliminate the temporary from
the generated code.
A word of warning, though: this technique is not without drawbacks. It
does not allow for in-place modification of the array's elements, which
implies that it does not scale well to cases where the elements are
themselves big objects with expensive copy operations.
More importantly, since the SparseArrayIndex class needs a (probably
implicitly defined) public copy constructor, there is no cheap way to
prevent access to elements in arrays that have gone out of scope.
- Wil
Marcelo Cantos
dan...@math.uni-hamburg.de (Daniel Hempel) writes:
> I ran in a problem when declaring an index operator for sparse arrays ... :
>
> Think about a class for arrays and especially a class for long arrays with
> a lot of zeros in it (sparse array). There is a book-keeping mechanism
in the
> class for the non-zero entries. Thus you don't need and use memory for the
> zeros.
Since the non-const operator[] could be used thus:
x[i] = 10.0;
it makes sense for it to add the element if it isn't found.
If you don't like this approach, then two options are available: throw
an exception, or replace the operator with a set member:
void operator set(int index, double value);
which could do whatever you want (even ignore it)!
--
______________________________________________________________________
Marcelo Cantos, Research Assistant __/_ mar...@mds.rmit.edu.au
Multimedia Database Systems Group, RMIT / _ Tel 61-3-9282-2497
723 Swanston St, Carlton VIC 3053 Aus/ralia ><_> Fax 61-3-9282-2490
Acknowledgements: errors - me; wisdom - God; funding - RMIT
Andy Philpotts
On 21 Apr 1997 11:07:26 -0400, dan...@math.uni-hamburg.de (Daniel
Hempel) wrote:
>Hello,
>
>I ran in a problem when declaring an index operator for sparse arrays ... :
>
>Think about a class for arrays and especially a class for long arrays with
>a lot of zeros in it (sparse array). There is a book-keeping mechanism in the
>class for the non-zero entries. Thus you don't need and use memory for the
>zeros.
[Example deleted]
>
>Comment: The problem is, that I am just able to differ between const and
>non-const cases. What I would need here, is to differ between lvalue
>and rvalue-cases, which is not the same.
>
>Question: Is there an elegant way to do this in C++ ... or is it a
>wrong design of the index operator.
>
There are many answers to this, and much depends on usage, but my
immediate reaction is that if a user of the class wants a non-const
ref to an unpopulated entry, you should allocate, then return that
instance, otherwise, why would they need it? Of course, if your class
cannot allow this you could consider raising an exception.
--
Andy P++ <xy...@pobox.com> http://www.pobox.com/~xyzzy
Robert DiFalco
:
: // non-const index-operator: (problem!)
: double & operator [] (int i)
: {
: if(entry_exists(i))
: return data(i); // no-problem
: else // problem:
: {
: // code variante 1:
: return 0.0; // error: const value will be returned when
: // non-const reference is expected.
:
: // code variante 2:
: return I_AM_ZERO; // ok: But everybody may change the variable
: // I_AM_ZERO.
:
: // code variante 3:
: cerr << "ERROR: Indexing is not possible!" << endl;
: exit(EXIT_FAILURE); // Is this what we want to do?
: }
: }
: };
:
: int main()
: {
: SparseArray x;
: ...
: double y;
: y = x[i]; // x is not constant. Thus the non-constant index operator
: // is used. Only "code variante 2" will do the right thing.
: ...
: x[i] = 1.5; // Only "code variante 3" would be correct.
: }
:
Why does it return zero if the element is not found? Is zero an illegal
value for some reason and therefore represents an error? If zero is a legal
value I don't see how you can arbitrarily deem to return zero to represent
an error. I mean, if zero is a legal value, semantically its the same as
returning 10 or 20 or some other legal value to indicate an error
condition. If it is not a legal value for an element than it makes more
sense to return but really, accessing a non-existent element is an error.
So, for me, the solution is simple, operator[] should raise either a
"range", "missing" or "invalid index" exception if the element at the
index does not exist. Its simple. It is illegal to return a modifiable
reference to a non-existent element. I mean no matter how you implement it
(even as a reference class such as used in bitset) at some level you are
going to get back to "how can I return a constant as a modifiable
reference." The answer is simply that you can't.
SparseArray a;
double d;
d = a[0]; // exception!
However, if it is your design intent to "create" an element if the element
does not exist, the solution is easy, add a new element and return a
reference to that element.
double& operator [] ( size_t n )
{
if ( n > Amplitude() )
throw XOverflow( "Index exceeds maximum capacity!" );
if ( n > Count() )
Resize( n ); // Make array big enough to return "n"
return At( n ); // Return reference to value At "n"
}
Hope this helps,
Alexandre Oliva
Robert DiFalco writes:
> Why does it return zero if the element is not found? Is zero an illegal
> value for some reason and therefore represents an error? If zero is a legal
> value I don't see how you can arbitrarily deem to return zero to represent
> an error.
I believe you should have read the problem before blaming the original
poster. In a sparse array, the intention is not to store elements
whose value is zero. That is, returning zero does not mean an error
occurred, it just means that no value was assigned to that element, so
it is still zero.
> However, if it is your design intent to "create" an element if the element
> does not exist, the solution is easy, add a new element and return a
> reference to that element.
The intent seems to be not to store any element whose value is zero,
so this won't work.
--
Alexandre Oliva
mailto:ol...@dcc.unicamp.br mailto:aol...@acm.org
Universidade Estadual de Campinas, SP, Brasil
James Kanze
"Wil Evers" <w...@ittpub.nl> writes:
|> Daniel Hempel <dan...@math.uni-hamburg.de> wrote in article
|> <5jfvq7$l...@netlab.cs.rpi.edu>...
|>
|> > I ran in a problem when declaring an index operator for sparse arrays ...
|> :
|>
|> [example compressed]
|>
|> > class SparseArray
|> > {
|> > public:
|> > // const index-operator: (no-problem!)
|> > double opertor [] (int i) const
|> > {
|> > return (entry_exists(i) ? data(i) : 0.0;
|> > }
|> >
|> > // non-const index-operator: (problem!)
|> > double & operator [] (int i)
|> > {
|> > if(entry_exists(i))
|> > return data(i); // no-problem
|> > else // problem:
|> > }
|> > };
|> >
|> > The problem is, that I am just able to differ between const and
|> > non-const cases. What I would need here, is to differ between lvalue
|> > and rvalue-cases, which is not the same.
|>
|> A common technique you could use here is to have the index operator return
|> a temporary object of a class carrying a pointer to the array and the index
|> to be used. The temporary has a conversion to double (use as rvalue) and
|> an assignment operator taking a double (use as lvalue):
This is the classical solution, well documented in "More Effective C++",
by Scott Meyers (Item 30), as well as in most other serious C++ books.
In the case of double, you probably will want to add operator+=,
operator-=, etc. A lot of extra typing, but no real extra complexity.
It's also worth noting that in the general case, this technique prevents
taking the address of "array[i]". You can define an operator& in the
proxy, but you must seriously consider what the behavior should be.
Practically, once the user has obtained a pointer to an element, that
element should probably remain locked, and neither moved nor removed
from the array.
--
James Kanze home: ka...@gabi-soft.fr +33 (0)1 39 55 85 62
office: ka...@vx.cit.alcatel.fr +33 (0)1 69 63 14 54
GABI Software, Sarl., 22 rue Jacques-Lemercier, F-78000 Versailles France
-- Conseils en informatique industrielle --
Robert DiFalco
:
: // non-const index-operator: (problem!)
: double & operator [] (int i)
: {
: if(entry_exists(i))
: return data(i); // no-problem
: else // problem:
: {
: // code variante 1:
: return 0.0; // error: const value will be returned when
: // non-const reference is expected.
:
: // code variante 2:
: return I_AM_ZERO; // ok: But everybody may change the
variable
: // I_AM_ZERO.
:
: // code variante 3:
: cerr << "ERROR: Indexing is not possible!" << endl;
: exit(EXIT_FAILURE); // Is this what we want to do?
: }
: }
: };
:
: int main()
: {
: SparseArray x;
: ...
: double y;
: y = x[i]; // x is not constant. Thus the non-constant index operator
: // is used. Only "code variante 2" will do the right
thing.
: ...
: x[i] = 1.5; // Only "code variante 3" would be correct.
: }
:
Why does it return zero if the element is not found? Is zero an illegal
value for some reason and therefore represents an error? If zero is a
legal
value I don't see how you can arbitrarily deem to return zero to
represent
an error. I mean, if zero is a legal value, semantically its the same as
returning 10 or 20 or some other legal value to indicate an error
condition. If it is not a legal value for an element than it makes more
sense to return but really, accessing a non-existent element is an
error.
So, for me, the solution is simple, operator[] should raise either a
"range", "missing" or "invalid index" exception if the element at the
index does not exist. Its simple. It is illegal to return a modifiable
reference to a non-existent element. I mean no matter how you implement
it
(even as a reference class such as used in bitset) at some level you are
going to get back to "how can I return a constant as a modifiable
reference." The answer is simply that you can't.
SparseArray a;
double d;
d = a[0]; // exception!
However, if it is your design intent to "create" an element if the
element
does not exist, the solution is easy, add a new element and return a
reference to that element.
double& operator [] ( size_t n )
{
if ( n > Amplitude() )
throw XOverflow( "Index exceeds maximum capacity!" );
if ( n > Count() )
Resize( n ); // Make array big enough to return "n"
return At( n ); // Return reference to value At "n"
}
Hope this helps,
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Alexandre Oliva
Daniel Hempel writes:
> I ran in a problem when declaring an index operator for sparse arrays ... :
> Think about a class for arrays and especially a class for long arrays with
> a lot of zeros in it (sparse array). There is a book-keeping mechanism in the
> class for the non-zero entries. Thus you don't need and use memory for the
> zeros.
The best way to cope with this problem is to return a proxy object
that can convert itself to a double, but will change the matrix if
assigned to:
class SparseArray::ProxyElement {
SparseArray& array;
int index;
bool initialized;
double value;
friend SparseArray;
ProxyElement(/*???*/); // only SparseArray should create ProxyElement
public:
operator double() const { if (initialized) return value; else return 0; }
ProxyElement& operator=(double); // left as exercise for the reader
};
OTOH, if you intend to keep things simple and don't care if you have
to explicitly insert non-zero elements, you may throw an exception if
the element was not explicitly initialized.
--
Alexandre Oliva
mailto:ol...@dcc.unicamp.br mailto:aol...@acm.org
Universidade Estadual de Campinas, SP, Brasil
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
jpo...@falcon.lhup.edu
On 21 Apr 1997 11:07:26 -0400, you wrote:
: Hello,
: I ran in a problem when declaring an index operator for sparse arrays ... :
: class SparseArray
: {
: public:
: ....
: // const index-operator: (no-problem!)
: double opertor [] (int i) const
: {
: return (entry_exists(i) ? data(i) : 0.0;
: }
:
: // non-const index-operator: (problem!)
: double & operator [] (int i)
DoubleReference operator [] (int i)
Where DoubleReference is a class that acts like a reference to double
and acts differently on the left and right. The three basic
requirements:
DoubleReference operator= (double) // lvalue stores
operator double () // rvalue returns value or zero
DoubleReference operator= (DoubleReference const& rhs) {
return *this = double(rhs);
}
See vector<bool> in the FCD or Scott Meyers More Effective C++ for all
the joys and troubles of proxies.
John
kjh...@mmm.com
Daniel Hempel wrote:
>
> Hello,
>
> I ran in a problem when declaring an index operator for sparse arrays ... :
>
> a lot of zeros in it (sparse array). There is a book-keeping mechanism in the
> class for the non-zero entries. Thus you don't need and use memory for the
> zeros.
>
> get a problem:
>
> ---------------------------------------------------------------
> double I_AM_ZERO = 0.0;
>
> {
> public:
> ....
>
> // const index-operator: (no-problem!)
> double opertor [] (int i) const
> {
> return (entry_exists(i) ? data(i) : 0.0;
> }
>
> // non-const index-operator: (problem!)
> double & operator [] (int i)
> if(entry_exists(i))
> return data(i); // no-problem
> else // problem:
> {
> // code variante 1:
> return 0.0; // error: const value will be returned when
> // non-const reference is expected.
>
> // code variante 2:
> return I_AM_ZERO; // ok: But everybody may change the variable
> // I_AM_ZERO.
>
> // code variante 3:
> cerr << "ERROR: Indexing is not possible!" << endl;
> exit(EXIT_FAILURE); // Is this what we want to do?
> }
> }
> };
>
> int main()
> {
> SparseArray x;
> ...
> double y;
> y = x[i]; // x is not constant. Thus the non-constant index operator
> // is used. Only "code variante 2" will do the right thing.
> ...
> x[i] = 1.5; // Only "code variante 3" would be correct.
> }
>
> Comment: The problem is, that I am just able to differ between const and
> non-const cases. What I would need here, is to differ between lvalue
> and rvalue-cases, which is not the same.
>
> wrong design of the index operator.
One way to do this is to return an intermediate object.
class ArrayRef
{
private:
friend class SparseArray;
SparseArray& m_array;
int m_index;
ArrayRef(SparseArray const& array, int index)
: m_array(array), m_index(index) { }
public:
~ArrayRef();
operator double() { return m_array.getData(m_index); }
void operator=(double x) { m_array.setData(m_index, x); }
};
And now a change to SparseArray:
class SparseArray
{
...
double operator[](int i) const { return getData(i); }
ArrayRef operator[](int i) { return ArrayRef(*this, i); }
double getData(int i) const { return entry_exists(i) ? data(i) : 0.0;
}
void setData(int i, double x) { whatever long code you need }
...
};
Now when the SparseArray is non-const, operator[] returns an ArrayRef
object. When the ArrayRef is an rvalue, it's operator double() is
called. When the ArrayRef is an lvalue, it calls
SparseArray::setData().
--
Kevin J. Hopps, Imation kjh...@imation.com
My opinions are my own. I speak neither for Imation nor 3M.
Brian S. Bearden
>I ran in a problem when declaring an index operator for sparse arrays ... :
>
>
> double & operator [] (int i)
> {
>
>non-const cases. What I would need here, is to differ between lvalue
>and rvalue-cases, which is not the same.
>Question: Is there an elegant way to do this in C++ ... or is it a
I am not sure if I would call my solution 'elegant', but I handle it by
using a 'hold' node. When a zero reference is returned it is to the value of
this hold node. The next time an operation is done, the hold node is inserted
into the list if it is non-zero, and then a new hold node is created. If it is
still zero, then nothing is done. It is a little convoluted to code, but not
too bad. Feel free to mail me if you would like the source code.
Robert DiFalco
:
: I believe you should have read the problem before blaming the original
: poster. In a sparse array, the intention is not to store elements
: whose value is zero. That is, returning zero does not mean an error
: occurred, it just means that no value was assigned to that element, so
: it is still zero.
:
I wasn't blaming, merely expressing my point of view. I didn't mean to make
anyone defensive. As for the meaning of zero, I believe I explained my
position in both cases.
:
: The intent seems to be not to store any element whose value is zero,
: so this won't work.
:
:
Then the proxy object solution I proposed (ala bitset) should work.
Robert
Brian Parker
jpo...@falcon.lhup.edu wrote:
>On 21 Apr 1997 11:07:26 -0400, you wrote:
>: Hello,
>: I ran in a problem when declaring an index operator for sparse arrays ... :
>: class SparseArray
>: {
>: public:
>: ....
>: // const index-operator: (no-problem!)
>: double opertor [] (int i) const
>: {
>: return (entry_exists(i) ? data(i) : 0.0;
>: }
>:
>: // non-const index-operator: (problem!)
>: double & operator [] (int i)
> DoubleReference operator [] (int i)
>Where DoubleReference is a class that acts like a reference to double
>and acts differently on the left and right. The three basic
>requirements:
> DoubleReference operator= (double) // lvalue stores
> operator double () // rvalue returns value or zero
> DoubleReference operator= (DoubleReference const& rhs) {
> return *this = double(rhs);
> }
>See vector<bool> in the FCD or Scott Meyers More Effective C++ for all
>the joys and troubles of proxies.
>John
One problem with the use of proxies that I have found that is not
discussed in "More Effective C++" is when they are used for templated
types e.g. for complex<double> instead of double in the above example.
In this scenario, when calling template functions that take complex<T>
(e.g. conj() et al) with a returned proxy, the proxy is not converted
to a complex<double> but instead a template argument deduction failure
results.
For this reason, I think that [temp.deduct] paragraph 4 in the CD2
should allow a user-defined conversion to be called when deducing
parameters of the form class-template-name<arguments> (or at least
specify that non-template specialisations of the global functions of
complex<T> for T == float, double, and long double are provided).
,Brian Parker (bpa...@gil.com.au)
Srinivas Vobilisetti
Marcelo Cantos wrote:
>
> dan...@math.uni-hamburg.de (Daniel Hempel) writes:
>
> > I ran in a problem when declaring an index operator for sparse arrays ... :
> >
> > a lot of zeros in it (sparse array). There is a book-keeping mechanism
> in the
> > class for the non-zero entries. Thus you don't need and use memory for the
> > zeros.
>
>
> x[i] = 10.0;
>
> it makes sense for it to add the element if it isn't found.
>
> If you don't like this approach, then two options are available: throw
> an exception, or replace the operator with a set member:
>
> void operator set(int index, double value);
>
> which could do whatever you want (even ignore it)!
>
Have a additional index and data fields in your SpareMatrix class. Here
is a skeleton implementation
class SpareMatrix {
private:
List list;
int index;
int data;
public:
....
int & SpareMatrix::operator [] (int);
....
};
int & SpareMatrix::operator [] (int i)
{
if(data != 0) {
insert index, data in the list of elements.
data = 0
}
if(entry found in the list)
return the info field //assuming list is a list of
pair(index,info)
}
index = i;
return data;