operator overloading

[pozdrav]

Hi,
I am writing a "vector" class. I know about the STL but I prefer to use this as I use this to create a "matrix" class later. I read that using the inbuilt STL to create a matrix is not the best way to do it.

At the moment, the class "vec" looks like this.

template <class T>
class vec {
private:
	int length;
	T *v;
public:
	vec();
	explicit vec(int n);
	vec(const T &a, int n);
	vec(const T *a, int n);
	vec(const vec &cpy);
	vec & operator=(const vec &equate);
	vec & operator=(const T &a);
	inline T & operator[](const int i);
	inline const T & operator[](const int i) const;
	inline int size() const;
	~vec();
};

Now, I want to overload the operator == in this way. It should accept a value (type T) say "val", and check through all the entries of this vector say "v1" and return another vector of type bool, which has "false" where v1 != val and "true" where v1 == val. I managed to write it this way...

member function:

vec<bool> operator==(const T &a) const;

the code definition is:

template <class T>
vec<bool> operator==(const T &a) const {
    vec<bool> tmp(false,length);
    for(int i=0; i<length; i++) {
        if(v[i] == a) {
            tmp[i] = true;
        }
    }
    return tmp;
}

This works great, but I would like to return the reference instead of the whole vector and would like to know how to do it. I am unable to make use of the "this" pointer as I am returning a "local vector". I would appreciate any help with this. thank you!

[firedraco]

IMO, making operator == return a vec is really strange...it kind of goes against what it should do (unless your vec<bool> is convertible to bool or something).

Anyway, you can't, since you are making a new vector. The closest thing you could do is return a pointer to it, but I would think that would just create a random layer of indirection (plus making the user have to delete a pointer later).

[Disch]

This works great, but I would like to return the reference instead of the whole vector and would like to know how to do it. I am unable to make use of the "this" pointer as I am returning a "local vector". I would appreciate any help with this. thank you!

The only way would be to extend the lifetime of the local variable. There is no good way to do that.

Here are 3 options. Note again that all of these options suck:

1) Make 'tmp' static. (Bad because it doesn't play nice if you are doing multiple comparisons)

2) Allocate 'tmp' with new. (Bad because it requires the calling function to delete it)

3) Make 'tmp' a member var. (Bad because it inflates the size of the class and doesn't play nice if you are doing multiple comparisons)


You're better off returning a copy.

The thing is -- copying generally shouldn't copy the entire vector. classes like this typically share a buffer between multiple instances and have a reference count, and copy-on-write behavior.

I'd explain in more detail but I have to get ready for work!

+ what firedraco said about this being very strange and unintuitive

[Onanymous]

I think it is OK to return the vector itself, good compiler should be able to eliminate all unnecessary temporaries.
What is wrong with returning vector from == ? I do think it is very natural if you compare vector to scalar value, and maybe even for vector to vector comparison.

Disch could you elaborate on use of the buffer and reference count please?

[Zhuge]

Because people expect the == operator to be a boolean operator that compares the vectors, not a "element-wise" equality operator.

[firedraco]

Onaymous wrote:

I do think it is very natural if you compare vector to scalar value,

Why/how would you do that? myVec == 2 makes no sense to me.

Onaymous wrote:

maybe even for vector to vector comparison.

This makes sense, but it should be returning a bool like Zhuge said.

[pozdrav]

Hi,
I understand the ambiguity in using == operator for a non-boolean type return purposes. My idea was to implement a library quite similar to Matlab with many utility functions. For example, if you have a vector A = [1,4,3,1,1] and would like to find the index of all 1's in A, then idx = find(A==1) will do.
The way I see it, creating a ptr to this object seems to be the only way out and probably to reduce the complexity for the user to deallocate every time I could create something like that of a "Smart pointer". But I see the ambiguity in implementing == in this manner in C++, out of its purpose. I will restrain using it this way and try something else, unless I find an agreeable and unambiguous way.

thank you.

[Disch]

Disch could you elaborate on use of the buffer and reference count please?

The idea is you have a "data" object that your "vector" uses. Multiple vectors can use the same data object, and therefore you can "copy" vectors without having to actually copy all of the data (they can just share the same pointer).

Of course with this setup, when one of the vectors changes the data, all vectors sharing it will see the change. Obviously this is undesirable, so that's where the "copy on write" idea comes in:

- A vector is about to change its data
- But that vector is sharing its data
- therefore it copies the data to a new 'data' object before writing
- now the shared data is not changed.


It might go a little something like this (note this is simplistic and may not be the best way to implement it):

template <typename T>
struct vecdata<T>
{
  unsigned refcount;  // the number of vec's using this data
  T* buf;   // the actual buffer
  unsigned size;  // the size of the buffer
  // any other 'vec' members here
};

template <typename T>
class vec
{
private:
  vecdata<T>* dat;  // the data

public:
  vec()  // default ctor
    : dat(new vecdata<T>)
  {
     dat->buf = whatever;
     dat->size = whatever;
     dat->refcount = 1;   // only 1 object referencing this data
  }

  vec(const vec& r)  // copy ctor
    : dat( r.dat )     // just take that object's data
  {
    ++dat->refcount;  // increment the ref count
    // copying is now quick.  No need to copy all of the data
  }

  ~vec()  // dtor
  {
    --dat->refcount;  // decrease the ref count
    if( dat->refcount == 0 )  // if no more objects are using this data
    {
      delete[] dat->buf;  // then clean it up
      delete dat;
    }
  }

  void AFunctionThatIsAboutToChangeTheData()
  {
    vecdata<T>* d = dat;  // the data we will be changing
    if(d->refcount > 1)  // is more than one object using it?
    {
       --d->refcount;  // seperate this object
       d = CopyData(dat);  // actually copy the data (expensive copy of the entire buffer and all memebers)
       d->refcount = 1;  // now this is the only vec using this data
    }

    d->buf[ whatever ] = whatever;  // now we can modify the data
  }
};

[imi]

I have another suggestion for the OP. You seem to want to write some kind of matlab program. And you seem to be concern about the speed of copying vectors. From this, I am making the following assumption about your later usage of vector. If they are wrong, then the rest of the text may hardly or not at all apply to your problem:

1) You are creating rather big vectors. Means not only like 3-elements (3D-Vector), but a vector with dozends of elements.
2) You are usually combining the vectors together, e.g. adding vectors to other vectors, scaling vectors by a scalar etc. instead of setting the elements directly all over the place.

If so, you could consider postponing the creation of the vector's values even more until you actually read the values. Let me explain..

Usually you create a vector by using some default memory for each cell, right? In your original synopsis, explicit vec(int n); probably creates a vector of n elements, each of it beeing 0. But at this point, there is no real need to create a memory block all filled with 0. You could just remember "I have a vector of size n with all zeroes."

Then later you work with the vector. You may add two vectors together, using some "v3 = v1 + v2". But even here, it may be much faster and much less memory consuming, if you just remember "the resulting vector v3 is an addition of v1 and v2 vector" instead of every single value.

Only if you read out a single element, you have to calculate the value of said element. Even then, you don't have to allocate memory for that. You remembered the "chain of operations" for this vector, so you just execute this chain for the requested memory cell.

The downside is, that now each "single element write access" operation need to be stored as an additional chain link.

It will look along those lines

struct Operation { virtual ~Operation(){} virtual int execute(int index, int current) = 0; };
struct SetPos : Operation // for setting a specific position only
{
    int constant, index;
    SetPos(int c, int i):constant(c), index(i) {}
    virtual int execute(int index, int current) { return i == index ? constant : current; }
};
struct Transpose : Operation // adding two vectors is called "transpose"
{
    vec<int> v;
    Transpose(const vec<int>& rhs):v(rhs){}
    virtual int execute(int index, int current) { return current + v[index]; }
};
struct Scale : Operation // scaling by a scalar
{
    int scale;
    Scale(int s):scale(s){}
    virtual int execute(int index, int current) { return current * scale; }
};
... // usually you'll end up in one operation per operator in your command line shell you have

struct vec
{
    std::list<std::tr1::shared_ptr<Operation>> operations;
    int size;
    vec(int n) : size(n) {} // no memory allocation here!
    vec(const vec& rhs) : operations(rhs.operations), size(rhs.size) {} // sharing operations

    int operator[](int index) const // element read access
    {
        int v = 0; // initial value is 0
        for (auto it = operations.begin(); it != operations.end(); ++it)
            v = (*it)->execute(index, v);
        return v;
    }
};
vec operator+(vec lhs, const vec& rhs)
{
    lhs.operations.push_back(std::tr1::shared_ptr<Operation>(new Transpose(rhs)));
    return lhs;
}

I only picture the idea for int's here and also was a bit sloppy with the interfaces (no private etc..). E.g. you should make sure your operation are immutable. (you only add operations and never change them).


Depending on the usage pattern of your vector class, this will decrease your memory consumption to a tiny fraction (if you have my 1) and 2) as typical operations) or just bloat up your PC (if you usually use for-loops to set every value step-by-step).

But especially for command line mathlab-similar tools where you don't set too many values anyway but usualy work with generated data, this technique can be skyrocking awesome. ;-)


Ciao, Imi.

PS: About your original question "how to not return a full copy": As Disch said, better forget about it. ;) Scott Meyer has an excellent chapter about this in "Effective C++" (or "More Effective C++". Don't remember), and he is right. It's more pain than worth it.
PPS: Disch: you may to rethink line 48 of your code and where this->dat is (still) pointing. ;-)

[jsmith]

The drawback is that now every matrix operation, no matter how simple, becomes a virtual function call.

I think where you are going is essentially expression templates, which is a really advanced template programming
topic, but would avoid the virtual function calls. (Though all expression templates are going to buy you is elimination
of temporaries while evaluating expressions containing more than one operation, ie, result = m1 + m2 + m3;
would normally result in at least one temporary (m1 + m2), possibly two. With expression templates, you could
avoid the interim temporaries).

[pozdrav]

I would rather put it this way. Lets say you create a vector class (or the inbuilt vector), how would you go about to find if a single value is present in this vector and if required return all indices of this vector where it equals to the value?


@imi,
thank you for your suggestions. Maybe I will have to first read more before trying. However you got my intentions right. I would like to create a vector/matrix class sophisticated to handle functions as similar as possible to Matlab, as I illustrated in the earlier post. I am interested in implementing most required utility functions (at least for me) such as find, unique, ismember, etc...

[jsmith]

Why not just return a vector of indices that match? (As opposed to a vector of bools).

The biggest concern was in use of operator== for this operation. operator== for vectors, maps, sets, strings,
etc, all return bool, just as operator== for all POD types does. Why should yours be different? That will just
confuse programmers; they will "expect" that operator== for a matrix returns a single true/false.

[pozdrav]

Hi,
Yes, that is absolutely right. I understand the confusion and that is why I don't want to use it. Returning the vector is absolutely possible. However, again what I would like to ask is to return the reference to the vector and not the vector itself. Because, I will have to do the same for matrices and the matrices I deal with in my problem are quite large in general and I don't want to return the whole matrix.

[jsmith]

I'm not sure you're going to be able to get around that in a useful/sane way.

How big are we talking?

[pozdrav]

As of now, the biggest matrix size is 1360 * 1140. But I am pretty sure its going to get bigger!

[jsmith]

Thinking about this a little more....

Any way you slice it, you need memory for potentially 1360 * 1140 "answers". If you're going
to implement the method at all, you might at well allocate another matrix and return it. The
alternatives have already been mentioned ... statics ... but those present a more difficult
programming model for the user of your library.

But, I'm wondering if this method is at all useful to the programmer. If you somehow return
a matrix, it is no easier for the user to manipulate the return value than it is to write the
find method him/herself.

[imi]

jsmith wrote:

The drawback is that now every matrix operation, no matter how simple, becomes a virtual function call.

Well, except of read access to not used fields, but that's rather an accident.

But in general you are right: One virtual call per operation and per element access. If you have many operations and few data, then you loose with this pattern. But if you have.. like.. five operations, five million data items and are printing out only five result elements, the virtual call becomes completely irrelevant.

Hm.. thinking of it, having the operations in a dynamically extensible class hierarchy may have other advantages later, going all way down to "plugin dll's with additional commands".

Any way you slice it, you need memory for potentially 1360 * 1140 "answers". ... The alternatives have already been mentioned ... statics

Or the "expression templates" (although I try to avoid this term as I found it usually starts more confusion about the "template" part.). No per-value memory allocation here.


Ciao, Imi.

[pozdrav]

jsmith wrote:

But, I'm wondering if this method is at all useful to the programmer. If you somehow return
a matrix, it is no easier for the user to manipulate the return value than it is to write the
find method him/herself.

I don't understand what you mean by "no easier to manipulate the return value". The user just does this:

// v1 = [1,2,3,1,1,1,4] say...
v2 = v1.find(1);
// now v2 = [1,4,5,6] the positions where v1 == 1. 

Now, what is the difficulty in manipulating the result in v2? I really don't understand. I am not demanding my method is the most efficient, I know it is not. I am rather asking which one is. But seemingly, there is none! I refuse to believe that a useful mathematical library (at least the ones I need) can not be efficiently implemented at all in C++ under the impression that the user could implement it with the same level of difficulty.

imi wrote:

Or the "expression templates" (although I try to avoid this term as I found it usually starts more confusion about the "template" part.). No per-value memory allocation here.

Thank you, I have not had the necessity to use or learn them yet. I will look into it to see if its useful.

[jsmith]

Here's my point, illustrated with three examples:

// Assume we have a vec<> already filled out:
vec<int> v;  // initialized with some values.

// Example 1.
for( int i = 0; i < v.size(); ++i )
    if( v[ i ] == 42 )
        std::cout << "42 found at position " << i << std::endl;

// Example 2, using vec<bool>:
vec<bool> find42 = v.find( 42 );
for( int i = 0; i < find42.size(); ++i )
    if( find42[ i ] == true )
        std::cout << "42 found at position " << i << std::endl;

// Example 3, using vec<int>, where only matching indices are returned
vec<int> find42 = v.find( 42 );
for( int i = 0; i < find42.size(); ++i )
    std::cout << "42 found at position " << i << std::endl;

Method #1 for you is "do nothing". From your user's point of view, method #2
is harder than method #1, simply because the logic is effectively the same
but there is an extra function call. Method #3, IMHO, is only slightly better than
method #1 because from the user's standpoint, it removes an if() check. BUT,
it does so at the cost of creating another data structure (ie, another vec<int>).
Does the increased usability outweigh the runtime penalty? That's a hard question
to answer because you're talking about a data structure that is megabytes in size.

What's your opinion?

[pozdrav]

Hi jsmith,

Your arguments are totally valid. I just have to add 3 things to it to ease the confusion.
1) vec<bool> as I understand it is not conventional C++ programming and would result only in confusion. However, in many mathematical applications, this IS a desired result. However, I can obtain the result without the confusing use of == operator.
2) v.find(int n) may not seem so obvious as an useful function. May be, if you were to write the same for-loop so many times or find elements of a matrix instead of vector or have the indices stored instead of just printing them, this becomes more obvious, which is the case in most of my projects. So, I wouldn't want to argue on the absolute importance of this function. I would rather focus on the raw question, returning not an object but a reference.
3) In Bjarne Stroustrup C++ programming language chapter 22 (22.4.7), he explains about writing the expression U = M*V + W (M is a matrix, V and W are vectors) efficiently without returning by value. I will write it here for convenience.First he creates 2 auxiliary classes to take care of M*V and (X + W) as,
The first auxiliary class:

struct MVmul {
    const Matrix&m;
    const Vector&v; 
    MVmul(const Matrix&mm,const Vector&vv):m(mm),v(vv){} 
    operator Vector(); // evaluate and return result
};
inline MVmul operator*(const Matrix&mm,const Vector&vv) {
}
return MVmul(mm,vv);

The second auxiliary class:

struct MVmulVadd{ 
    const Matrix&m;
    const Vector&v; 
    const Vector&v2;
    MVmulVadd(const MVmul&mv,const Vector&vv):m(mv.m),v(mv.v),v2(vv){} 
    operator Vector(); // evaluate and return result
};

inline MVmulVadd operator+(const MVmul&mv,const Vector&vv) {
    return MVmulVadd(mv,vv);
}

Now we define the class Vector as,

class Vector{ 
    // ...
    public: 
    Vector(const MVmulVadd& m) { // initialize by result of m
        // allocate elements, etc. 
        mul_add_and_assign(this,&m.m,&m.v,&m.v2);
    }
    Vector& operator=(const MVmulVadd& m) { // assign the result of m to *this
        mul_add_and_assign(this,&m.m,&m.v,&m.v2); 
        return *this;
    } 
    //...
};

He claims that, U=M*V+W is automatically expanded to U.operator=(MVmulVadd(MVmul(M,V),W)) which because of inlining resolves to the desired simple call mul_add_and_assign(&U,&M,&V,&W). Here I don't understand what is operator Vector(); syntax in the first 2 auxiliary classes. And the other problem is that instead of the RHS being an expression with operators * and +, I have a find(v1, 1) function.

Is anyone able to see a way of employing a similar way to implement find to return the reference by creating say an auxiliary find class? I have been reading this and trying on this for a while now!

thank you.