C++ 昇順でlistに入った数字を並び替える

Question

コンソールから正の整数を入力すると、それまで入力した数値が、小さい順に並べ替えて表示されるようなプログラムを作りなさい。-1が入力されたら、プログラムは終了するものとする。なお、それまで入力され続けていた数値は、listに格納し、適切な場所に挿入するようにすること。

という問題。。。

自分の書いたコード。。

#include<iostream>
#include<list>
#include<string>

using namespace std;
int main() {
	int n = 0;
	int temp;
	list <int> li;


		
	while (n != -1) {
		cout << "正の整数を入力";
		cin >> n;
		if (n == -1)break;
		li.push_back(n);
	}

	list<int>::iterator i1;
	list<int>::iterator j;
	for (i1 = li.begin(); i1 != li.end()--; i1++) {
		for (j = ++i1; j != li.end(); j++) {
			if (*i1 > * j) {
				temp = *i1;
				*i1 = *j;
				*j = temp;
			}
		}
	}
	for (i1 = li.begin(); i1 != li.end(); i1++) {
		cout << *i1 << "";
	}
}

昇順に並び替える方法は、以下のサイトなどを参照した。
https://webkaru.net/clang/array-sort-ascending-order/

コードに関しては、実行画面で、
[Expression:cannot increment end list iterator]
というエラーが出た。
コード自体にはエラーは無かった。

インクリメントで、どこがおかしいのか、わからなかったため、わかる方、ご教授ください。。

Answer 1

#include <iostream>
#include <list>
#include <string>

int main() {
    using namespace std;

    int n = 0;
    list <int> li;

    while ( true ) {
        cout << "正の整数を入力";
        cin >> n;
        if (n == -1) break;
        li.push_back(n);
    }

    li.sort(); // こんだけ。
 
    for ( int item : li ) {
        cout << item << " ";
    }
}

Comments

[big000]

解答ありがとうございました。

私が書いたコードで、誤ってる点はありますか。

[episteme]

> for (i1 = li.begin(); i1 != li.end()--; i1++)
li.end()-- ってなんだ? i1 != prev(li.end()) のマチガイか?

[majiponi]

内側のループでjを初期化するときに、i1をインクリメントしてるのがまずい。

Answer 2

    list<int>::iterator i1;
    list<int>::iterator j;
    for (i1 = li.begin(); i1 != li.end()--; i1++) {
        for (j = ++i1; j != li.end(); j++) {

この部分を次のように変えるとエラーになりません。

    list<int>::iterator i1, j, end = li.end();
    for (--end, i1 = li.begin(); i1 != end; ++i1) {
        for (j = i1; ++j != li.end(); ) {

しかし、この for文によるソートは選択ソートです。
課題は、挿入ソートを実装しなさいというものです。

#include<iostream>
#include<list>

using namespace std;

int main()
{
    list <int> li;
    while (true) {
        cout << "正の整数を入力 ";
        int n;
        cin >> n;
        if (!cin || n < 0) break;

        list<int>::iterator i1;
        for (i1 = li.begin(); i1 != li.end(); ++i1)
            if (n < *i1) break;
        li.insert(i1, n);
        for (i1 = li.begin(); i1 != li.end(); ++i1)
            cout << " " << *i1;
        cout << endl;
    }
}

Answer 3

適切な場所に挿入するようにすること

という文言から，題意的には，
「適当にlistにpush_backしておいて最後に１回ソートすればいいよね」という形ではなくて，
「listに各要素を入れる際に毎度入れるべき箇所に入れろ」という指定がなされているように思える．

std::list<int> li;
{
    while(true)
    {
        int n = -1;
        std::cin >> n;
        if (n == -1)break;

        //「適切な場所に挿入」ってのはこういうのを書けってことでは？
        li.insert(
            std::find_if( li.begin(), li.end(), [n](int v){ return (v>=n);  } ),
            n
        );
    }
}

//whileを抜けた時点で，昇順に並んでいる
for( int v : li ){  std::cout << v << " ";  }
return 0;

Comments

[episteme]

li.insert(std::upper_bouond(li.begin(), li.end(), n), n);
の方が多分速い♪

[fana]

常にソートされてるわけだから，２分探索が使えるということですね．