Сортировка вставками: что я делаю не так?

Я пытаюсь сделать сортировку вставками. Песня представляет собой простую структуру, содержащую свойства Artist и Title. Я вызываю функцию CompareTitle(Song&s1, Song&s2), которая возвращает true, если название первой песни стоит перед названием второй песни. Условие сортировки работает нормально, когда закомментированная часть кода заменяется. Когда нет, я получаю эту ошибку. Я не уверен, как к этому подойти:

playlist.cc:192:22: ошибка: объект типа «Песня» не может быть назначен, потому что его копирующий оператор присваивания неявно удален *itr = j;

//do insertion sort
for(auto itr = newSongList.begin(); itr != newSongList.end(); ++itr)
{

    for(auto jtr=itr; jtr != newSongList.begin(); --jtr){
        cout << itr->GetTitle() << " " << jtr->GetTitle() << endl;
        // if s1 is not before s2 then swap them
        if(!Song::CompareTitle(*itr, *jtr)){
            cout << "Swap True (" << itr->GetTitle() << "," << jtr->GetTitle() << " )"<< endl;
            Song i = Song(itr->GetTitle(),itr->GetArtist());
            Song j = Song(jtr->GetTitle(), jtr->GetArtist());

            *itr = j;
            *jtr = i;

            cout << "Swap After (" << jtr->GetTitle() << "," << itr->GetTitle() << endl;
        }
    }
}

Ниже представлена ​​структура песни и плейлиста:

#ifndef PLAYLIST_H
#define PLAYLIST_H

#include <functional>   // For std::function
#include <string>
#include <list>

using namespace std;

extern void SongCallback();

class Song {
  public:
    explicit Song(const string& title, const string& artist,
        const function<void()> = &SongCallback);
        const string& GetTitle() const;
        const string& GetArtist() const;
        bool operator==(const Song& s) const;
        bool operator()(const Song& s) const;

        static bool CompareTitle(const Song& s1, const Song& s2);
        static bool CompareArtistTitle(const Song& s1, const Song& s2);

private:
    const string title_;
    const string artist_;
    const function<void()> callback_;
};

class Playlist {
public:
    explicit Playlist() {}
    void AddSong(const string& title, const string& artist);
    unsigned int RemoveSongs(const string& title, const string& artist);
    list<Song> PlaylistSortedByTitle() const;
    list<Song> PlaylistSortedByArtistTitle() const;
    unsigned int NumSongs() const;
    unsigned int NumSongs(const string& artist) const;

private:
    list<Song> songs_;
};

#endif // PLAYLIST_H

c++ insertion-sort
person Potion    schedule 18.05.2018    source источник
comment
Мы не знаем, какой тип у newSongList, но вставки делают недействительными все итераторы в std::vector.   -  person FBergo    schedule 18.05.2018
comment
@FBergo, извините, newSongList - это список «Песня». Песни заполняются нажатием песни с помощью конструктора Song(string title, string artist). Я также добавил этот метод в свое редактирование.   -  person Potion    schedule 18.05.2018
comment
Ваш код подкачки вставляет 2 элемента и не удаляет ни одного. Вместо этого рассмотрите std::swap(*itr, *jtr);.   -  person FBergo    schedule 18.05.2018
comment
Пробовали использовать отладчик?   -  person BessieTheCookie    schedule 18.05.2018
comment
@FBergo К сожалению, я не могу использовать это, так как все мои методы константны. Оно будет жаловаться на это.   -  person Potion    schedule 18.05.2018
comment
@FeiXiang да, я сузил его до обмена. Я не могу поменять местами, как было предложено ранее, потому что я получаю сообщение об ошибке «ошибка: объект типа «Песня» не может быть назначен, потому что его оператор присваивания копирования неявно удален   -  person Potion    schedule 18.05.2018
comment
Все мои методы являются константами, вы имеете в виду включение вашей функции сортировки? Как функция должна сортировать данные, если она не может изменить объект? Можем ли мы увидеть класс Song? Похоже, вы не создали оператор присваивания копии, когда он вам был нужен. Пожалуйста, предоставьте код, который мы можем использовать для воспроизведения проблемы.   -  person BessieTheCookie    schedule 18.05.2018
comment
@FeiXiang, это правильно. Я бы предположил, что если бы я сделал копию списка воспроизведения (newSongList) и отсортировал оттуда и вернул этот новый список, все было бы хорошо. Я также обновил код, чтобы показать структуру.   -  person Potion    schedule 18.05.2018

Ответы (2)


arrow_upward
1
arrow_downward

Казалось бы, каждый раз, когда вы должны менять местами два элемента итератора, вместо этого вы добавляете элементы в контейнер перед itr и jtr.

for(auto itr = newSongList.begin(); itr != newSongList.end(); ++itr)
{

    for(auto jtr=itr; jtr != newSongList.begin(); --jtr){
        cout << itr->GetTitle() << " " << jtr->GetTitle() << endl;
        // if s1 is not before s2 then swap them
        if(!Song::CompareTitle(*itr, *jtr)){
            swap(*itr, *jtr);
        }
    }
}

Здесь вы можете либо использовать std::swap в качестве функции подкачки, либо написать свою собственную функцию для переключения названий и исполнителей песен вместе с любыми другими элементами, которые могут быть к ним добавлены. std::iter_swap также можно использовать в качестве альтернативы.

std::swap ссылка на CPP

std::iter_swap ссылка на CPP

person Quinn Mortimer    schedule 18.05.2018
comment
Я не могу использовать std::swap или std::iter_swap, так как все мои методы константны. - person Potion; 18.05.2018
comment
Хотелось бы, чтобы это было указано в вопросе ранее. Я чувствую, что ответил на вопрос, как было изначально заявлено, но недавние изменения внесли дополнительные сложности. - person Quinn Mortimer; 18.05.2018
comment
Если метод не является Const, это правильно. Поскольку в моем первоначальном вопросе это не указывалось, я выберу этот ответ как подходящий, поскольку он отвечает на мой вопрос, спасибо. - person Potion; 22.05.2018

arrow_upward
0
arrow_downward

Поскольку у вас есть параметры const title_ и artist_, вы не можете назначать и перезаписывать их с помощью assignment operator.

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

Вместо этого я думаю, что вы можете манипулировать записями списка, используя list::insert и list::erase, как я показал ниже для достижения желаемого результата.

for(auto itr = newSongList.begin(); itr != newSongList.end(); ++itr)
{

    for(auto jtr=itr; jtr != newSongList.begin(); --jtr){
        cout << itr->GetTitle() << " " << jtr->GetTitle() << endl;
        // if s1 is not before s2 then swap them
        if(!Song::CompareTitle(*itr, *jtr)){
            cout << "Swap True (" << itr->GetTitle() << "," << jtr->GetTitle() << " )"<< endl;
            Song i = Song(itr->GetTitle(),itr->GetArtist());
            Song j = Song(jtr->GetTitle(), jtr->GetArtist());

            newSongList.insert(itr, j); // extend list by inserting j song before itr song
            newSongList.erase(itr);     // itr is still pointing to original song
            newSongList.insert(jtr, i); // extend list by inserting i song before jtr song
            newSongList.erase(jtr);     // jtr is still pointing to original song

            cout << "Swap After (" << jtr->GetTitle() << "," << itr->GetTitle() << endl;
        }
    }
}
person Saeed    schedule 18.05.2018