2
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.

2
  • А что не так с if constexpr, который по ссылке упоминается? Или вам нужно именно в С++11 это сделать? 7 июл 2018 в 11:50
  • Visual Studio ругается на использование C++17. Я сейчас пробую решить эту проблему, но хотелось бы стандарт не позже C++14, ибо не все тестирующие системы на контестах принимают новый стандарт. 7 июл 2018 в 11:53

2 ответа 2

4

Для эмулирования поведения 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);
}
3
  • Решение конечно очень классное и хитрое, спасибо, заодно узнал такой интересный прием. Правда наверно в данном конкретном случае быстрее и компактнее написать перегрузку. Без if constexpr не работает, как я понимаю, потому что на этапе компиляции list_type неизвестен и компилятор пытается подставить list в обе ветки? 7 июл 2018 в 12:44
  • @ВладСивирин list_type, как и любой другой параметр шаблона, известен на этапе компиляции. Без использования if constexpr обе ветки будут компилироваться. При известном результате is_same... вторая ветка потенциально может быть оптимизирована, но она все равно должна корректно компилироваться. Другими словами, с if constexpr сначала одна ветка отбрасывается, а потом оставшаяся компилируется, а без него обе ветки компилируются, и только потом одна из них может быть отброшена во имя оптимальности. 7 июл 2018 в 12:49
  • Спасибо, очень помогли с пониманием :) 7 июл 2018 в 13:02
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> вы не сможете. Лучше уж иметь пару перегруженных функций или подойти к вопросу с точки зрения иерархии классов. Или же написать шаблонную функцию, и ее частичную специализацию.

2
  • По поводу передачи matrix как константу согласен, спасибо. Но со списком вы неправы. Список смежности - двумерный vector< vector< int > > , я писал об этом. Каждый вложенный vector[i] исходного vector'а - список вершин, в которые существует путь из i-ой вершины. Поэтому мне нужно сначала проинициализировать list количеством вершин у всего графа, а потом уже для каждой вершины добавлять исходящие из нее другие вершины. Я тестировал эту функцию и она работает, как ожидается (кроме ветвления, в котором у меня возник вопрос). Перегрузить, безусловно, могу, просто было интересно сделать иначе. 7 июл 2018 в 12:58
  • тогда, тем более вам нужна специализация шаблона только для готовых списков , уже имеющие matrix.size() количество элементов, а не присваивать в функции. У вас может и работать, если как list_type вы передадите вами написанный специальный тип. Но в таком случаи как шаблонная функция, ваша функция еще больше теряет смысль.. 7 июл 2018 в 13:14

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.