Resizing arrays in C++?

[Default User]

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

 

[Juha Kettunen]

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.

 

[Juha Kettunen]

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.

 

[Juha Kettunen]

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

 

[Ioannis Vranos]

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

 

[John Harrison]

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

 

[Ioannis Vranos]

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

 

[John Harrison]

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:perator=, 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

 

[Default User]

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

 

[Default User]

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

 

[Ioannis Vranos]

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

 

[Ioannis Vranos]

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

 

[John Harrison]

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

 

[Chris Dearlove]

John Harrison ([email protected]) 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.)

 

[John Harrison]

John Harrison ([email protected]) 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:air<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

 

[tom_usenet]

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

 

[John Harrison]

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:air<const Key,
Value>.

john

 

[tom_usenet]

Are you sure? I would say that std::map and std::multimap elements are not
assignable by definition since they are defined as std:air<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/wg21/docs/lwg-defects.html#276
Clearly, node based containers don't need assignable elements in
general, although they might for certain member functions.

Tom

 

[John Harrison]

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/wg21/docs/lwg-defects.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:ush_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

 

[Chris Dearlove]

John Harrison ([email protected]) 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:air<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.)