CODEWITHSUNDEEP
c++
Jackie
Jackie

Reputation: 1121

Vector versus dynamic array, does it make a big difference in speed?

Now I am writing some code for solving vehicle routing problems. To do so, one important decision is to choose how to encode the solutions. A solution contains several routes, one for each vehicle. Each route has a customer visiting sequence, the load of route, the length of route. To perform modifications on a solution the information, I also need to quickly find some information.

For example,
Which route is a customer in?
What customers does a route have?
How many nodes are there in a route?
What nodes are in front of or behind a node?

Now, I am thinking to use the following structure to keep a solution.

struct Sol
{
    vector<short> nextNode;   // show what is the next node of each node;
    vector<short> preNode;    //show what is the preceding node
    vector<short> startNode; 
    vector<short> rutNum;
    vector<short> rutLoad;
    vector<float> rutLength;
    vector<short> rutSize;
};

The common size of each vector is instance dependent, between 200-2000.

I heard it is possible to use dynamic array to do this job. But it seems to me dynamic array is more complicated. One has to locate the memory and release the memory. Here my question is twofold.

How to use dynamic array to realize the same purpose? how to define the struct or class so that memory location and release can be easily taken care of?

Will using dynamic array be faster than using vector? Assuming the solution structure need to be accessed million times.

Upvotes: 2

Views: 10049

Answers (3)

DanDan
DanDan

Reputation: 10562

I'm using MSVC and the implementation looks to be as quick as it can be.

Accessing the array via operator [] is:

return (*(this->_Myfirst + _Pos));

Which is as quick as you are going to get with dynamic memory.

The only overhead you are going to get is in the memory use of a vector, it seems to create a pointer to the start of the vector, the end of the vector, and the end of the current sequence. This is only 2 more pointers than you would need if you were using a dynamic array. You are only creating 200-2000 of these, I doubt memory is going to be that tight.

I am sure the other stl implementations are very similar. I would absorb the minor cost of vector storage and use them in your project.

Upvotes: 0

NPE
NPE

Reputation: 500457

It is highly unlikely that you'll see an appreciable performance difference between a dynamic array and a vector since the latter is essentially a very thin wrapper around the former. Also bear in mind that using a vector would be significantly less error-prone.

It may, however, be the case that some information is better stored in a different type of container altogether, e.g. in an std::map. The following might be of interest: What are the complexity guarantees of the standard containers?

It is important to give some thought to the type of container that gets used. However, when it comes to micro-optimizations (such as vector vs dynamic array), the best policy is to profile the code first and only focus on parts of the code that prove to be real -- rather than assumed -- bottlenecks.

Upvotes: 6

Mark B
Mark B

Reputation: 96261

It's quite possible that vector's code is actually better and more performant than dynamic array code you would write yourself. Only if profiling shows significant time spent in vector would I consider writing my own error-prone replacement. See also Dynamically allocated arrays or std::vector

Upvotes: 1

Related Questions