vector_sort.cpp

斯坦福Energy211/CME211课《c++编程——地球科学科学家和工程师》的课件

// This program reads a vector of positive integers, and then
// sorts them.  It asks whether the user wants to sort the
// entire sequence or only a portion of it, and it also asks
// whether it should sort in ascending or descending order.

// Then, it does the same with a vector of strings.

#include <algorithm>
#include <iostream>
#include <exception>
#include <vector>
#include <cctype>
#include <string>

// Always do this.  It's just easier.
using namespace std;

// Compare two objects of type T and return true if the first
// is less than the second
template<typename T> bool compare_ascending(T s1, T s2)
{
	return s1 < s2;
}

// Convert a string to lower case, using the tolower function
void makelower(string& s)
{
	for ( unsigned int i = 0; i < s.size(); i++ )
		s[i] = tolower(s[i]);
}

// This is a specialization of compare_ascending above.
// Compare two strings, but in a case-insensitive manner.
template<> bool compare_ascending<string>(string s1, string s2)
{
	makelower(s1);
	makelower(s2);
	return s1 < s2;
}

// Now, we add a similar function template for sorting in
// descending order...
template<typename T> bool compare_descending(T s1, T s2)
{
	return s1 > s2;
}

// ...with the same specialization
template<> bool compare_descending<string>(string s1, string s2)
{
	makelower(s1);
	makelower(s2);
	return s1 > s2;
}

// Sort the elements of the vector v, with the option of
// sorting only a (contiguous) portion of it, and the option
// of sorting in either ascending or descending order.

// Both start and finish must lie in the range 1 to n, where
// n is the number of elements in the vector.  Finish can be
// set to -1, which is interpreted as referring to the last
// element.

// The vector v must be passed by reference, because it will
// be modified (it is sorted "in-place").
template<typename T> void my_sort(vector<T>& v, int start = 1, int finish = -1, bool ascend = true)
{
	// For finish, we can't use a default value of v.size(),
	// because the compiler doesn't know about v at the point
	// where it sets default values.  Instead, we use the
	// out-of-bounds value -1 to indicate that we want to 
	// sort up to the end of the sequence of elements.
	
	// And here, we give finish a proper value.
	if ( finish == -1 )
		finish = v.size();
	// Make sure start and finish values are valid
	if ( finish > (int) v.size() || start < 0 )
		throw std::exception();
	// Perform the actual sort, based on the desired ordering.
	// begin() and end() are random access iterators, so we
	// can add values to them to refer to the start and finish
	// elements.  Note that at the start, we must subtract 1,
	// because arrays in C/C++ are zero-based.  However, for
	// the end of the vector, we do not subtract 1, because
	// the iterator representing the end actually refers to
	// the location AFTER the end, not the end itself.
	
	// Later, we'll learn how to pass a comparison function
	// as an argument, so that we don't have to hard-code
	// compare_ascending and compare_descending.
	if ( ascend )
		sort(v.begin() + start - 1, v.begin() + finish, 
			compare_ascending<T>);
	else
		sort(v.begin() + start - 1, v.begin() + finish, 
			compare_descending<T>);
}

// This handy function restores cin to a working state so we
// can continue reading from it.  It should only be called
// if we know that cin == false.
void reset_cin()
{
	cin.clear();
	string s;
	getline(cin, s);
}

// Another handy function, that prompts the user for an
// integer within a specified range, reads the integer
// (retrying if invalid input is given) and returns it
int get_int_in_range(int i1, int i2, string name)
{
	int value;
	bool valid = false;
	do
	{
		// Prompt the user, specifying the valid range
		// of values
		cout << "Enter " << name << " index (";
		cout << i1 << "-" << i2 << "): ";
		cin >> value;
		// If bad input is given, clean up cin to try again
		if (!cin)
			reset_cin();
		else if (value >= i1 && value <= i2)
			valid = true;  // Value is in range
		else  // We read an integer, but it's out of bounds
			cout << "Value out of range!" << endl;
		// Continue iterating until we get what we want
	} while (!valid);
	// Finally, we're done
	return value;
}

// Yet another handy function that asks the user a question,
// and reads a yes or no answer (actually, y or n, or Y or N)
// The function returns true if the answer is yes.
bool answer_yes_no(string question)
{
	char c;
	
	do
	{
		// Ask the question
		cout << question << " (y/n) ";
		string s;
		// Read the response
		cin >> s;
		// Look only at the first character, and convert to
		// lower case to simplify checking
		c = tolower(s[0]);
		// Keep iterating until we get a y or n
	} while (c != 'y' && c != 'n');
	
	// Return true if yes, false otherwise
	return c == 'y';
}

// Function template for reading a vector whose elements are
// of type T.  The argument type_string is used to inform the
// user of what kind of element is expected.  The argument
// end_value is used to indicate the end of the vector.
template<typename T> vector<T> read_vector(string type_string, T end_value)
{
	vector<T> v; 
	do {
		// Prompt the user
		cout << "Enter " << type_string;
		cout << " (" << end_value << " to exit): ";
		// Read the value
		T value;
		cin >> value;
		// If bad input, keep prompting
		while (!cin)
		{
			reset_cin();
			cout << "Invalid input!" << endl;
			cout << "Enter " << type_string << ": ";
			cin >> value;
		}
		// If the user types the end_value, the vector
		// is ended
		if (value == end_value)
			break;
		// Otherwise, add the value to the vector
		v.push_back(value);
	} while (true);
	return v;
}
	
// Function template for sorting a vector of elements of
// type T, in which the user is prompted for their sorting
// preferences, and then the vector is sorted.  The vector v
// is passed by reference because it is sorted in-place.
template<typename T> void sort_vector(vector<T>& v)
{
	// There's no need to sort unless there's more than
	// one element!
	if (v.size() > 1)
	{
		// Ask the user if they want to sort the entire
		// vector, or only a portion of it
		bool sort_all = answer_yes_no("Sort entire vector?");
		// Set the start and end indices accordingly
		int start, end;
		if (sort_all)
		{
			start = 1;
			end = v.size();
		}
		else
		{
			start = get_int_in_range(1, v.size(), "start");
			end = get_int_in_range(1, v.size(), "end");
		}
		
		// If the portion to be sorted is empty, no need
		// to go any further
		if (start < end)
		{
			// Get desired sorting order
			bool ascend = answer_yes_no("Sort in ascending order?");
			// Finally, we can sort!
			my_sort(v, start, end, ascend);
		}
	}
}

// Function template for displaying the elements of v in
// a comma-separated list
template<typename T> void display_vector(vector<T> v)
{
	for (unsigned int i = 0; i < v.size(); i++)
	{
		cout << v[i];
		// Don't need a comma after the last element
		if (i < v.size() - 1)
			cout << ", ";
	}
	cout << endl;
}

int main()
{
	// Read, sort and display a vector of positive integers
	vector<int> numbers;
	numbers = read_vector("positive integer", 0);
	sort_vector(numbers);
	display_vector(numbers);
	
	// Read, sort and display a vector of strings
	vector<string> words;
	string end_word("END");
	words = read_vector("string", end_word);
	sort_vector(words);
	display_vector(words);
}