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.