By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,370 Members | 1,552 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,370 IT Pros & Developers. It's quick & easy.

Resizing arrays in C++?

P: n/a
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.
Jul 22 '05 #1
Share this Question
Share on Google+
46 Replies


P: n/a
Blue Ocean wrote:

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
Jul 22 '05 #2

P: n/a
Blue Ocean wrote:
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.

Jul 22 '05 #3

P: n/a
Default User wrote:
Well, malloc() and realloc() are part of C.


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

Brian Rodenborn
Jul 22 '05 #4

P: n/a
Rolf Magnus wrote:
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
Jul 22 '05 #5

P: n/a

"Default User" <fi********@boeing.com.invalid> wrote in message
news:40***************@boeing.com.invalid...
Rolf Magnus wrote:
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.


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?
Jul 22 '05 #6

P: n/a

"Juha Kettunen" <no******@email.com> wrote in message
news:NN***************@newsfe5-gui.ntli.net...

"Default User" <fi********@boeing.com.invalid> wrote in message
news:40***************@boeing.com.invalid...
Rolf Magnus wrote:
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.


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.
Jul 22 '05 #7

P: n/a
"Aguilar, James" wrote:

"Juha Kettunen" <no******@email.com> wrote in message
news:NN***************@newsfe5-gui.ntli.net...

"Default User" <fi********@boeing.com.invalid> wrote in message
news:40***************@boeing.com.invalid...
Rolf Magnus wrote:

> 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.


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.


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.
Jul 22 '05 #8

P: n/a
On Sun, 11 Jul 2004 00:25:17 GMT, Juha Kettunen <no******@email.com> wrote:

"Default User" <fi********@boeing.com.invalid> wrote in message
news:40***************@boeing.com.invalid...
Rolf Magnus wrote:
> 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.


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
Jul 22 '05 #9

P: n/a

"John Harrison" <jo*************@hotmail.com> wrote in message
news:opsaymu9ol212331@andronicus...
On Sun, 11 Jul 2004 00:25:17 GMT, Juha Kettunen <no******@email.com> wrote: 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?
Jul 22 '05 #10

P: n/a
On Sun, 11 Jul 2004 07:52:01 GMT, Juha Kettunen <no******@email.com> wrote:

"John Harrison" <jo*************@hotmail.com> wrote in message
news:opsaymu9ol212331@andronicus...
On Sun, 11 Jul 2004 00:25:17 GMT, Juha Kettunen <no******@email.com>

wrote:
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
Jul 22 '05 #11

P: n/a

"John Harrison" <jo*************@hotmail.com> wrote in message
news:opsayovgu4212331@andronicus...
On Sun, 11 Jul 2004 07:52:01 GMT, Juha Kettunen <no******@email.com> wrote:

"John Harrison" <jo*************@hotmail.com> wrote in message
news:opsaymu9ol212331@andronicus...


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.
Jul 22 '05 #12

P: n/a
Blue Ocean wrote:
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
Jul 22 '05 #13

P: n/a
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.
Jul 22 '05 #14

P: n/a
Juha Kettunen wrote:
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
Jul 22 '05 #15

P: n/a
John Harrison wrote:
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
Jul 22 '05 #16

P: n/a

"Default User" <fi********@boeing.com.invalid> wrote in message
news:40***************@boeing.com.invalid...
Juha Kettunen wrote:
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 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.
Jul 22 '05 #17

P: n/a
Aguilar, James wrote:
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
Jul 22 '05 #18

P: n/a

"Ioannis Vranos" <iv*@guesswh.at.grad.com> wrote in message
news:cc***********@ulysses.noc.ntua.gr...
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?
Jul 22 '05 #19

P: n/a
Aguilar, James wrote:
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
Jul 22 '05 #20

P: n/a
"Aguilar, James" wrote:

"Default User" <fi********@boeing.com.invalid> wrote in message
news:40***************@boeing.com.invalid...
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.


I noted that in another post.

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.
As someone else pointed out, you were supposed to create a set, not a
vector. So you shouldn't be implementing the way vector does.
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.
Says who? Library code has as much need to be safe and easy to develop
as any other code. Premature optimization and all that.
In any case, I've got it working now, using delete and then new.


Ok, good.

Brian Rodenborn
Jul 22 '05 #21

P: n/a

"Default User" <fi********@boeing.com.invalid> wrote in message
news:40***************@boeing.com.invalid...
John Harrison wrote:
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.


but on the other hand, If a hard-core professional gives that kind of
advice, its very possible that it is the truth! Yes , if you have time, you
can learn it yourself as well, but sometimes you just listen what experts
say.
Jul 22 '05 #22

P: n/a

"Ioannis Vranos" <iv*@guesswh.at.grad.com> wrote in message
news:cc***********@ulysses.noc.ntua.gr...
Aguilar, James wrote:
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


thanks for this info, very interesting . Now I understand that STL is good
to use.
Jul 22 '05 #23

P: n/a
one question: would you always use std vectors instead of int* p? What is
then the use of int* arrays?
Jul 22 '05 #24

P: n/a
Juha Kettunen wrote:
one question: would you always use std vectors instead of int* p?

Yes, including built in arrays! And for all types of objects, not only
built in types.
What is
then the use of int* arrays?

To define vectors. :-) I suggest you read "The C++ Programming Language"
3rd Edition or Special Edition by Bjarne Stroustrup, the creator of C++.

An interesting technique, C++ supports is "resource acquisition is
initialisation".
In a few words, "resource acquisition is initialisation" technique is the
encapsulation of a resource to a class having the destructor
automatically free the resource and the constructors to automatically
allocate. The destructor is automatically called when the object goes
out of scope or an exception is thrown and you have not to allocate and
deallocate manually resources 1000 times in your code. This also
decreases the amount of the code.
Imagine something like:

class file
{
FILE *fp;

public:
file(const std::string &s)
{
fp=fopen(s.c_str(), "rb");

if fp==NULL
throw custom_exception();

}

....

~file() { fclose(fp); }
};
Of course C++ standard library provides better file facilities (that
also support this technique), but this was an example. "Resource
acquisition is initialisation" technique can be applied to any resource
(ip connections, e.t.c.) and produces bullet proof code.

All the containers of C++ standard library support "resource
acquisition is initialisation" (string, e.t.c.).


Regards,

Ioannis Vranos

http://www23.brinkster.com/noicys
Jul 22 '05 #25

P: n/a
On Tue, 13 Jul 2004 10:06:14 +0300, Ioannis Vranos
<iv*@guesswh.at.grad.com> wrote:
Juha Kettunen wrote:
one question: would you always use std vectors instead of int* p?

Yes, including built in arrays! And for all types of objects, not only
built in types.


Interesting point that I've just run into. I tried to use a vector for a
class that was copy constructable but not copy assignable. This failed to
compile on both implementaions of the STL I tried it on, even though I was
not using any methods that obviously needed assignment.

So while I agree in general, in this case I had to roll my own vector
class (which of course used pointers and dynamic allocation).

john
Jul 22 '05 #26

P: n/a
John Harrison wrote:
Interesting point that I've just run into. I tried to use a vector for
a class that was copy constructable but not copy assignable. This
failed to compile on both implementaions of the STL I tried it on, even
though I was not using any methods that obviously needed assignment.

So while I agree in general, in this case I had to roll my own vector
class (which of course used pointers and dynamic allocation).


It seems you have run to an outdated implementation. Perhaps if you
provided an example code we could be more helpful.


Regards,

Ioannis Vranos

http://www23.brinkster.com/noicys
Jul 22 '05 #27

P: n/a
On Tue, 13 Jul 2004 10:42:08 +0300, Ioannis Vranos
<iv*@guesswh.at.grad.com> wrote:
John Harrison wrote:
Interesting point that I've just run into. I tried to use a vector for
a class that was copy constructable but not copy assignable. This
failed to compile on both implementaions of the STL I tried it on,
even though I was not using any methods that obviously needed
assignment.
So while I agree in general, in this case I had to roll my own vector
class (which of course used pointers and dynamic allocation).


It seems you have run to an outdated implementation. Perhaps if you
provided an example code we could be more helpful.


Well I wasn't actually asking for help, but since you've asked the
following fails to compile on either VC++ 7.1, g++ 3.3.1 or online Comeau
C++, so I don't think its a matter of an outdated implementation.

#include <vector>

struct Node
{
const int x;
int y;
};

int main()
{
Node x = { 1, 2 };
std::vector<Node> v;
v.push_back(x);
}

All error messages refer to the unusable Node::operator=, in fact Comeau
explciitly says that I've violated the assignable requirement. Remove the
call to push_back and g++ and VC++ 7.1 both compile it, but Comeau still
fails. I guess assignablity is a general requirement of std::vector.

So as I said, I wrote my own vector type class which did not require
assignment. The only point I was making was that sometimes you cannot rely
on the STL even for simple things like vectors.

john
Jul 22 '05 #28

P: n/a
Juha Kettunen wrote:

"Default User" <fi********@boeing.com.invalid> wrote in message
news:40***************@boeing.com.invalid...
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.


but on the other hand, If a hard-core professional gives that kind of
advice, its very possible that it is the truth!


But you'd better learn WHY. Just accepting blindly such advice is a bad
idea. If a hard-core professional tells something that you don't
understand, say so. Sometimes your hard-core professional is full of
crap or passes off preferences as fact.
Yes , if you have time, you
can learn it yourself as well, but sometimes you just listen what experts
say.


If you want to have a career in programming, you need to learn what
things do, when to use them, when not to use them. Believe it, after all
I'm a hard-core professional.

Brian Rodenborn
Jul 22 '05 #29

P: n/a
Juha Kettunen wrote:

one question: would you always use std vectors instead of int* p? What is
then the use of int* arrays?


Probably always in place of dynamic arrays, unless you are interacting
with legacy code that requires such a thing.

Fixed arrays can still have a place.

Brian Rodenborn
Jul 22 '05 #30

P: n/a
John Harrison wrote:
Well I wasn't actually asking for help, but since you've asked the
following fails to compile on either VC++ 7.1, g++ 3.3.1 or online
Comeau C++, so I don't think its a matter of an outdated implementation.

#include <vector>

struct Node
{
const int x;
int y;
};

int main()
{
Node x = { 1, 2 };
std::vector<Node> v;
v.push_back(x);
}
Yes push_back() uses the assignment operator to copy the value of the
passed object to a newly created object at the end of the sequence, and
const int x cannot be copied.

#include <vector>

struct Node
{
const int x;
int y;
};

int main()
{
Node x = { 1, 2 };
std::vector<Node> v(1,x);
}


So as I said, I wrote my own vector type class which did not require
assignment. The only point I was making was that sometimes you cannot
rely on the STL even for simple things like vectors.


Before we rush to reinvent the wheel, it is better to have a slow,
thorough read of an up to date C++ book like TC++PL. :-)


Regards,

Ioannis Vranos

http://www23.brinkster.com/noicys
Jul 22 '05 #31

P: n/a
Ioannis Vranos wrote:
Yes push_back() uses the assignment operator to copy the value of the
passed object to a newly created object at the end of the sequence, and
const int x cannot be copied.

Actually push_back() is free to work as its implementer likes, however
since it would be an expensive operation for an implementation to
allocate new memory space, copy all existing elements to the new space,
and delete the old one in every push_back, for efficiency, the
implementations usually allocate more space to use in such situations,
that's why the assignment operator is usually used in each push_back.
As TC++PL says:

"Except for the word vector instead of stack, there is nothing unusual
in this. The suffix _back is used to emphasize that elements are added
to the end of the vector rather than to the beginning.

Adding an element to the end of a vector could be an expensive operation
because extra memory needs to be allocated to hold it. However, an
implementation must ensure that repeated stack operations incur
growth-related-overhead only infrequently."


Regards,

Ioannis Vranos

http://www23.brinkster.com/noicys
Jul 22 '05 #32

P: n/a
On Tue, 13 Jul 2004 22:38:52 +0300, Ioannis Vranos
<iv*@guesswh.at.grad.com> wrote:
Ioannis Vranos wrote:
Yes push_back() uses the assignment operator to copy the value of the
passed object to a newly created object at the end of the sequence, and
const int x cannot be copied.

Actually push_back() is free to work as its implementer likes, however
since it would be an expensive operation for an implementation to
allocate new memory space, copy all existing elements to the new space,
and delete the old one in every push_back, for efficiency, the
implementations usually allocate more space to use in such situations,
that's why the assignment operator is usually used in each push_back.


But that extra space is uninitalised memory so there is no need to assign
to it (in fact it would be wrong to assign to it). It's perfectly possible
to implement push_back without using assignment and without reallocating
memory each push_back.

I was surprised to find that three different implementations had not done
it that way, but apparently the C++ standard gives them that license. I
guess putting an unassignable object in a vector is a pretty obscure thing
to want to do.

So for this particular case I was forced to reinvent the wheel.

john
Jul 22 '05 #33

P: n/a
John Harrison (jo*************@hotmail.com) wrote:
: So for this particular case I was forced to reinvent the wheel.

Or just don't have a const member. Several orders of magnitude
easier.

For just this reason this is one of Steven Dewhurst's C++ Gotchas
(book of that name) which I recall since I just finished reading it.
(I'd agree with the ACCU review's Recommended with Reservations
rating incidentally.)

Jul 22 '05 #34

P: n/a

"Chris Dearlove" <cm*@gmrc.gecm.com> wrote in message
news:40**********@baen1673807.greenlnk.net...
John Harrison (jo*************@hotmail.com) wrote:
: So for this particular case I was forced to reinvent the wheel.

Or just don't have a const member. Several orders of magnitude
easier.


Well believe it or not I had good reasons for having a const member.
Specifically I needed a vector of map<T, U>::value_type. And the C++
standard defines map<T, U>::value_type as std::pair<const T, U>. Note the
const.

I wouldn't normally put const in a class I defined, but I'm not responsible
for what the authors of the C++ standard do.

john
Jul 22 '05 #35

P: n/a
On Tue, 13 Jul 2004 10:42:08 +0300, Ioannis Vranos
<iv*@guesswh.at.grad.com> wrote:
John Harrison wrote:
Interesting point that I've just run into. I tried to use a vector for
a class that was copy constructable but not copy assignable. This
failed to compile on both implementaions of the STL I tried it on, even
though I was not using any methods that obviously needed assignment.

So while I agree in general, in this case I had to roll my own vector
class (which of course used pointers and dynamic allocation).


It seems you have run to an outdated implementation. Perhaps if you
provided an example code we could be more helpful.


Container elements are required to be assignable. Otherwise you have
undefined behaviour (which is this case means some code on some
compilers will compile and work as expected, and some won't compile -
generally there's no danger involved except portability).

Tom
Jul 22 '05 #36

P: n/a

"tom_usenet" <to********@hotmail.com> wrote in message
news:to********************************@4ax.com...
On Tue, 13 Jul 2004 10:42:08 +0300, Ioannis Vranos
<iv*@guesswh.at.grad.com> wrote:
John Harrison wrote:
Interesting point that I've just run into. I tried to use a vector for
a class that was copy constructable but not copy assignable. This
failed to compile on both implementaions of the STL I tried it on, even though I was not using any methods that obviously needed assignment.

So while I agree in general, in this case I had to roll my own vector
class (which of course used pointers and dynamic allocation).


It seems you have run to an outdated implementation. Perhaps if you
provided an example code we could be more helpful.


Container elements are required to be assignable. Otherwise you have
undefined behaviour (which is this case means some code on some
compilers will compile and work as expected, and some won't compile -
generally there's no danger involved except portability).

Tom


Are you sure? I would say that std::map and std::multimap elements are not
assignable by definition since they are defined as std::pair<const Key,
Value>.

john
Jul 22 '05 #37

P: n/a
On Wed, 14 Jul 2004 15:20:17 +0100, "John Harrison"
<jo*************@hotmail.com> wrote:
Are you sure? I would say that std::map and std::multimap elements are not
assignable by definition since they are defined as std::pair<const Key,
Value>.


Yup (although you just had me diving for the standard in doubt:
23.1/3). However, take a look at this:
http://www.open-std.org/jtc1/sc22/wg...fects.html#276
Clearly, node based containers don't need assignable elements in
general, although they might for certain member functions.

Tom
Jul 22 '05 #38

P: n/a

"tom_usenet" <to********@hotmail.com> wrote in message
news:4e********************************@4ax.com...
On Wed, 14 Jul 2004 15:20:17 +0100, "John Harrison"
<jo*************@hotmail.com> wrote:
Are you sure? I would say that std::map and std::multimap elements are notassignable by definition since they are defined as std::pair<const Key,
Value>.


Yup (although you just had me diving for the standard in doubt:
23.1/3). However, take a look at this:
http://www.open-std.org/jtc1/sc22/wg...fects.html#276
Clearly, node based containers don't need assignable elements in
general, although they might for certain member functions.

Tom


Thanks for the link, I always put off finding out this stuff from the
standard itself, I just find it so hard to read.

Quote -
In principle we could also relax the "Assignable" requirement for individual
vector member functions, such as push_back. However, the LWG did not see
great value in such selective relaxation. Doing so would remove
implementors' freedom to implement vector::push_back in terms of
vector::insert.

That's the little nugget of information I've been looking for, I suspected
the reasoning might be someting like that, so its nice to have it confirmed.
Unfortunately a push_back that doesn't require "Assignable" is exactly what
I want, guess I should get myself on that committee.

john
Jul 22 '05 #39

P: n/a
John Harrison (jo*************@hotmail.com) wrote:

: Well believe it or not I had good reasons for having a const member.
: Specifically I needed a vector of map<T, U>::value_type. And the C++
: standard defines map<T, U>::value_type as std::pair<const T, U>. Note the
: const.

OK. Now are those pairs still in a map, or have they been removed
from one? (If the answer is some of each I give up.) In the former
case is there a reason not to have a vector not of the pairs but
of iterators to the pairs? In the latter case can you not work
with a vector of non-const pairs converted from the map value type?

(I'm working from the position that unpleasant although these options
may be compared to what you really want, they aren't as unpleasant
as reinventing vector.)

Jul 22 '05 #40

P: n/a

"Chris Dearlove" <cm*@gmrc.gecm.com> wrote in message
news:40**********@baen1673807.greenlnk.net...
John Harrison (jo*************@hotmail.com) wrote:

: Well believe it or not I had good reasons for having a const member.
: Specifically I needed a vector of map<T, U>::value_type. And the C++
: standard defines map<T, U>::value_type as std::pair<const T, U>. Note the : const.

OK. Now are those pairs still in a map, or have they been removed
from one? (If the answer is some of each I give up.) In the former
case is there a reason not to have a vector not of the pairs but
of iterators to the pairs? In the latter case can you not work
with a vector of non-const pairs converted from the map value type?

(I'm working from the position that unpleasant although these options
may be compared to what you really want, they aren't as unpleasant
as reinventing vector.)


What I'm actually trying to do is develop a general data structure which I'm
calling IndexedMap (add IndexedSet, IndexedMultiMap, and IndexedMultiSet).
This will be very similar to map etc. but the iterators will be random
access and reflect not the ordering of the keys but the order in which the
values were added to the set. A sort of cross between a map and a vector.
You can do it provided you don't mind deletion being O(n) instead of O(lg n)
as it is with map, insert and find remain O(lg n).

My first attempt was something similar to what you suggest, basically
combining a map with a vector and storing links between the two. One thing
bothered my about this however which was that as far as I can tell you need
to store two allocators, one in the map and one in the vector. If the user
wants to use a stateful allocator then they aren't going to be happy.

Then I realised that you could implement a red-black tree algorithm where
all the nodes are stored in a vector and everything would fall into place.
That was when I found out about the assignable requirement of vectors.

I've implemented my vector replacement, its called LightweightVector, didn't
take too long, it has everything that doesn't require you to assign elements
(push_back and pop_back for instance, but no insert or erase), even whole
vector assignment, which is done by copy and swap. As a nice bonus you get
strong exception safety as well. I think I may be using it more often.

john
Jul 22 '05 #41

P: n/a
On Thu, 15 Jul 2004 12:33:26 +0100, "John Harrison"
<jo*************@hotmail.com> wrote:

"Chris Dearlove" <cm*@gmrc.gecm.com> wrote in message
news:40**********@baen1673807.greenlnk.net...
John Harrison (jo*************@hotmail.com) wrote:

: Well believe it or not I had good reasons for having a const member.
: Specifically I needed a vector of map<T, U>::value_type. And the C++
: standard defines map<T, U>::value_type as std::pair<const T, U>. Notethe
: const.

OK. Now are those pairs still in a map, or have they been removed
from one? (If the answer is some of each I give up.) In the former
case is there a reason not to have a vector not of the pairs but
of iterators to the pairs? In the latter case can you not work
with a vector of non-const pairs converted from the map value type?

(I'm working from the position that unpleasant although these options
may be compared to what you really want, they aren't as unpleasant
as reinventing vector.)


What I'm actually trying to do is develop a general data structure which I'm
calling IndexedMap (add IndexedSet, IndexedMultiMap, and IndexedMultiSet).
This will be very similar to map etc. but the iterators will be random
access and reflect not the ordering of the keys but the order in which the
values were added to the set. A sort of cross between a map and a vector.
You can do it provided you don't mind deletion being O(n) instead of O(lg n)
as it is with map, insert and find remain O(lg n).

My first attempt was something similar to what you suggest, basically
combining a map with a vector and storing links between the two. One thing
bothered my about this however which was that as far as I can tell you need
to store two allocators, one in the map and one in the vector. If the user
wants to use a stateful allocator then they aren't going to be happy.


Allocators should be cheap to copy, and shouldn't take up too much
space. Remember that, for example, std::deque has to hold two copies
of the allocator (one for the segment map, one for the segments), so I
don't think it's a problem your map doing the same.
Then I realised that you could implement a red-black tree algorithm where
all the nodes are stored in a vector and everything would fall into place.
That was when I found out about the assignable requirement of vectors.
I see a slight problem with this - you lose stability of references to
elements, an important feature of node based containers. Also, how do
you erase elements from the map? Do you swap the last element over the
erased one, updating the pointers (presumably you've used vector
indices rather than pointers for stability) in the referencing nodes?
Or do you just mark the node as deleted, and skip it during an
insertion-order-iteration?

Tuning your tree to be as fast as a good std::map implementation may
be hard, but the last few % of performance may not be an issue for you
of course. Testing your implementation for correctness is another
issue, and I bet there's a bug in there somewhere if you haven't
written comprehensive unit tests yet.
I've implemented my vector replacement, its called LightweightVector, didn't
take too long, it has everything that doesn't require you to assign elements
(push_back and pop_back for instance, but no insert or erase), even whole
vector assignment, which is done by copy and swap. As a nice bonus you get
strong exception safety as well. I think I may be using it more often.


This should be easier to implement bug free, but have you implemented
all of the comparison operators, etc.?

Finally, have you looked at boost's multi_index library? It's not part
of an official release yet, but it's in the main CVS.

Tom
Jul 22 '05 #42

P: n/a

"tom_usenet" <to********@hotmail.com> wrote in message
news:7v********************************@4ax.com...
On Thu, 15 Jul 2004 12:33:26 +0100, "John Harrison"
<jo*************@hotmail.com> wrote:

"Chris Dearlove" <cm*@gmrc.gecm.com> wrote in message
news:40**********@baen1673807.greenlnk.net...
John Harrison (jo*************@hotmail.com) wrote:

: Well believe it or not I had good reasons for having a const member.
: Specifically I needed a vector of map<T, U>::value_type. And the C++
: standard defines map<T, U>::value_type as std::pair<const T, U>. Notethe
: const.

OK. Now are those pairs still in a map, or have they been removed
from one? (If the answer is some of each I give up.) In the former
case is there a reason not to have a vector not of the pairs but
of iterators to the pairs? In the latter case can you not work
with a vector of non-const pairs converted from the map value type?

(I'm working from the position that unpleasant although these options
may be compared to what you really want, they aren't as unpleasant
as reinventing vector.)


What I'm actually trying to do is develop a general data structure which I'mcalling IndexedMap (add IndexedSet, IndexedMultiMap, and IndexedMultiSet).This will be very similar to map etc. but the iterators will be random
access and reflect not the ordering of the keys but the order in which thevalues were added to the set. A sort of cross between a map and a vector.
You can do it provided you don't mind deletion being O(n) instead of O(lg n)as it is with map, insert and find remain O(lg n).

My first attempt was something similar to what you suggest, basically
combining a map with a vector and storing links between the two. One thingbothered my about this however which was that as far as I can tell you needto store two allocators, one in the map and one in the vector. If the userwants to use a stateful allocator then they aren't going to be happy.


Allocators should be cheap to copy, and shouldn't take up too much
space. Remember that, for example, std::deque has to hold two copies
of the allocator (one for the segment map, one for the segments), so I
don't think it's a problem your map doing the same.


It's not the cost of copying, but the fact that if the user uses a stateful
allocator, then they are going to have trouble accessing that state. To make
a trivial example, suppose the allocator counts allocations made, then with
two allocators we have two counts, presumably the get_allocator method would
return one or other of the allocators and the other count would be lost.

I hadn't realised that std::deque does this already, but then the standard
does give STL implementors license to assume stateless allocators.
Personally I think it would be entirely reasonable for the standard to
mandate that all allocators be stateless.

Of course I didn't abandon my original design solely for this reason. It's
just this issue set me thinking about how I could implement my class with
only a single allocator and when I realised I could, I preferred the new
design anyway.
Then I realised that you could implement a red-black tree algorithm where
all the nodes are stored in a vector and everything would fall into place.That was when I found out about the assignable requirement of vectors.
I see a slight problem with this - you lose stability of references to
elements, an important feature of node based containers. Also, how do
you erase elements from the map? Do you swap the last element over the
erased one, updating the pointers (presumably you've used vector
indices rather than pointers for stability) in the referencing nodes?
Or do you just mark the node as deleted, and skip it during an
insertion-order-iteration?


The main point of my class is that is allows you to efficiently get an index
for any entry added to the container. Because the iterators are random
access you can just subtract the iterator to the start of the container from
the iterator for the inserted element. And of course the reverse, given an
index efficiently get the associated entry.

To answer your other points - I'm not bothered about O(n) deletion time.
Obviously this is a drawback, but it won't matter for the application I have
in mind where elements are only going to be added to the container. I
haven't implemented the erase yet, but it is probably going to successively
destroy and copy construct elements from the deletion point to the end of
the vector. I don't fancy mark as deleted, though it hadn't occurred to me
until now.

And I do use vector indices internally.

And the class will have reserve and capacity methods which will help with
stability of references in some situations (and help with efficiency).

Tuning your tree to be as fast as a good std::map implementation may
be hard, but the last few % of performance may not be an issue for you
of course.
I'll run some comparisons. I suspect the use of vector indices will slow my
implementation down. It might be interesting to see how allocating in a
single block vs allocating nodes affects things. As you say I'm not that
bothered about a few percentage points (but how many is a few?).
Testing your implementation for correctness is another
issue, and I bet there's a bug in there somewhere if you haven't
written comprehensive unit tests yet.
I hate unit tests, but they will be written at some point.
I've implemented my vector replacement, its called LightweightVector, didn'ttake too long, it has everything that doesn't require you to assign elements(push_back and pop_back for instance, but no insert or erase), even whole
vector assignment, which is done by copy and swap. As a nice bonus you getstrong exception safety as well. I think I may be using it more often.
This should be easier to implement bug free, but have you implemented
all of the comparison operators, etc.?


Yes, they are easy enough.

Finally, have you looked at boost's multi_index library? It's not part
of an official release yet, but it's in the main CVS.


No, but I'll check it out, thanks.

john
Jul 22 '05 #43

P: n/a
On Thu, 15 Jul 2004 16:56:36 +0100, "John Harrison"
<jo*************@hotmail.com> wrote:
It's not the cost of copying, but the fact that if the user uses a stateful
allocator, then they are going to have trouble accessing that state. To make
a trivial example, suppose the allocator counts allocations made, then with
two allocators we have two counts, presumably the get_allocator method would
return one or other of the allocators and the other count would be lost.
An allocator like that should use reference counting, using a
representation class that is independent of the template parameter of
the allocator so that differently typed instances can share the data.
get_allocator returns a copy of the allocator, so there will be
multiple copies of it around if someone is using it like that.
I hadn't realised that std::deque does this already, but then the standard
does give STL implementors license to assume stateless allocators.
Personally I think it would be entirely reasonable for the standard to
mandate that all allocators be stateless.
But that makes pool allocators impossible, and they are very useful
for high performance applications, such as games; a lot of games
programmers use the STL these days I think. I think most libraries do
allow stateful allocators, but very few allow exotic
allocator::pointer types (Dinkumware is the only one that I know for
sure supports them).
Of course I didn't abandon my original design solely for this reason. It's
just this issue set me thinking about how I could implement my class with
only a single allocator and when I realised I could, I preferred the new
design anyway.
It is more efficient in terms of memory usage and performance, until
you start deallocating nodes (and as long as you reserve sufficient
space). The locality of reference gained from using contiguous storage
might help performance too, although a custom (stateful!) allocator
can achieve this too.
To answer your other points - I'm not bothered about O(n) deletion time.
Obviously this is a drawback, but it won't matter for the application I have
in mind where elements are only going to be added to the container. I
haven't implemented the erase yet, but it is probably going to successively
destroy and copy construct elements from the deletion point to the end of
the vector. I don't fancy mark as deleted, though it hadn't occurred to me
until now.


When deleting, you'll have to update all of the nodes, subtracting 1
from indices greater than the element (or elements) being deleted, so
erase is going to be a slow operation.

Still, it's always fun writing low level code like containers, if
rather wasteful of time and energy (there are almost always free
alternatives already written and tested). I've never written a
red-black tree, but I bet it's great fun! :o)

Tom
Jul 22 '05 #44

P: n/a
On Thu, 15 Jul 2004 16:56:36 +0100, John Harrison
<jo*************@hotmail.com> wrote:
I
haven't implemented the erase yet, but it is probably going to
successively
destroy and copy construct elements from the deletion point to the end of
the vector. I don't fancy mark as deleted, though it hadn't occurred to
me
until now.


I'm starting to get a bit worried about this. It seems difficult to
arrange any sort of execption safety without copying the entire vector,
which I'm a bit reluctent to do. Any thoughts?

john
Jul 22 '05 #45

P: n/a
On Thu, 15 Jul 2004 18:32:17 +0100, tom_usenet <to********@hotmail.com>
wrote:

Still, it's always fun writing low level code like containers, if
rather wasteful of time and energy (there are almost always free
alternatives already written and tested). I've never written a
red-black tree, but I bet it's great fun! :o)


In a perverse sort of way, yes it is. Of course this is a hobby activity,
I wouldn't be allowed to waste my time on this at work.

john
Jul 22 '05 #46

P: n/a
On Thu, 15 Jul 2004 18:35:19 +0100, "John Harrison"
<jo*************@hotmail.com> wrote:
On Thu, 15 Jul 2004 16:56:36 +0100, John Harrison
<jo*************@hotmail.com> wrote:
I
haven't implemented the erase yet, but it is probably going to
successively
destroy and copy construct elements from the deletion point to the end of
the vector. I don't fancy mark as deleted, though it hadn't occurred to
me
until now.


I'm starting to get a bit worried about this. It seems difficult to
arrange any sort of execption safety without copying the entire vector,
which I'm a bit reluctent to do. Any thoughts?


Hmm, that's a thorny one. I guess you'll have to start by relinking
the nodes as though the erased elements aren't there, then actually do
erase in the vector, finally updating the indices to reflect the
change. If an exception is thrown during the erase in the vector,
you'll have to then update the indices to elements that have moved,
and somehow cope with the fact that you've got two copies of one of
the elements, before rethrowing.

Alternative implementations suddenly do look more attractive, although
it's always hard to give very good exception safety with vector::erase
- if an exception is thrown you inevitably end up with two copies of
one of the elements.

Tom
Jul 22 '05 #47

This discussion thread is closed

Replies have been disabled for this discussion.