mardi 9 février 2021

What's the problem of saving pointer of vector inside std::map

I am trying to find the best sum with memorization, but when saving the vector pointer inside a map the values keep appending inside the vector and getting the wrong vector. if I commented out the map insertion it works properly. saving nullptr is not possible in case trying to save vector inside the map by reference.

std::vector<int> *bestSumV(int target, int nums[], int size) {

  static std::map<int, std::vector<int> *> memo;

  if (memo.find(target) != memo.end())
    return memo.at(target);

  if (target == 0)
    return new std::vector<int>();

  if (target < 0)
    return NULL;

  std::vector<int> *bestCom = nullptr;

  for (int i = 0; i < size; i++) {

    int reminder = target - nums[i];

    std::vector<int> *reminderResult = bestSumV(reminder, nums, size);

    if (reminderResult != NULL) {

      reminderResult->push_back(nums[i]);

      if (bestCom == nullptr || reminderResult->size() < bestCom->size()) {
        bestCom = static_cast<std::vector<int> *>(reminderResult);
      }
    }
  }
  // if i commented out the map insertion i am getting the correct value
  // and getting a vector of 5 items

  memo.insert(std::make_pair(target, std::move(bestCom)));

  return bestCom;
}

void runHowbestTest() {

  int testArray[] = {5, 4, 2};

  std::vector<int> *bestSum25 = bestSumV(25, testArray, 3);

  for (int i = 0; i < bestSum25->size(); i++) {
    std::cout << "the items  " << bestSum25->at(i) << std::endl;
  }
}

Aucun commentaire:

Enregistrer un commentaire