Реализация таблицы памятки с картой на основе пары int, int и int

Question

Я реализовал рекурсивный алгоритм, для повышения производительности я хочу добавить таблицу памятки. Наиболее естественной структурой для моей проблемы будет

map<pair<int,int>,int> lookup_table;

и рекурсивный алгоритм, который я использую:

int max_sum_path(int maximum_rows,vector<vector<int> >& matrix,int row_index,int colm_index)
{
  if(row_index >= maximum_rows || colm_index > row_index)
  {
    //we have reached a cell outside the Triangular Matrix
    return 0;
  }
  else if(lookup_table.find(row_index,colm_index) != lookup_table.end())
  {
    //the memoization step to avoid repeated calculations and make recursion more efficient
    return lookup_table[row_index,colm_index];
  }
  else
  {
    lookup_table[row_index,colm_index] = matrix[row_index][colm_index] + max(max_sum_path(maximum_rows,matrix,row_index+1,colm_index), max_sum_path(maximum_rows,matrix,row_index+1,colm_index+1));
    return lookup_table[row_index,colm_index];
  }
}

Это создает кучу ошибок компиляции. Я не уверен, что синтаксис правильный. Должен ли я использовать строковый буфер для создания строки, а затем использовать ее вместо пары?

Вот ошибки компилятора:

sums_triangle.cpp: In function ‘int max_sum_path(int, std::vector<std::vector<int> >&, int, int)’:
sums_triangle.cpp:50:49: error: no matching function for call to ‘std::map<std::pair<int, int>, int>::find(int&, int&)’
sums_triangle.cpp:50:49: note: candidates are:
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:736:7: note: std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const key_type&) [with _Key = std::pair<int, int>, _Tp = int, _Compare = std::less<std::pair<int, int> >, _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<const std::pair<int, int>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:736:7: note:   candidate expects 1 argument, 2 provided
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:751:7: note: std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const key_type&) const [with _Key = std::pair<int, int>, _Tp = int, _Compare = std::less<std::pair<int, int> >, _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<const std::pair<int, int>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:751:7: note:   candidate expects 1 argument, 2 provided
sums_triangle.cpp:53:35: warning: left operand of comma operator has no effect [-Wunused-value]
sums_triangle.cpp:53:45: error: no match for ‘operator[]’ in ‘lookup_table[(0, colm_index)]’
sums_triangle.cpp:53:45: note: candidate is:
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:445:7: note: std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>, _Tp = int, _Compare = std::less<std::pair<int, int> >, _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int, std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:445:7: note:   no known conversion for argument 1 from ‘int’ to ‘const key_type& {aka const std::pair<int, int>&}’
sums_triangle.cpp:57:28: warning: left operand of comma operator has no effect [-Wunused-value]
sums_triangle.cpp:57:38: error: no match for ‘operator[]’ in ‘lookup_table[(0, colm_index)]’
sums_triangle.cpp:57:38: note: candidate is:
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:445:7: note: std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>, _Tp = int, _Compare = std::less<std::pair<int, int> >, _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int, std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:445:7: note:   no known conversion for argument 1 from ‘int’ to ‘const key_type& {aka const std::pair<int, int>&}’
sums_triangle.cpp:58:35: warning: left operand of comma operator has no effect [-Wunused-value]
sums_triangle.cpp:58:45: error: no match for ‘operator[]’ in ‘lookup_table[(0, colm_index)]’
sums_triangle.cpp:58:45: note: candidate is:
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:445:7: note: std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>, _Tp = int, _Compare = std::less<std::pair<int, int> >, _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int, std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.6.2/../../../../include/c++/4.6.2/bits/stl_map.h:445:7: note:   no known conversion for argument 1 from ‘int’ to ‘const key_type& {aka const std::pair<int, int>&}’
sums_triangle.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]

Просто чтобы прояснить, я не уверен, что синтаксис правильный. Я хочу знать, как я могу использовать пару в качестве ключа для карты.

Дополнительная информация: Я задавал этот вопрос ранее. Я оптимизирую это сейчас. Не стесняйтесь предложить другую структуру для таблицы памятки.

Answer 1

Вместо этого

lookup_table.find(row_index,colm_index) //incorrect - your code

напишите это,

lookup_table.find(std::make_pair(row_index,colm_index)) //correct - my code

Аналогичным образом посмотрите также,

lookup_table[row_index,colm_index];  //incorrect  - your code
lookup_table[std::make_pair(row_index,colm_index)]; //correct - my code

Объяснение:

Поскольку lookup_table равно std::map<std::pair<int,int>,int>, его тип ключа равен std::pair<int,int>, поэтому при использовании оператора [] ключом должен быть индекс lookup_table.

std::make_pair являетсяслужебная функция, которая возвращает объект типа std::pair<int,int>, если оба аргумента std::make_pair равны int.Вместо записи std::make_pair вы можете использовать std::pair<int,int>(row_index,colm_index), но это выглядит громоздко, поэтому предпочтительным является std::make_pair.

Answer 2

Вы не можете получить доступ к map<pair<int,int>,int>, используя lookup_table[row_index,colm_index] и find(row_index,colm_index). Чтобы получить к нему доступ, нужно создать пару из двух целых.

Answer 3

Храните row_index и colm_index в std::pair:

pair<int, int> map_key_value = std::make_pair(row_index, colm_index);

Затем используйте map_key_value в lookup_table.find() и lookup_table[].

Answer 4

К сожалению, это не питон.Вы не можете использовать этот синтаксис:

lookup_table[row_index,colm_index]

Вам нужно использовать make_pair () для создания пары:

lookup_table[std::make_pair(row_index,colm_index)]

Кроме этого, вам, вероятно, следует использовать итератор, возвращенный изmap.find (), чтобы вернуть ваш запомненный результат.В нынешнем виде вы делаете поиск дважды.