Like Tree2Likes
  • 2 Post By iMalc

Automatically resizing arrays

This is a discussion on Automatically resizing arrays within the C++ Programming forums, part of the General Programming Boards category; I am implementing a sort of MATLAB-esque interpreter. I had asked a question in a previous thread about std::vector and ...

  1. #1
    Epy
    Epy is offline
    Hen-teaser Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    880

    Automatically resizing arrays

    I am implementing a sort of MATLAB-esque interpreter. I had asked a question in a previous thread about std::vector and apparently it's not really want I want.

    In MATLAB, you can dynamically allocate arrays in a very poor and inefficient fashion, i.e.

    a(54,34) = 4.5;

    would allocate an array of that size and set the very bottom right corner to 4.5. You can further say

    a(54,66) = 23532;

    which would resize the array and set that value.

    My question is, what would be the most efficient way to implement this? Right now I'm just thinking that it needs to allocate an array larger than the initial dimensions (create a reserve), and every time you go to set a value, through overloaded operations or whatever, it'll have to check to see if you're requesting a location outside of the reserve and possibly resize and copy the old data. If it's not outside the reserve size, increase the "size" variable of the array to match the new largest dimensions accessed.

    I can't really think of a better way to do this. I'd like to avoid if statements for every time you want to set a value...but I don't think I'm going to get around it. Thanks in advance for any suggestions.

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I'd like to avoid if statements for every time you want to set a value...but I don't think I'm going to get around it.
    There's no way around it.

    You could use a std::vector of std::vector's, and resize as needed. That way the std::vector will handle memory allocation, re-allocation, etc. for you. The at() method will let you know when access is out of range.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    Use these underneath ... judiciously:
    Allocator (C++) - Wikipedia, the free encyclopedia
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    You want either a "sparse matrix" or a
    Code:
    std::map<std::pair<int, int>, int>
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Epy
    Epy is offline
    Hen-teaser Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    880
    Quote Originally Posted by iMalc View Post
    You want either a "sparse matrix" or a
    Code:
    std::map<std::pair<int, int>, int>
    The array might not be sparse though, the matrix might be full of actual data and then some idiot decides he wants to add an additional column.

    Edit: This will mostly be for use with a 1-D array
    Last edited by Epy; 02-03-2012 at 12:45 PM.

  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,188
    If you don't use a sparse array (ie, add elements to every index), then use push_back.
    Otherwise you can just add resize statements to resize the vector to the row/column you are currently going to assign. Not as convenient as Matlab, but tt isn't that complicated, at least.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  7. #7
    Epy
    Epy is offline
    Hen-teaser Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    880
    Trying to copy MATLAB's behavior exactly. The problem with push_back AFAIK is that it only inserts a value at the end of the array. I need the ability to assign a value far far away.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    You simply need a class with a method that allows you to read or write any cell, and which resizes upon out-of-bounds access. This is not hard. I was feeling generous so...
    Code:
    #include <vector>
    
    template <typename T>
    class growableMatrix
    {
    	std::vector<T> contents;
    	size_t num_rows, num_cols;
    public:
    	growableMatrix(size_t rows=0, size_t cols=0) :
    	  contents(rows*cols), num_rows(rows), num_cols(cols)
    	{}
    	T &operator()(size_t row, size_t col)
    	{
    		if (row >= num_rows && col < num_cols)
    		{
    			num_rows = row+1;
    			contents.resize(num_rows*num_cols);
    		}
    		else if (row >= num_rows || col >= num_cols)
    		{
    			size_t new_num_rows = std::max(row+1, num_rows);
    			size_t new_num_cols = std::max(col+1, num_cols);
    			std::vector<T> new_contents(new_num_rows * new_num_cols);
    			for (size_t i = 0; i<num_rows; ++i)
    				for (size_t j = 0; j<num_cols; ++j)
    					new_contents[i * new_num_cols + j] = contents[i * num_cols + j];
    			new_contents.swap(contents);
    			num_rows = new_num_rows;
    			num_cols = new_num_cols;
    		}
    		return contents[row * num_cols + col];
    	}
    	T operator()(size_t row, size_t col) const
    	{
    		if (row >= num_rows || col >= num_cols)
    			return T();
    		return contents[row * num_cols + col];
    	}
    	size_t width() const { return num_cols; }
    	size_t height() const { return num_rows; }
    };
    
    
    	// Example usage:
    	growableMatrix<double> x;
    	x(3, 4) = 12;
    	x(4, 5) = 20;
    	x(4, 8) = 32;
    	x(6, 8) = 48;
    	x(2, 7) = 14;
    
    	assert(x(3, 4) == 12);
    	assert(x(4, 5) == 20);
    	assert(x(4, 8) == 32);
    	assert(x(6, 8) == 48);
    	assert(x(2, 7) == 14);
    
    	const growableMatrix<double> &y = x;	
    	assert(y(10, 99) == 0.0);
    	assert(y(4, 8) == 32);
    	assert(y.height() == 7 && y.width() == 9);
    Heck I even tested it today.
    Note that it does not support negative indexing, I assume this is not required. You'll note that I also added a const accessor that allows you to perform reads, even to coordinates which have never been written to, in which case you'll get back zero.
    Last edited by iMalc; 02-03-2012 at 11:48 PM.
    Epy and C_ntua like this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Epy
    Epy is offline
    Hen-teaser Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    880
    Lol, I didn't want someone to do it for me. I just wanted to make sure that the obvious solution is the most efficient solution. Thank you though.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    Nevermind, you're welcome. It's not complete of course, it's lacking a swap method for starters. Sometimes the best way to describe a solution is to show rather than tell.

    One of the main reasons I come here is to get inspired by mildly interesting problems that make me go "Hey I know a good way of doing that which would result in some nice reusable code".

    Hmm, I also just noticed that if it weren't for lines 16 & 17, it would provide the strong exception safety guarantee. Lines 14-18 aren't really necessary anyway, they're just an optimisation I thought of that I'm not sure makes any significant difference. I'll fix my local copy, and might put it up on my site some time later.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. char arrays, "cutting", resizing etc.
    By cnewbie1 in forum C Programming
    Replies: 29
    Last Post: 06-21-2011, 11:41 AM
  2. automatically disassociating pointers
    By underthesun in forum C++ Programming
    Replies: 19
    Last Post: 07-16-2009, 04:58 PM
  3. Do cpp Files get Included Automatically in VS?
    By bengreenwood in forum C++ Programming
    Replies: 2
    Last Post: 05-20-2009, 04:12 PM
  4. Arrays getting disfigured automatically!
    By rghai6 in forum C++ Programming
    Replies: 4
    Last Post: 10-08-2007, 04:36 AM
  5. Resizing Arrays in a Class
    By XSquared in forum C++ Programming
    Replies: 3
    Last Post: 07-03-2002, 09:45 PM

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