插入排序:我做错了什么?

Question

我正在尝试进行插入排序。歌曲是包含艺术家和标题属性的简单结构。我称之为CompareTitle(Song&s1，Song&s2(，如果第一首歌曲的歌曲标题在第二首歌曲的标题之前，则返回true。当代码的交换部分被注释掉时，排序条件似乎工作正常。如果没有，我会收到此错误。我不确定如何处理它：

playlist.cc：192：22：错误：无法分配类型为"Song"的对象，因为其复制赋值运算符被隐式删除 *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

Answer 1

似乎每次您应该交换两个元素的迭代器时，您都在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也可以用作替代方案。

关于CPP参考std::swap

关于CPP参考std::iter_swap

Answer 2

由于您有常量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;
}
}
}