Ошибка ветвления в шаблонной функции

182

27 августа 2018, 09:10

template <typename matrix_type, typename list_type>
void matrix_to_list(matrix_type& matrix, list_type& list)
{
    if (list.size() == 0) 
        list = list_type(matrix.size());
    for (size_t i = 0; i < matrix.size(); ++i)
    {
        for (size_t j = 0; j < matrix[i].size(); ++j)
        {
            if (matrix[i][j])
            {
                if (is_same< list_type, vector< vector< pair<int, int> > > >::value)
                    list[i].push_back(pair<int, int>(j, matrix[i][j]));
                else
                    list[i].push_back(j);
            }
        }
    }
}

Пишу функцию преобразования матрицы смежности в список смежности (для графов). Т.к. для взвешенных и невзвешенных графов списки смежности имеют разные типы (vector< vector< int > > и vector< vector< pair< int, int > > >), но в целом схема перехода из матрицы в список практически идентична, захотелось написать одну шаблонную функцию, вместо перегрузок. Однако компилятор ругается:

Ошибка C2664 "void std::vector<int,std::allocator<_Ty>>::push_back(_Ty &&)": невозможно преобразовать аргумент 1 из "std::pair<int,int>" в "const int &"

Можно ли что-то с этим сделать или лучше написать перегрузку? (P.S. сначала я в функцию передавал флаг weighted и ветвление делал от него и изначально шел именно с этим вопросом, но stackoverflow предложил вот это решение, но оно не помогло). Пишу в Visual Studio 2017.

Answer 1

Для эмулирования поведения if constexpr в более старых версиях стандарта можно написать шаблон функции с частичными специализациями. Для эмулирования частичных специализаций для шаблонов функций (которые до сих пор запрещены) можно написать шаблон класса со статической функцией:

template <typename matrix_type, typename list_type, typename x_enabled = void> class
push_to_list_impl final
{
    public: static void
    Do(size_t const i, size_t const j, matrix_type const & matrix, list_type & list)
    {
         list[i].emplace_back(j);
    }
};
template <typename matrix_type, typename list_type> class
push_to_list_impl
<
    matrix_type
,   list_type
,   typename ::std::enable_if
    <
        ::std::is_same
        <
            list_type
        ,   ::std::vector<::std::vector<::std::pair<int, int>>>   
        >::value          
    >::type
> final
{
    public: static void
    Do(size_t const i, size_t const j, matrix_type const & matrix, list_type & list)
    {
         list[i].emplace_back(j, matrix[i][j]);
    }
};

…

if (matrix[i][j])
{
    push_to_list_impl<matrix_type, list_type>::Do(i, j, list, matrix);
}

Answer 2

template <typename matrix_type, typename list_type>
void matrix_to_list(const matrix_type& matrix, list_type& list)
{

функция не модифицирует matrix, потому нужно передавать его как константный. Дальше:

if (list.size() == 0) 
    list = list_type(matrix.size());

Здесь вы игнорируете имеющийся список(последовательность), присвоив его обьект с размером матрицы, и весь этот список не инициализируете, а ...

for (size_t i = 0; i < matrix.size(); ++i)
{
    for (size_t j = 0; j < matrix[i].size(); ++j)
    {
        if (matrix[i][j])
        {
            if (is_same< list_type, vector< vector< pair<int, int> > > >::value)
                list[i].push_back(pair<int, int>(j, matrix[i][j]));
            else
                list[i].push_back(j);

добавляете в конец имеющийся неинициализированной списке еще matrix.size() * matrix[i].size()

Т.е. если матрица имеет размер n*m, то у вас получится список размера n*m + n*m*m, где первые n*m неинициализированные, а значения остальных не то что вам нужно...
Все нужно исправить.

Во вторых, смысль этой шаблонной функции непонятен, поскольку ваша матрица должна содержать элементы только одного типа(типа int). Передать в шаблонную функцию контейнер, содержащийся элементы с типом отличающимся от int или pair<int, int> вы не сможете. Лучше уж иметь пару перегруженных функций или подойти к вопросу с точки зрения иерархии классов. Или же написать шаблонную функцию, и ее частичную специализацию.