CODEWITHSUNDEEP
c++algorithmmemorymemory-managementunordered-map
Daniel Reina
Daniel Reina

Reputation: 6347

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.

Upvotes: 0

Views: 550

Answers (1)

Sam Mokari
Sam Mokari

Reputation: 471

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.

Upvotes: 5

Related Questions