Блог

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

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

 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 clockn";
    exit(1);
    }

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

    exit(2);
    }

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

}

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> resu< 
    for (int i = 0; i < num_elts; i  ) {
    double datum = 1.0*rand()/RAND_MAX; 
    result.push_back(datum);
    }
    return resu<
}

// 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 << "sortedn";  
} 
  

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

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

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

Ваша шаблонная функция 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;  
}
  

Я не уверен, что вы получите empty ranges…so это может быть отвлекающим маневром.

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

     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");
}
  

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

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