about new and delete

[arunix]

is it the right way to write the Code......
Here is mine code for using new and delete where i use get the number
from the user and print them. in a order. can i do it better ?
How?

#include<iostream>
#include<new>

int main()
{
int i,n;
int *p;
std :: cout << "How many numbers would you like to type ";
std :: cin >> i;
p= new(std::nothrow) int;
if(p==0)
std :: cout<<"Memory Could Not Be Allocated ";
else
for(n=0;n<i;n++)
{
std :: cout <<"Enter Number ";
std :: cin >>p[n];
}
std :: cout<< "You have Entered ";
for(n=0; n<i;n++)
{
if(p[n] < p[i-1])
{
std :: cout <<p[n]
<<", ";
}
else if(p[n] == p[i-1])
{
std :: cout <<p[n]
<<".";
}
}
delete [] p;
std :: cout <<std ::endl;
return 0;
}

 

[Scooser]

Hi,
your code will crash if new fails because you'll dereferencing the
NULL pointer when doing the output. So your code is a perfect example
why using the std::nothrow option almost always is a bad idea, don't
do it.

Next is exceptions, yes there are no exceptions in your simple example
but are you sure there aren't in a more realistic scenario? So you
will have a memory leak if something between new and delete will throw
an exception. Solving this scenario by putting the code into a try
block might be a solution but when your catch code looks like this

catch(...){ delete [] p; throw }

you should think about RAII instead and encapsulate the array or
atleast the pointer in an object which deletes the array in its
deconstructor.

The best solution to solve all theser problems is to simply use
std::vector<int> instead of int[]. The vectore takes care of proper
memory handling, and if you have to use old C-code which expects
pointers to arrays and the size of the array like this one:

void oldCFunc (int * data, size_t size);

then you can call it with a vector too

std::vector<int> myVector(20);
oldCFunc (&myVector[0], myVector.size());

 

[arunix]

increasing order. If you typed them in an unsorted order, your punctuation
is going to come out broken.

Thanks Sam for the Reply
Yes its broken when user give unsorted order of numbers. how i can do
better with it. i already done it with vector.

 

[Scooser]

Hi, using the stl you can do it this way:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main( void )
{
typedef std::vector<int> container_type;

container_type values;
container_type::value_type value;

std::cout << "Enter numbers, end with 'q': ";
while (std::cin >> value)
{
values.push_back(value);
}

if (! values.empty())
{
std::cout << "\nYou entered the " << values.size() << " values: ";

const container_type::iterator last (--values.end ());

// copy all but the last value from the container
// to the output stream, use ", " as delimiter.
std::copy ( values.begin()
, last
, std:stream_iterator<container_type::value_type>
(std::cout, ", ") );

// copy the last value to the output stream
std::cout << *last << "." << std::endl;
}
else
std::cout << "\nYou entered no valid data." << std::endl;

return 0;
}


- Scooser

 

[Pandit]

Hi, using the stl you can do it this way:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main( void )
{
  typedef std::vector<int> container_type;

  container_type              values;
  container_type::value_type  value;

  std::cout << "Enter numbers, end with 'q': ";
  while (std::cin >> value)
  {
    values.push_back(value);
  }

  if (! values.empty())
  {
    std::cout << "\nYou entered the " << values.size() << " values: ";

    const container_type::iterator last (--values.end ());

    // copy all but the last value from the container
    // to the output stream, use ", " as delimiter.
    std::copy ( values.begin()
              , last
              , std:stream_iterator<container_type::value_type>
(std::cout, ", ") );

    // copy the last value to the output stream
    std::cout << *last << "." << std::endl;
  }
  else
    std::cout << "\nYou entered no valid data." << std::endl;

  return 0;

}

- Scooser

Thnaks Scooser its Grt...

 

[Richard Herring]

Well, if the scope of your question is whether or not you're using new
and delete correctly, you are. However, if "better" should be
interpreted in a wide, generic, manner, a better approach is to use
std::list,

What features of list, as opposed to any of the other standard
containers, do you see as being particularly relevant to the OP's
problem?

 

[Jerry Coffin]

Richard Herring writes:

[ ... ]

The ability to collect a list of numbers, of variable size, then iterate
over them for the purpose of printing them back.

I'll repeat part of what Richard said for emphasis: "as opposed to
any of the other standard containers"

Do you believe list is the only standard container that can collect a
list of numbers of variable size then iterate over them to print them
out?

If you believe that, I'd suggest you spend a bit of time studying the
other standard containers -- starting with vector and deque.

 

[Richard Herring]

The ability to collect a list of numbers, of variable size, then
iterate over them for the purpose of printing them back.

std::vector can do all of that.

Not random insertion, deletion and splicing, then?

 

[Alf P. Steinbach]

* Sam:

Except that you either need to know the number of elements in advance,
or end up doing a lot of needless reallocations.


Insertion and deletion from a middle of a std::list carries less
complexity than it is for a std::vector, but thank you for playing anyway.

I think the point was that std::list is a poor choice as default: in practice
small allocations are inefficient by default, and the functionality of std::list
is not very well suited to what one ordinarily needs.


Cheers,

- Alf

 

[James Kanze]

Except that you either need to know the number of elements in
advance, or end up doing a lot of needless reallocations.

You do a lot less allocations using vector than you will using
list. This is typical of the sort of thing vector is best for.

 

[Juha Nieminen]

Except that you either need to know the number of elements in advance,
or end up doing a lot of needless reallocations.

A lot? How much is "a lot"?

If you insert, let's say, one million elements into a vector with
push_back() (and without any reserve()), exactly how many reallocations
will be performed? I think the answer is about 20.

Maybe you consider 20 reallocations for 1 million elements "a lot",
but consider how many allocations will your std::list perform when you
push 1 million elements to it.

Insertion and deletion from a middle of a std::list carries less
complexity than it is for a std::vector, but thank you for playing anyway.

That assumes you already have an iterator to the element you want to
remove (or where the insertion should be done). If you don't, then there
will be little difference between std::list and std::vector.

Suppose you have a std::list with 1 million elements, and a
std::vector with 1 million elements, and you want to remove the element
in the middle. Which one is faster?

 

[Juha Nieminen]

Repeating the same question will only yield the same answer: "the
ability to collect a list of numbers, of variable size, then iterate
over them for the purpose of printing them back". If you do not
understand what that means, look it up.

And exactly how is that different from any other STL container? Why is
std::list the best solution in this case?

 

[Pascal J. Bourguignon]

Indeed. push_back is O(1). The number of element copy is only 2 per
element, once for the first insertion, and on average, once per
element for the reallocation.

A lot? How much is "a lot"?

If you insert, let's say, one million elements into a vector with
push_back() (and without any reserve()), exactly how many reallocations
will be performed? I think the answer is about 20.

Maybe you consider 20 reallocations for 1 million elements "a lot",
but consider how many allocations will your std::list perform when you
push 1 million elements to it.

What matters is that each element is not copied O(N) times, but O(1)
times. Actually, when you insert N elements, there's 2N copies
(instead of N copies if you knew in advance the number of elements).

See http://groups.google.fr/group/comp.programming/msg/3da8ae4c35834138?hl=en
(beware of the typo, inserting is O(1), not O(N)).

 

[Bo Persson]

Indeed. push_back is O(1). The number of element copy is only 2 per
element, once for the first insertion, and on average, once per
element for the reallocation.



What matters is that each element is not copied O(N) times, but O(1)
times. Actually, when you insert N elements, there's 2N copies
(instead of N copies if you knew in advance the number of elements).

We also have another problem here - what is the cost of copying one
int? What is the cost of allocating each int separately?

How much did you save from copying N ints over 2N ints?


Bo Persson

 

[Alf P. Steinbach]

* Sam:

Because, in the OP's poster case, his basic demo program did not require
random access, and std::list won't require obtaining the size of the
list in advance, in order to get the best performance.

Hi.

For the OP's purpose, std::vector does not require obtaining the size of the
list in advance (see the push_back() member routine), and has generally better
performance: push_back is of amortized O(1) complexity. ;-)

I guess that's why people are sort of "upset" about your suggestion of std::list.

Not that it's terribly wrong or that std::vector is so much better or that it
matters at all in this case, and if one starts being pedantic about things then
a case can be made for std::deque as the probably best all-round potato.

But std::list is not generally a good *default* choice: it's a very special
purpose structure.


Cheers & hth.,

- Alf

 

[Alf P. Steinbach]

* Sam:

* Sam:

Hi.

For the OP's purpose, std::vector does not require obtaining the size
of the list in advance (see the push_back() member routine), and has
generally better performance: push_back is of amortized O(1)
complexity. ;-)

I am curious how true it is. So, I decided to measure the performance of
std::vector vs std::list in OP's original context: collect and store a
relatively small list of numbers. How efficient is std::list, versus
std::vector, in creating a small list/vector.

Test program:

int main()
{
size_t j;

for (j=0; j<100000; j++)
{
std::list<int> n;
size_t i;

for (i=0; i<10; i++)
n.push_back(i);
}
return (0);
}

Compiled with gcc 4.4.1. Default compilation options. Three consecutive
runs:

[mrsam@lc2440 tmp]$ time ./t

real 0m0.219s
user 0m0.209s
sys 0m0.002s
[mrsam@lc2440 tmp]$ time ./t

real 0m0.214s
user 0m0.208s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t

real 0m0.216s
user 0m0.210s
sys 0m0.002s

Replace std::list with std::vector. The results:

[mrsam@lc2440 tmp]$ time ./t

real 0m0.305s
user 0m0.296s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t

real 0m0.304s
user 0m0.297s
sys 0m0.000s
[mrsam@lc2440 tmp]$ time ./t

real 0m0.303s
user 0m0.297s
sys 0m0.001s

Seems fairly consistent -- std::vector is about 30% slower.

Now, using -O2, the results for std::list:

[mrsam@lc2440 tmp]$ time ./t

real 0m0.093s
user 0m0.086s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t

real 0m0.093s
user 0m0.086s
sys 0m0.000s
[mrsam@lc2440 tmp]$ time ./t

real 0m0.092s
user 0m0.086s
sys 0m0.001s

and for std::vector:

[mrsam@lc2440 tmp]$ time ./t

real 0m0.111s
user 0m0.105s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t

real 0m0.110s
user 0m0.105s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t

real 0m0.110s
user 0m0.104s
sys 0m0.001s

The performance gap has narrowed, somewhat, but std::list still has the
edge.

I guess that's why people are sort of "upset" about your suggestion of
std::list.

Yeah, finding out that they've been barking up the wrong tree, all this
time, can be quite shocking .

But std::list is not generally a good *default* choice: it's a very
special purpose structure.

In OP's use case, it does seem to be a better one.

No.

Can you figure out what's wrong with your measurement?


Cheers & hth.,

- Alf

 

[Alf P. Steinbach]

* Sam:

Yes: nothing.

Well, OK, that may explain your apparent bafflement at the comments you're drawing.

The key to understanding this is to combine three pieces of information:

* The C++03 standard requires a contiguous buffer for std::vector.

* push_back has guaranteed amortized O(1) complexity.

* Allocation is generally way more costly (time) than copying a handful
of bytes.

Regarding the last point it seems that you have a fast allocator. This
influences the relative performance of std::list versus std::vector.

The first two points mean that that when the buffer space is exceeded a
std::vector /must/ increase the buffer size by a factor, not by a constant
amount. The most common, as far as I know, is to just double the buffer size.
This involves 1 allocation plus copying O(n) bytes, where n is the current size.

When a std::vector that uses buffer doubling is created by repeated push_back
operations you therefore have two main contributions to the time: roughly C*n
time for copying (where C is some constant), and roughly A*(1+log2(n)) time for
allocations (where A is some other constant, and log2(x) is the number such that
2^(log2(x)) = x).

In contrast, for the std::list each push_back generally involves one allocation,
so you have roughly C*n+A*n (with possibly not quite the same values for C and
A, but whatever), anyway, linear in n.

If you draw the graph of log2(x) you'll see that from x=1 on it starts going
upward at a good incline, but flattens out rapidly. For example, log2(4) = 2,
but then you have to go up to log2(8) to get 3, and next all the way up to
log2(16) to get 4. Further on, log2(128) = 7, but then you have to go 128 units
more to increase the result to 8. So on, it gets really flat very fast.

And so at the beginning around n=10, which was you chose, there is a practical
possibility that std::list can outperform a std::vector, because (if there is no
small buffer optimization in the std::vector implementation) you have five
allocations for the vector and ten for the list, and with a fast allocator the
data copying of the vector may make up for that.

But if you go up to n=15 you still have just five allocations for the vector,
but now 15 for the list! At this point std::vector will probably outperform
std::list.

At n=16 you should expect a possible apparent drop in std::vector efficiency,
because here (with a buffer-doubling vector) you incur an additional allocation.

But then it's a free ride all the way up to and including n=32, where for the
list you have 32 allocations, and for std::vector you have just 6. Given that
the assumption in the third point above holds, you should expect std::list to be
decidedly inferior efficiency-wise in this range of n. Which is still *small*.

In short, the main problem with your test was that you tested only a single n
which was not just small but very small (namely 10). Instead your test should
have checked various values of n within some reasonable small range. And better
yet, systematically checking the general behavior of std::list versus
std::vector as n increases.


Cheers & hth.,

- Alf

 

[Jerry Coffin]

Yes: nothing.

Rather the contrary -- there's quite a lot wrong with it. First of
all, what you originally claimed was supposed to be done was not just
insert some data into the collection, but iterate over the collection
to print out the items. Your test doesn't iterate over the items to
print them out, OR do anything else with them.

Second, since you've done nothing with the contents of the
collection, it's entirely possible (in fact rather likely, if you're
using a good compiler) that most of what you've done is being
optimized away completely. I can't say exactly how much the
particular compiler you're using happens to do in that direction, but
in the end it doesn't matter -- a meaningful benchmark has to
_ensure_ that it's measuring what it's supposed to, and yours does
nothing of the sort.

Third, you're creating an object (either the vector or list) inside
outer loop, so there's a good chance that the creation time is
affecting your results.

Fourth, you're measuring the time for the program as a whole instead
of even attempting to measure it for the part you care about.

Fifth, the total time taken by either program is small enough that
there's little certainty that the times you're getting mean much of
anything. To mean much, you need to increase the total time taken by
(for example) increasing the number of iterations in your outer loop.

Those aren't really the only problems, but they give some idea of how
far off the mark your test really is.

Now, there is one minor problem: if we actually print out the
contents, that printing will almost inevitably dominate the overall
time -- to the point that what we care about will probably be lost in
the noise. At the same time, we do want to ensure that the contents
of the collection is actually _used_, so the work being done can't be
optimized away. One way to meet both of these requirements is to
summarize the contents of the collection (e.g. add up all the values)
and only print out the sum.

One possible outcome of dealing with those glaring problems would be
code like this:

#include <vector>
#include <list>
#include <time.h>
#include <iostream>
#include <numeric>

int main()
{

std::vector<int> n;

clock_t start = clock();
for (size_t j=0; j<900000; j++)
{
n.clear();
for (size_t i=0; i<10; i++)
n.push_back(i);
}
int total = std::accumulate(n.begin(), n.end(), 0);

clock_t total_time = clock()-start;

std::cout << total << "\n";
std::cout << total_time << "\n";
return (0);
}

Three runs of this gives:

D:\C\source>time_lst
45
46

D:\C\source>time_lst
45
46

D:\C\source>time_lst
45
46

Switching to list gives:

D:\C\source>time_lst
45
1435

D:\C\source>time_lst
45
1435

D:\C\source>time_lst
45
1419

There's still a bit of jitter in the timing, but it's of little
relevance -- either way, vector is quite a bit faster. Of course the
exact ratio also depends on the compiler and library. Trying with the
compilers I have handy, list does a bit better than shown above with
some of them -- but even at best, it's still about 15 times slower
than vector.

 

[Alf P. Steinbach]

* Sam:

Yes. No amount of grandiose pondering on various theoretical aspects of
various algorithms has any impact on the practical conclusion that, for
OP's case, std::list is the best solution.

OK, I put it in first-year-student terms but that wasn't enough.

I'm sorry but I don't think it can be simplified more than that. At least not by me.

While std::list:ush_back()'s complexity is guaranteed constant, with
no additional qualifiers. Period.


Indeed. I'm only using the most popular compiler, and the most popular C
library, on non-MSFT platforms. Gee, I really worked so hard to assemble
such a marginal environment in order to gather those metrics.


Yeah -- just like OP's test program, where I suggested that he'd look at
std::list, instead. I must've missed the part where he was trying to
allocate memory for a million ints, and meticulously typing all of them
in from the keyboard.

Try with more than ten elements.

Talking about millions is, sorry to be blunt, idiocy.

And your analysis, which was aimed to defend one's bias towards
std::vector, conveniently neglected to consider all the other factors
that work to the detriment of std::vector:

1) Objects with expensive copy constructors

2) Objects of large size

Both will work to make std::vector's overall performance worse than
std::list's, as the number of elements in the container increases.

Sorry, that's incorrect.

Your argument for std::vector was resting on theoretical aspects of
std::vector and std::list's complexity outside of the boundaries of the
original OP's use case,

Sorry, that's incorrect.

and had no practical elements. However, once you
went beyond the original OP's requirements, and confined to theoretical
factors only, your argument was artificially limited to only those
theoretical factors that work in std::vector's favor, and they seemingly
ommited all the factors that work in std::list's favor.

I'm sorry, but an analysis of complexity isn't a set of arguments for and
against. It isn't an emotional thing feeling your way to a decision about which
arguments are strongest or most convincing. It's simple *math*, in this case at
the secondary school level, and you can check that math by simple programs.

However, since you failed to understand it, and since I don't know how to
simplify it even more, I think that's that.


Cheers & hth.,

- ALf

 

[James Kanze]

You probably missed the beginning of this thread. The OP was
learning the basics; and was trying to write a simple program
that read and stored a list of numbers, then printed them
back.

Exactly. And the normal solution for that is std::vector.

The OP was trying to learn the basics of new/delete, thusly
the OP was allocating an array, for this purpose, from the
heap. Since doing that requires knowing the number of elements
in advance, the OP was reading the number of elements first,
allocating the array from the heap, populating the array, then
iterating over it, and printing back its contents. The OP also
asked for general points and tips.

Clearly. And the correct response to this is vector, unless
there are particular needs which suggest otherwise.

I pointed out that functionality similar results can be
obtained by using std::list.

The most similar functionality to a C style array allocated
dynamicly is std::vector. In general, std::vector is the
container one uses by default. There are, in practice, very,
very few cases where std::list is appropriate.

Additionally, that won't require getting beforehand the number
of elements in the array, in advance. Given that OP did not
require random access, I believe that std::list would be a
better choice.

Better than dynamically allocating a C style array, yes. But
nowhere near as good as using std::vector.