使用以 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,int>，它的键类型是 std::pair，因此当您使用时，lookup_table 的索引必须是它的键[] 运算符。

std::make_pair 是一个实用函数，如果两个参数都为 std::make_pair，则返回一个 std::pair 类型的对象code> 是 int。您可以使用 std::pair(row_index,colm_index) 而不是编写 std::make_pair，但这看起来很麻烦，这就是为什么std::make_pair 是首选。

Answer 2

不幸的是这不是Python。
您不能使用此语法：

lookup_table[row_index,colm_index]

您需要使用 make_pair() 来创建对：

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

除此之外，您可能应该使用从 map.find() 返回的迭代器来返回您的记忆结果。就目前而言，您要进行两次查找。

Answer 3

将 row_index 和 colm_index 存储在 std::pair 中：

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

然后在 lookup_table.find 中使用 map_key_value () 和 lookup_table[]。

Answer 4

您无法使用 lookup_table[row_index,colm_index] 和 find(row_index,colm_index) 访问 map,int> >。要访问它，您必须创建一对两个整数。