new int[size] vs std::vector

Question

To allocate dynamic memory, I have been using vectors all this time in C++. But recently, while reading some source code, I found the use of "new int[size]" and on some research, found that it too allocates dynamic memory.

Can anyone give me advice as to which is better? I am looking from an algorithmic and ICPC point of view?

Answer 1

Always prefer the standard containers. They have well-defined copying semantics, are exception safe, and release properly.

When you allocate manually, you must guarantee that the release code is executed, and as members, you must write correct copy assignment and copy constructor which does the right thing without leaking in case of exception.

Manual:

int *i = 0, *y = 0;
try {
    i = new int [64];
    y = new int [64];
} catch (...) {
    delete [] y;
    delete [] i;
}

If we want our variables to have only the scope they really need, it gets smelly:

int *i = 0, *y = 0;
try {
    i = new int [64];
    y = new int [64];
    // code that uses i and y
    int *p;
    try { 
        p = new int [64];
        // code that uses p, i, y
    } catch(...) {}
    delete [] p;
} catch (...) {}
delete [] y;
delete [] i;

Or just:

std::vector<int> i(64), y(64);
{
    std::vector<int> p(64);
}

It is a horror to implement that for a class that has copy semantics. Copying may throw, allocation may throw, and we want transaction semantics, ideally. An example would burst this answer tho.

---

Ok here.

Copyable class - Manual resource management vs containers

We have this innocent looking class. As it turns out, it is pretty evil. I feel reminded of American McGee's Alice:

class Foo {
public:
    Foo() : b_(new Bar[64]), f_(new Frob[64]) {}
private:
    Bar  *b_;
    Frob *f_;
};

Leaks. Most beginner C++ programmers recognize that there's missing deletes. Add them:

class Foo {
public:
    Foo() : b_(new Bar[64]), f_(new Frob[64]) {}
    ~Foo() { delete f_; delete b_; }
private:
    Bar  *b_;
    Frob *f_;
};

Undefined behavior. Intermediate C++ programmers recognize that the wrong delete-operator is used. Fix this:

class Foo {
public:
    Foo() : b_(new Bar[64]), f_(new Frob[64]) {}
    ~Foo() { delete [] f_; delete [] b_; }
private:
    Bar  *b_;
    Frob *f_;
};

Bad design, leaks and double deletes lurk there if the class is copied. The copying itself is fine, the compiler cleanly copies the pointers for us. But the compiler won't emit code to create copies of the arrays.

Slightly more experienced C++ programmers recognize that the Rule of Three was not respected, which says that if you have explicitly written any of destructor, copy assignment or copy constructor, you probably also need to write out the others, or make them private without implementation:

class Foo {
public:
    Foo() : b_(new Bar[64]), f_(new Frob[64]) {}
    ~Foo() { delete [] f_; delete [] b_; }

    Foo (Foo const &f) : b_(new Bar[64]), f_(new Frob[64])
    {
        *this = f;
    }
    Foo& operator= (Foo const& rhs) {
        std::copy (rhs.b_, rhs.b_+64, b_);
        std::copy (rhs.f_, rhs.f_+64, f_);
        return *this;
    }
private:
    Bar  *b_;
    Frob *f_;
};

Correct. ... Provided you can guarantee to never run out of memory and that neither Bar, nor Frob can fail on copying. Fun starts in next section.

The wonderland of writing exception safe code.

Construction

Foo() : b_(new Bar[64]), f_(new Frob[64]) {}

• Q: What happens if the initialization of f_ fails?
• A: All Frobs that have been constructed are destroyed. Imagine 20 Frob were constructed, the 21st will fail. Than, in LIFO order, the first 20 Frob will be correctly destroyed.

That's it. Means: You have 64 zombie Bars now. The Foos object itself never comes to life, its destructor will therefore not be called.

How to make this exception safe?

A constructor should always succeed completely or fail completely. It shouldn't be half-live or half-dead. Solution:

Foo() : b_(0), f_(0)
{
    try {    
        b_ = new Bar[64];
        f_ = new Frob[64];
    } catch (std::exception &e) {
        delete [] f_; // Note: it is safe to delete null-pointers -> nothing happens
        delete [] b_;
        throw; // don't forget to abort this object, do not let it come to life
    }
}

Copying

Remember our definitions for copying:

Foo (Foo const &f) : b_(new Bar[64]), f_(new Frob[64]) {
    *this = f;
}
Foo& operator= (Foo const& rhs) {
    std::copy (rhs.b_, rhs.b_+64, b_);
    std::copy (rhs.f_, rhs.f_+64, f_);
    return *this;
}

• Q: What happens if any copy fails? Maybe Bar will have to copy heavy resources under the hood. It can fail, it will.
• A: At the time-point of exception, all objects copied so far will remain like that.

This means that our Foo is now in inconsistent and unpredictable state. To give it transaction semantics, we need to build up the new state fully or not at all, and then use operations that cannot throw to implant the new state in our Foo. Finally, we need to clean up the interim state.

The solution is to use the copy and swap idiom (http://gotw.ca/gotw/059.htm).

First, we refine our copy constructor:

Foo (Foo const &f) : f_(0), b_(0) { 
    try {    
        b_ = new Bar[64];
        f_ = new Frob[64];

        std::copy (rhs.b_, rhs.b_+64, b_); // if this throws, all commited copies will be thrown away
        std::copy (rhs.f_, rhs.f_+64, f_);
    } catch (std::exception &e) {
        delete [] f_; // Note: it is safe to delete null-pointers -> nothing happens
        delete [] b_;
        throw; // don't forget to abort this object, do not let it come to life
    }
}

Then, we define a non-throwing swap function

class Foo {
public:
    friend void swap (Foo &, Foo &);
};

void swap (Foo &lhs, Foo &rhs) {
    std::swap (lhs.f_, rhs.f_);
    std::swap (lhs.b_, rhs.b_);
}

Now we can use our new exception safe copy-constructor and exception-safe swap-function to write an exception-safe copy-assignment-operator:

Foo& operator= (Foo const &rhs) {
    Foo tmp (rhs);     // if this throws, everything is released and exception is propagated
    swap (tmp, *this); // cannot throw
    return *this;      // cannot throw
} // Foo::~Foo() is executed

What happened? At first, we build up new storage and copy rhs' into it. This may throw, but if it does, our state is not altered and the object remains valid.

Then, we exchange our guts with the temporary's guts. The temporary gets what is not needed anymore, and releases that stuff at the end of scope. We effectively used tmp as a garbage can, and properly choose RAII as the garbage collection service.

You may want to look at http://gotw.ca/gotw/059.htm or read Exceptional C++ for more details on this technique and on writing exception safe code.

Putting it together

Summary of what can't throw or is not allowed to throw:

• copying primitive types never throws
• destructors are not allowed to throw (because otherwise, exception safe code would not be possible at all)
• swap functions shall not throw** (and C++ programmers as well as the whole standard library expect it to not throw)

And here is finally our carefully crafted, exception safe, corrected version of Foo:

class Foo {
public:
    Foo() : b_(0), f_(0)
    {
        try {    
            b_ = new Bar[64];
            f_ = new Frob[64];
        } catch (std::exception &e) {
            delete [] f_; // Note: it is safe to delete null-pointers -> nothing happens
            delete [] b_;
            throw; // don't forget to abort this object, do not let it come to life
        }
    }

    Foo (Foo const &f) : f_(0), b_(0)
    { 
        try {    
            b_ = new Bar[64];
            f_ = new Frob[64];

            std::copy (rhs.b_, rhs.b_+64, b_);
            std::copy (rhs.f_, rhs.f_+64, f_);
        } catch (std::exception &e) {
            delete [] f_;
            delete [] b_;
            throw;
        }
    }

    ~Foo()
    {
        delete [] f_;
        delete [] b_;
    }

    Foo& operator= (Foo const &rhs)
    {
        Foo tmp (rhs);     // if this throws, everything is released and exception is propagated
        swap (tmp, *this); // cannot throw
        return *this;      // cannot throw
    }                      // Foo::~Foo() is executed

    friend void swap (Foo &, Foo &);

private:
    Bar  *b_;
    Frob *f_;
};

void swap (Foo &lhs, Foo &rhs) {
    std::swap (lhs.f_, rhs.f_);
    std::swap (lhs.b_, rhs.b_);
}

Compare that to our initial, innocent looking code that is evil to the bones:

class Foo {
public:
    Foo() : b_(new Bar[64]), f_(new Frob[64]) {}
private:
    Bar  *b_;
    Frob *f_;
};

You better don't add more variables to it. Sooner or later, you will forget to add proper code at some place, and your whole class becomes ill.

Or make it non-copyable.

class Foo {
public:
    Foo() : b_(new Bar[64]), f_(new Frob[64]) {}
    Foo (Foo const &) = delete;
    Foo& operator= (Foo const &) = delete;
private:
    Bar  *b_;
    Frob *f_;
};

For some classes this makes sense (streams, for an instance; to share streams, be explicit with std::shared_ptr), but for many, it does not.

The real solution.

class Foo {
public:
    Foo() : b_(64), f_(64) {}
private:
    std::vector<Bar>  b_;
    std::vector<Frob> f_;
};

This class has clean copying semantics, is exception safe (remember: being exception safe does not mean to not throw, but rather to not leak and possibly have transaction semantics), and does not leak.

Answer 2

Can anyone give me advice as to which is better?

Vector is better when

1. You haven't learned to do manual memory management.
2. You have learned of it, but aren't confident yet.
3. You think you know how to do it, but are unwittingly overconfident.
4. You really know what you're doing, but might make a mistake.
5. You are a guru and none of the above applies, but your code might be later maintained by a colleague, for whom any of the above does apply.

...

999. Pretty much always.

---

Manual memory management can easily and often does lead to memory leaks, and worse yet, undefined behaviour.

Answer 3

In just about any situation, std::vector is preferable. It has a destructor to free the memory, whereas manually managed memory must be explicitly deleted once you've finished with it. It is very easy to introduce memory leaks, for example if something throws an exception before it is deleted. For example:

void leaky() {
    int * stuff = new int[10000000];
    do_something_with(stuff);
    delete [] stuff; // ONLY happens if the function returns
}

void noleak() {
    std::vector<int> stuff(10000000);
    do_something_with(stuff);
} // Destructor called whether the function returns or throws

It is also more convenient if you need to resize or copy the array.

The only reason to prefer a raw array is if you have extreme performance or memory limitations. vector is a larger object than a pointer (containing size and capacity information); and it will sometimes value-initialise its objects, while a raw array will default-initialise them (which, for trivial types, means they are left uninitialised).

In the rare cases when these issues might be important, you should consider std::unique_ptr<int[]>; it has a destructor which will prevent memory leaks, and has no run-time overhead when compared to a raw array.

Answer 4

Even though both methods allocates dynamic memory, one is an object made for handling data of arbitrary length (std::vector<T>), while the other is just a pointer to a sequential line of memory slots of size N (ints in this case).

---

Among other differences

• A std::vector<T> will automatically resize the allocated memory for your data if you try to append a new value and it runs out of space. A int * will not.

• A std::vector<T> will free the allocated memory when the vector goes out of scope, a int * will not.

• A int * will have little to no overhead (compared to the vector), though std::vector<T> isn't exactly a new thing and is normally very optimized. Your bottle neck will probably be elsewhere.

  But a std::vector<int> will always consume more memory than a int *, and some operations will always take a little more time.

  So if there are memory/CPU limitations and you want to shave off every single cycle that you possible can.. use an int *.

---

There are situations where one is definitely preferable over the other!

• When you need "raw"/"real" memory and full control over it, operator new is your best bet.

  For example when you are using placement new.

  ^{by raw/real memory I mean something that is not managed through a wrapper-container, such as std::vector<T>.}

• When you are looking for a container to handle arbitrary and don't want to reinvent the wheel regarding memory management; std::vector<T> (or any other appropriate STL container)

Answer 5

If you need a dynamically sized sequence of objects, use a vector. If you need to allocate raw memory and manage that memory yourself, allocate memory. You will find that sometimes vectors are more useful, and at other times a flat memory buffer is better.

Answer 6

Internally the vector do exactly the same also it will make care about the memory release. So there is no any reason to use the new operator. std::vector is a part of c++, it is standard, it is tested and it is safe, don't use the raw pointer when you have some standard way to do your work.

Answer 7

I don't think that there's ever a case where new int[size] is preferable. You'll sometimes see it in pre-standard code, but even then, I don't think it was ever a good solution; in pre-standard days, if you didn't have an equivalent to std::vector in your tool kit, you wrote one. The only reasons you might want to use a new int[size] is in the implementation of a pre-standard vector class. (My own separated allocation and initialization, like the containers in the standard library, but this might be overkill for a very simple vector class.)