Resizing arrays in C++?

[Blue Ocean]

How do I do it?

I'm doing a practice problem which includes me implementing a set of
ints as a class. I don't want to use vector because that would be
cheating. I don't want to spend enough time on it to make it a
treeset, so I'm just gonna do an array set. It's gonna have a static
const int default size, and it's going to have a member private int
threshold. Once the size of the set passes the threshold, the next
call to any operation on it will resize it to double whatever its
current size is.

So the only difficulty is, how do I resize the array? I know that I
could use c's malloc and realloc if I included the libraries, but I
don't know if this is the right way to do things in C++.

Any help is much appreciated, as always.

 

[Default User]

How do I do it?

I'm doing a practice problem which includes me implementing a set of
ints as a class. I don't want to use vector because that would be
cheating. I don't want to spend enough time on it to make it a
treeset, so I'm just gonna do an array set. It's gonna have a static
const int default size, and it's going to have a member private int
threshold. Once the size of the set passes the threshold, the next
call to any operation on it will resize it to double whatever its
current size is.

So the only difficulty is, how do I resize the array? I know that I
could use c's malloc and realloc if I included the libraries, but I
don't know if this is the right way to do things in C++.

Well, malloc() and realloc() are part of C. As you dealing with POD data
(ints) there's no real problem doing so. If you use new, then you'd have
to copy the data to the new block. So pick method and go with it. I'd
use the *alloc() family, personally if I had to do this problem.

Don't forget you need to implement the [] and = operators at the least
to make it look work an array. What to do with out of bounds access is
up to you.



Brian Rodenborn

 

[Default User]

Well, malloc() and realloc() are part of C.

Damn. Are part of C++ I meant to say.



Brian Rodenborn

 

[Rolf Magnus]

How do I do it?

Do what?

I'm doing a practice problem which includes me implementing a set of
ints as a class. I don't want to use vector because that would be
cheating. I don't want to spend enough time on it to make it a
treeset, so I'm just gonna do an array set. It's gonna have a static
const int default size, and it's going to have a member private int
threshold. Once the size of the set passes the threshold, the next
call to any operation on it will resize it to double whatever its
current size is.

So the only difficulty is, how do I resize the array? I know that I
could use c's malloc and realloc if I included the libraries, but I
don't know if this is the right way to do things in C++.

Use new. If you need to resize, allocate another block with new, copy
the data over and deallocate the old block. That's what realloc usually
does, too.

 

[Default User]

Use new. If you need to resize, allocate another block with new, copy
the data over and deallocate the old block. That's what realloc usually
does, too.

So why use it instead of realloc()? Besides saving coding steps, there's
a possiblity that realloc() will have some under-the-hood tricks to
speed things up.

Now, if he was creating a template version that would deal with non-POD
objects, then yes. But in this case, new only adds overhead while buying
you nothing. The allocated data is contained and managed by the array
class, it won't have the problem of incorrect deallocation that can
happen when mixing new and malloc() allocations.



Brian Rodenborn

 

[Aguilar, James]

I remember reading from some book, that never use malloc with C++, but use
new instead. dont remember the reason. Was it even in Bjarne's book? I have
a feeling, that new is better ... but I am not going to start arguing.

I went and looked it up in Bjarne's text after you mentioned it. It does
indeed say in Ch 1's notes to C programmers not to use malloc or realloc
unless it's unavoidable.

 

[Juha Kettunen]

So why use it instead of realloc()? Besides saving coding steps, there's
a possiblity that realloc() will have some under-the-hood tricks to
speed things up.

I remember reading from some book, that never use malloc with C++, but use
new instead. dont remember the reason. Was it even in Bjarne's book? I have
a feeling, that new is better ... but I am not going to start arguing.

Any experts here to tell the truth?

 

[Julie]

I went and looked it up in Bjarne's text after you mentioned it. It does
indeed say in Ch 1's notes to C programmers not to use malloc or realloc
unless it's unavoidable.

Hopefully he went off to explain exactly why he made that statement.

Personally, I avoid all 'do' or 'don't do' generalizations -- they really serve
no purpose. I have found that having someone understand the various
idioms/solutions, and then let them make what they feel to be the appropriate
choice goes a lot further to creating good programmers and programming styles.

My recommendation to the OP is to: research the various ways to create and
maintain arrays, including C-style malloc, C++ new, STL containers, rolling
your own container, etc. If you don't have the time/desire to do all that
research up front, typically the best solution for arrays is using one of the
STL containers such as vector.

Remember, that all of the language constructs are there for a reason. There is
no perfect solution for all situations. Consider each possible solution on a
case-by-case basis, and when you are done, review what you have done and see if
it truly fit your needs/requirements. If not, either re-implement (refactor),
or learn from the experience and make improvements in the future.

 

[John Harrison]

I remember reading from some book, that never use malloc with C++, but
use
new instead. dont remember the reason. Was it even in Bjarne's book? I
have
a feeling, that new is better ... but I am not going to start arguing.

Any experts here to tell the truth?

The reason is undoubtedly that new creates objects (i.e. constructors get
called) whereas malloc only allocates memory (no constructors get called).
However the OP is creating ints, so there is no constructor to call. There
are also situations where there is a constructor but you want to delay
calling it for some reason. As Julie says later on, always be suspicious
of 'never to this', 'always do that', try to understand the reasons for
the advice and realise that there often will be exceptions.

I agree with DefaultUser, in this case I think malloc, realloc would be
fine, unless the OP is thinking at some future point of trying to get his
class working with something more complex than ints.

john

 

[John Harrison]

I agree with DefaultUser, in this case I think malloc, realloc would be

fine, unless the OP is thinking at some future point of trying to get
his
class working with something more complex than ints.

But this fact is maybe just the reason to use new at the very beginning
...so that your code is ready to all changes better. You dont need to
remember in future whether you need to change malloc to new or not ...
the
code is ready for complicated modifications. I personally prefer to write
code, which is ready for the future, and you need to change as little as
possible to get it work after adding new things (of course this is not
always possible, for example you cannot code so that Windows code will be
easily to translated to Unix code for example). I am always keeping in my
mind, that the code is easily ready for the future addings. Thats why for
example, if you need to define human (and at the first version you need
only
integers to define it), I will NOT define it as:

int Human[10];

but

class CHuman
{
....
};

CHuman Human[10];


So that it is ready for the future when I want to add something more for
the
Human.

Is this right?

Yes I think its right. Far, far too many programmers just think of solving
the immediate problem rather than thinking about how the code is likely to
evolve to solve future problems. Its definitely a sign that you are a good
programmer if you are thinking that way.

However I did get the impression that the OP was just playing around to
learn the language, rather that writing some code that will stand the test
of time.

john

 

[Juha Kettunen]

I agree with DefaultUser, in this case I think malloc, realloc would be

fine, unless the OP is thinking at some future point of trying to get his
class working with something more complex than ints.

But this fact is maybe just the reason to use new at the very beginning
....so that your code is ready to all changes better. You dont need to
remember in future whether you need to change malloc to new or not ... the
code is ready for complicated modifications. I personally prefer to write
code, which is ready for the future, and you need to change as little as
possible to get it work after adding new things (of course this is not
always possible, for example you cannot code so that Windows code will be
easily to translated to Unix code for example). I am always keeping in my
mind, that the code is easily ready for the future addings. Thats why for
example, if you need to define human (and at the first version you need only
integers to define it), I will NOT define it as:

int Human[10];

but

class CHuman
{
.....
};

CHuman Human[10];


So that it is ready for the future when I want to add something more for the
Human.

Is this right?

 

[Ioannis Vranos]

How do I do it?

I'm doing a practice problem which includes me implementing a set of
ints as a class.

Unless you are just experimenting with C++, you had better use std::set
or std::mutliset defined in <set>.

I don't want to use vector because that would be
cheating. I don't want to spend enough time on it to make it a
treeset, so I'm just gonna do an array set. It's gonna have a static
const int default size, and it's going to have a member private int
threshold. Once the size of the set passes the threshold, the next
call to any operation on it will resize it to double whatever its
current size is.

So the only difficulty is, how do I resize the array? I know that I
could use c's malloc and realloc if I included the libraries, but I
don't know if this is the right way to do things in C++.

The malloc() family do not call constructors for objects created. You
can use them on ints without problem, but it is better to not get used
to them.


Instead of the malloc() family and the new family you *should* use
vectors (unless another container is more suitable). In this way, if an
exception is thrown, the container's destructor will clean up things by
itself.


This is not about cheating, but reliable programming. On the other hand
if you are experimenting with the low level facilities, you can use
new[]/delete[] in combination.

Unfortunately I have paused reading TC++PL at the beginning of Chapter
19. From Chapter 19 and then there are some very cool stuff including
<memory> facilities.






Regards,

Ioannis Vranos

 

[Juha Kettunen]

Yes I think its right. Far, far too many programmers just think of solving
the immediate problem rather than thinking about how the code is likely to
evolve to solve future problems.

Sometimes this kind of "wrong" style is forced by leaders of the project
when they want the program to be coded as fast as possible. You just dont
have the time to do things properly ... It happened to me in my last job. I
always wanted to do good code, but if you need to be fast, you cannot do
things properly.

 

[rep_movsd]

Hi
Actually there's nothing wrong with using malloc / realloc / free in
C++ so long as you use them properly.
At least on VC6 , new actually calls malloc(), though that can't be
relied upon
in other releases or compilers.

 

[Default User]

But this fact is maybe just the reason to use new at the very beginning
...so that your code is ready to all changes better. You dont need to
remember in future whether you need to change malloc to new or not ... the
code is ready for complicated modifications.

This is a homework problem. In actual usage, why write such a thing? The
std::vector template class is ready for use and is very likely better
than anything you cobble together.

It's good to think about expansion, but don't hamstring the problem at
hand. The change from malloc() to new would be one of many that would
need to be made if you expanded.

Use the correct tool for the job, not necessarily the tool you might
need next week.




Brian Rodenborn

 

[Default User]

Yes I think its right. Far, far too many programmers just think of solving
the immediate problem rather than thinking about how the code is likely to
evolve to solve future problems.

Also, too many people try to make "solutions" that implement unnecessary
functionality under the idea that the may need it someday. This is a
balancing act.

Too often I see things like Juha wrote, "I've heard I'm not supposed to
use X . . ." Well, you should understand what X is. In this case, anyone
programming in C++ should become familiar with malloc() and realloc(),
as well as new, new(), new[], placement new, all the various forms of
allocation.

However I did get the impression that the OP was just playing around to
learn the language, rather that writing some code that will stand the test
of time.

Right. I thought I remembered him saying it was homework, but rereading
it seems not.




Brian Rodenborn

 

[Aguilar, James]

This is a homework problem. In actual usage, why write such a thing? The
std::vector template class is ready for use and is very likely better
than anything you cobble together.

It actually wasn't a homework problem at all. Classes don't start until
Sept. 1st, and though I'm in Algorithms and Data Structures next semester, I
don't think they will be giving us anything quite this easy. It was a
problem from "The C++ Programming Language," Chapter 10, question 9. The
reason why I don't want to use a vector is because I want to do it the way
vector does it. I'm trying to pretend like it is real library code, for
which you would not want to use the (if slightly) less efficient vector.

In any case, I've got it working now, using delete and then new.

 

[Ioannis Vranos]

It actually wasn't a homework problem at all. Classes don't start until
Sept. 1st, and though I'm in Algorithms and Data Structures next semester, I
don't think they will be giving us anything quite this easy. It was a
problem from "The C++ Programming Language," Chapter 10, question 9. The
reason why I don't want to use a vector is because I want to do it the way
vector does it. I'm trying to pretend like it is real library code, for
which you would not want to use the (if slightly) less efficient vector.

At first, a compiler/library vendor may use even assembly in the
definition of a standard library facility. Of course they can also be
defined with the language itself.


On another matter, what do you mean by "less efficient vector"?






Regards,

Ioannis Vranos

http://www23.brinkster.com/noicys

 

[Aguilar, James]

Aguilar, James wrote:

On another matter, what do you mean by "less efficient vector"?

I have been given to understand that vector can in some situations be
slightly slower than just using arrays, if you're careful with the arrays
and you know what you're doing. However, this is beside the point, and I'm
sorry for bringing it up.

My point is that if I'm trying to write a set class, it would be silly to
use standard library collections to do it. The whole exercise is based on
the idea that, in the writing of this class, I am avoiding the use of
standard collection libraries. Otherwise, why write a set at all, instead
of just using the standard library's version?

 

[Ioannis Vranos]

I have been given to understand that vector can in some situations be
slightly slower than just using arrays, if you're careful with the arrays
and you know what you're doing. However, this is beside the point, and I'm
sorry for bringing it up.

That is a common myth. Check my page

http://www23.brinkster.com/noicys/cppfaq.htm

for that. C++ standard library facilities are aimed to have the maximum
efficiency.


So if you make an array on the free store by yourself instead of having
a vector to make its own you gain nothing. In the contrary you lose the
elegance and easiness of vector usage and your code is less bullet
proof.


And if speed is your primary concern (e.g. math intensive matrix
operations) you can consider the use of valarray.


Also check:

http://www.research.att.com/~bs/esc99.html

My point is that if I'm trying to write a set class, it would be silly to
use standard library collections to do it.

Why? Usual C++ code:


class whatever
{
vector<int>array;
// ...
public:
A() {}
A(const unsigned size):array(size) { ... }
// ...
};


instead of

class outdated
{
int *array;
// ...
public:
A() {}
A(const unsigned size) { array=new int[size]; ... }
~A() { delete[] array; }
// ...
};

The whole exercise is based on
the idea that, in the writing of this class, I am avoiding the use of
standard collection libraries. Otherwise, why write a set at all, instead
of just using the standard library's version?

If it is not a homework, I do wonder why you are writing one. Also
containers can also use other containers inside their definitions.






Regards,

Ioannis Vranos

http://www23.brinkster.com/noicys