dgrcode dgrcode - 4 years ago 95
C++ Question

Can I avoid copying an unordered_map in C++ in the following situation?

Context



I am trying to solve the Travelling Salesman Problem using a Dynamic Programming algorithm with C++. I am trying to solve the problem for 25 cities, meaning that I have to store up to 5 million key-value pairs in a
unordered_map
per iteration.

Using this algorithm with Python and 4GB ram I had my process killed due to lack of memory, so I'm trying to improve the performance in memory.

Problem



To reduce the amount of memory used, I am trying to keep two
unordered_set
, one with the values of the previous iteration, and another one with the new values.

std::unordered_map<std::string, int> costs;
std::unordered_map<std::string, int> new_costs;

for (int m = 1; m <= n; m++) {
new_costs.clear();
while (something) {
// I build the content of new_costs based on the content of costs
}

// Here I want to make costs point to new_costs and free new_costs to
// build the next iteration
costs = new_costs; // ??
}


I don't know if I can avoid copying all
new_costs
to
costs
as we are talking about millions of elements.

I was wondering if I could use pointers to make
costs
point to
new_costs
, but in that case I don't know what would happen when I do
new_costs.clear();
.

Question



Summing up my question is, how can I allocate new memory for
new_costs
, put the content of
new_costs
inside
costs
(hopefully in constant time?), and free the memory already used by the old
costs
that I will not use again?

Any help is really appreciated! Thanks!

-- Feel free to edit the title to make it more descriptive. I couldn't find a good title.

Answer Source

The best course of action is using standard functions. When you use std containers, using std::move or std::swap could be a good solution for your problem.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download