Matrix element access

This is a discussion on Matrix element access within the C++ Programming forums, part of the General Programming Boards category; Hello everyone Lately I've developing a MATRIX class. It went fine (mostly), but now I'm working on a SPARSE MATRIX. ...

  1. #1
    Registered User nepper271's Avatar
    Join Date
    Jan 2008
    Location
    Brazil
    Posts
    50

    Matrix element access

    Hello everyone

    Lately I've developing a MATRIX class. It went fine (mostly), but now I'm working on a SPARSE MATRIX. (Those unfamiliar with sparse matrix, check the end for a quick explanation). My problem is the following:
    When accessing element i,j of the matrix, the user should call something like A(i,j), i.e.

    Code:
    cout << A(i,j);
    Also, the user could like to change the value of the element i,j, so he would call

    Code:
    A(i,j) = 2;
    The point is, in the first use, I can return the element itself and in the second I would have to return the reference to the element, so the user could change it.
    So I wrote the code:

    Code:
    double & MATRIX::operator () (int x, int y)
    {
      return (val[(x - 1) * n_col + y - 1]); //matrix is stored using linearization strategy
    }
    
    double MATRIX::operator () (int x, int y) const
    {
      return (val[(x - 1) * n_col + y - 1]);
    }
    I found out only now that the second function was never called. But in the case of the MATRIX, it meant nothing, for everything worked fine.
    But in the case of the SPARSE matrix, my functions had to change a little. It became something like

    Code:
    double & SPARSE::operator () (int x, int y)
    {
      //...
      //Search for the element, if found return it, if not, create the element and pass the reference
      CREATE (0.0, x, y, k);
      return *(val.begin () + k);
    }
    
    double SPARSE::operator () (int x, int y) const
    {
      //...
      //Search for the element, if found return it, if not, create the element and pass the reference
      return 0.0;
    }
    Details have been hid to help visualization. As you can see, I must create a zero element and pass reference to it so the user can change (and I hope the user don't pass another 0.0). The mess here is that anytime it access an element to read, it creates a zero valued element in the matrix and stores it, and that what's wrong.

    If anyone can give me a tip on how to use the same function operator() to both tasks, I would be very happy. And if it's not possible, I would be happy to know that as well, thank you very much.

    Nepper271.

    SPARSE MATRIX

    A matrix is said to be sparse if there are many zero elements in it, in fact, many more zeros than non-zeros. As this kind of matrix appears widely on various applications, it's fundamental to research better ways to deal with it. The first thing to consider is that storing all the elements of the matrix is not useful. You store only the non-zero elementos of the matrix and the position they are held. For instance, the matrix

    Code:
    M =
    7 0 0
    0 0 8
    0 9 0
    could be stored as

    Code:
    val = 7 8 9
    lin = 1 2 3
    col = 1 3 2
    That's all for now

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    For such purposes you need two versions, const and non-const but both would return a reference.

    Code:
    double & SPARSE::operator () (int x, int y) {}
    const double & SPARSE::operator () (int x, int y) const {}
    One would be used for non-constant objects (both reading and writing), the other for constant objects (read-only access).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User nepper271's Avatar
    Join Date
    Jan 2008
    Location
    Brazil
    Posts
    50
    No, it still doesn't work. He still makes the call to the first one.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,593
    No, it still doesn't work. He still makes the call to the first one.
    The overloaded const version will only be called if the object itself is const (or used in a context where it is immutable).

    The mess here is that anytime it access an element to read, it creates a zero valued element in the matrix and stores it, and that what's wrong.
    Basically, you have to fix it such that the matrix does not store elements unless they are supposed to be stored.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Perhaps returning a reference to a proxy object is the right thing here, where the proxy object contains some information to indicate where it belongs?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User nepper271's Avatar
    Join Date
    Jan 2008
    Location
    Brazil
    Posts
    50
    Quote Originally Posted by laserlight View Post
    Basically, you have to fix it such that the matrix does not store elements unless they are supposed to be stored.
    I must create a space in the vector that stores the elements of the matrix to pass it to the user, so I create one that will simply waste space if the user do something funny like setting it to zero. The elements must be ordered following the matrix rows, so I can't simply push_back it either.

    Quote Originally Posted by matsp View Post
    Perhaps returning a reference to a proxy object is the right thing here, where the proxy object contains some information to indicate where it belongs?
    I'm sorry, I didn't understand what you meant. What is a proxy object?

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    A proxy object is an object that "takes the place of the real object", such that you could return a reference to the object and when it's being written, it updates the actual cell location. I'm not sure exactly how you would use that here.

    The other option is to simply scan [when you do math on the array perhaps] for zero's and remove them...

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I can't think of a way to force the compiler use a different overload based on on which side of assignment the function is called. What you are attempting is overloading only based on return type (the const-ness of the second version doesn't help you, since you are calling the method on a non-const object) and there is no such thing.

    May-be you could use a different function for read-only access that doesn't add elements to the array?

    Returning 0 might not be good for a general-purpose container, because someone might want to store 0-s in it. If it is a precondition of the read-only function that the index is valid, perhaps use assert.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    Registered User nepper271's Avatar
    Join Date
    Jan 2008
    Location
    Brazil
    Posts
    50
    Quote Originally Posted by matsp View Post
    The other option is to simply scan [when you do math on the array perhaps] for zero's and remove them...
    That was though about it at first, but it would slow things down a bit (every operation would need an additional comparison). My other option, which is what I'm doing now, and will keep if have no other choice, is use A.get(...) and A.set() instead. This way I can check whether the number is zero or not.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,593
    I must create a space in the vector that stores the elements of the matrix to pass it to the user, so I create one that will simply waste space if the user do something funny like setting it to zero. The elements must be ordered following the matrix rows, so I can't simply push_back it either.
    I think it is pretty simple: if the element at (x, y) exists, return it. Else, throw a std::out_of_range exception. To add an element, the caller should use another member function, e.g., insert().
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    if the element at (x, y) exists, return it.
    But what if the user sets the element to 0?
    He needs a "set to 0" detector.
    A separate set method may be best.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,593
    But what if the user sets the element to 0?
    He needs a "set to 0" detector.
    A separate set method may be best.
    Yes, I forgot about that.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User nepper271's Avatar
    Join Date
    Jan 2008
    Location
    Brazil
    Posts
    50
    Yes, considering I must check if the element exists and must erase it if the user set it to zero, I will use a set function separate from the get function.

    My function will be

    Code:
    A.set (int i, int j, double a)
    It will find the element (i, j), if he can't find it, it will create a new element with value a, if a is not zero. If he finds it, it will check whether a is zero. If a is zero, it will erase element (i,j), otherwise it will simply change (i,j) element's value to a.

    Thank you everyone,
    Nepper271.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,593
    It will find the element (i, j), if he can't find it, it will create a new element with value a, if a is not zero. If he finds it, it will check whether a is zero. If a is zero, it will erase element (i,j), otherwise it will simply change (i,j) element's value to a.
    That sounds correct to me.

    By the way, are you really naming your sparse matrix class SPARSE? Note that such all uppercase identifiers are typically reserved by convention for macro names and names of special constants. More typical conventions for class names include capitalising each word in the name (e.g., Sparse or SparseMatrix), adding a C prefix (e.g., CSparse, CSparseMatrix), or simply leaving it all in lowercase with underscore separators.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User nepper271's Avatar
    Join Date
    Jan 2008
    Location
    Brazil
    Posts
    50
    No, no, of course not. I'm actually naming it 'esparsa', that is, sparse in portuguese, hehe.
    But thanks for the tips, are always welcome.

    Nepper271.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. getting orientation and position in opengl
    By ting in forum Game Programming
    Replies: 9
    Last Post: 07-07-2008, 04:13 PM
  3. Gauss-Jordan Matrix Inversion in C++
    By Max_Power82 in forum C++ Programming
    Replies: 3
    Last Post: 12-03-2006, 07:31 PM
  4. OpenGL - Getting a Grip on Perspectives
    By Tonto in forum Game Programming
    Replies: 14
    Last Post: 11-09-2006, 11:00 PM
  5. Sorting a 2-dimensional array
    By kmoyle73 in forum C++ Programming
    Replies: 3
    Last Post: 05-05-2004, 01:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21