Функция может быть вызвана только один раз в основной

Question

По какой-то причине функцию check_sort можно вызывать в основной функции только один раз, в противном случае рабочий процесс останавливается после первого выполнения.

Например. Выход заканчивается в:

How many elements for container? 5000
Check: list is sorted
Elapsed time: 0.32 seconds

Вместо продолжения вроде:

How many elements for next container? 5000
Check: list is sorted
Elapsed time: 0.30 seconds
Check: set is sorted
Elapsed time: 0.01 seconds
Check: vector is sorted
Elapsed time: 0.25 seconds

Полная программа ниже:

#include <cmath>
#include <iterator>
#include <iostream>
#include <iomanip>
#include <vector>
#include <ctime>
#include <list>
#include <set>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef void Inserter(vector<double>);

vector<double> gen_data(int num_elts);
void insert_list(vector<double> data);
void insert_set(vector<double> data);
void insert_vector(vector<double> data);

void time_insert( Inserter inserter, vector<double> data);

template <class Iter> bool is_sorted(Iter first, Iter last);
template <class Iter> void check_sort(Iter first, Iter last, string cont_kind);

list<double> l;
set<double> s;
vector<double> v;

int main() {
    srand(time(0));// initialize random number generator
    cout << "How many elements for container? ";
    int num_elts = 0;

    while (cin >> num_elts) {
    if (num_elts <= 0)
        cout << "Error, should be > 1";
    else {
        vector<double> data = gen_data(num_elts);

        check_sort(l.begin(), l.end(), "list");
        time_insert(insert_list, data);
        check_sort(s.begin(), s.end(), "set");
        time_insert(insert_set, data);
        check_sort(v.begin(), v.end(), "vector");
        time_insert(insert_vector, data);

    }
    cout << "\nHow many elements for next container? ";

    }
    return 0;

} 
void time_insert( Inserter inserter, vector<double> data) {
    clock_t t1 = clock();
    if (t1 == clock_t(-1)) { //if clock() doesn’t work
    cerr << "sorry, no clock\n";
    exit(1);
    }

    inserter(data);
    clock_t t2 = clock(); 
    if (t2 == clock_t(-1)) {
    cerr << "sorry, clock overflow\n";

    exit(2);
    }

    cout << "Elapsed time: " << fixed << setprecision(2)
     << double(t2-t1)/CLOCKS_PER_SEC << " seconds\n";

}

class Larger_than { 
    double v;
public: 
    Larger_than(double vv) : v(vv){}
    bool operator()(double x) const {return x>v;}
};

// Sorts and then inserts data into a list
void insert_list(vector<double> data)
{
    list<double> l;
    for(int i=0; i < data.size(); i++){
    list<double>::iterator p = find_if(l.begin(),l.end(), Larger_than(data[i]));
    l.insert(p, data[i]);
    }
} 
// Sorts and then inserts data into a list
void insert_set(vector<double> data)
{
    set<double> s; 
    for(int i=0; i < data.size(); i++){
    set<double>::iterator p = find_if(s.begin(),s.end(), Larger_than(data[i]
                          ));
    s.insert(p, data[i]);
    }
} 
// Sorts and then inserts data into a list 
void insert_vector(vector<double> data)
{
    vector<double> v; 
    for(int i=0; i < data.size(); i++){
    vector<double>::iterator p = find_if(v.begin(),v.end(), Larger_than(data
                                        [i]));
    v.insert(p, data[i]);
    }
} 

// generate num_elts random numbers in the range [0.0, 1.0), 
// which are returned in a vector

vector<double> gen_data (int num_elts) 
{
    vector<double> result; 
    for (int i = 0; i < num_elts; i++) {
    double datum = 1.0*rand()/RAND_MAX; 
    result.push_back(datum);
    }
    return result;
}

// is container spanned by [from, last) sorted?  
template <class Iter> bool is_sorted(Iter first, Iter last)  
{  
    Iter next = first;                   // next element  
    for (next++; next != last; next++, first++) {  
    if (*first > *next)  
        return false;  
    }  
    return true;  
}  

// prints a msg describing container kind, as well as whether container  
// spanned by [from, last) is sorted  
template <class Iter> void check_sort(Iter first, Iter last, string cont_kind)  
{  
    cout << "Check: " << cont_kind << " is ";  
    if (!is_sorted(first, last)) cout << "not ";  
    cout << "sorted\n";  
} 

Answer 1

Я не знаю, является ли это частью вашей проблемы, но is_sorted работает неправильно, если first - конец контейнера. next увеличивается на единицу за end и встречается неопределенное поведение.

РЕДАКТИРОВАТЬ: На самом деле это определенно так: вы не заполняете контейнеры vector / list / set до вызова для них функции проверки. Даже если вы вызывали функции вставки до , вызывая функцию проверки, она все равно не сработала бы, потому что каждая функция insert_* объявляет локальный элемент для заполнения, который затеняет глобальную переменную, которую вы пытаетесь заполнить.

EDIT2: в insert_set find_if фактически делает ваш код менее производительным, чем он должен быть. Вы должны просто использовать std::set::insert и позволить ему использовать встроенную сортировку, которая будет более эффективной, чем find_if, потому что она знает реализацию базового set.

Answer 2

Ваша функция шаблона is_sorted() не проверяет должным образом, равен ли first значение last перед увеличением next, которое является копией first:

template <class Iter> bool is_sorted(Iter first, Iter last)  
{  
    Iter next = first;                   // next element  
    for (next++; next != last; next++, first++) {  
        if (*first > *next)  
            return false;  
    }  
    return true;  
}

Это может привести к проблемам, если вы перебираете пустой диапазон, я думаю.

template <class Iter> bool is_sorted(Iter first, Iter last)  
{  
    if (first == last)
        return false;
    for (Iter next = first+1; next != last; next++, first++)
    {  
        if (*first > *next)  
            return false;  
    }  
    return true;  
}

Я не уверен, что вы получаете пустые диапазоны ... так что это может быть красная сельдь.

Поскольку вы не устанавливаете список перед проверкой его сортировки (и не проверяете, сортируется ли он после вставки данных), вы сталкиваетесь с проблемами с пустыми диапазонами. Вам необходимо изменить последовательность операций вставки и проверки:

    vector<double> data = gen_data(num_elts);
    time_insert(insert_list, data);
    check_sort(l.begin(), l.end(), "list");
    time_insert(insert_set, data);
    check_sort(s.begin(), s.end(), "set");
    time_insert(insert_vector, data);
    check_sort(v.begin(), v.end(), "vector");

---

Вы должны избегать дублирования кода в вашем основном цикле, вызывая функцию, чтобы получить количество элементов для обработки. Также обычно сообщают об ошибках на cerr.

static int get_num_elts()
{
    int num_elts;
    cout << "How many elements for container? ";
    cin >> num_elts;
    if (num_elts < 1)
        cerr << "Error: number should be >= 1" << endl;
    return num_elts;
}


...
int num_elts;

while ((num_elts = get_num_elts()) > 0)
{
    vector<double> data = gen_data(num_elts);
    time_insert(insert_list, data);
    check_sort(l.begin(), l.end(), "list");
    time_insert(insert_set, data);
    check_sort(s.begin(), s.end(), "set");
    time_insert(insert_vector, data);
    check_sort(v.begin(), v.end(), "vector");
}

Answer 3

Ваш код не входит в тело цикла в функции is_sorted

вместо for (next++; next != last; next++, first++) до for (next; next != last; next++, first++). Потому что если первый == последний, то это будет проблемой, и это то, с чем вы сталкиваетесь. Но не увеличение следующего указателя не принесет вреда, так как первое сравнение будет сравнивать первый элемент с самим собой, который всегда будет оцениваться как ложный в большей степени, чем сравнение с самим собой.