Vector and List - Part 2

◀ Vector and List - Part 1▶ Queue and Stack Amazon There are two functions provided by #include <algorithm> I want you to know about because at times they can be very useful: random_shuffle() and sort(). They both require that the container support random access, such as a vector and deque. The random_shuffle() takes two iterators specifying a range and rearranges the contents within that range arbitrarily. So if hollywood is an instance of vector<Star>, you can do

random_shuffle(hollywood.begin(), hollywood.end());

to randomize the order of elements in hollywood. There are two versions of sort(). The first one takes two iterators that specify a range and sorts the contents within that range based on the operator <. If the container elements are user-defined types, then you need to define operator<() that returns a bool. The following is an example of operator<() definition:

bool operator<(Star star, Star star2) {
	if(star.wealth < star2.wealth)
		return true;
	else if(star.wealth == star2.wealth && star.height < star2.height)
		return true;
	return false;
}

This function returns true if the first star is less wealthy than the second one, or if they are equally wealthy the first star is shorter; it returns false otherwise. Here is the function call to use sort():

sort(hollywood.begin(), hollywood.end());

After sorting is done, the first element in hollywood will be the least wealthy.

The second version of sort() takes two iterators that indicate a range and a third argument which is a function address so that sorting is done based on that function instead of operator <. The following is such a function:

bool newSort(Star star, Star star2) {
  if(star.wealth < star2.wealth)
    return true;
  return false;
}

If you use newSort() to sort, then the first element of the resulting vector will be the least wealthy. But if there are more than one such star, there is no knowing how they are ordered. Here is a function call to use newSort() to sort:

sort(hollywood.begin(), hollywood.end(), newSort);

Now let’s see a program illustrating how to use list:

#include <iostream>
using namespace std;
#include <list>

template <typename T>
ostream & operator<<(ostream & os, list<T> a){
	list<T>::iterator lii;
	for(lii = a.begin(); lii != a.end(); lii++)
		os << *lii << ' ';
	return os;
}

int main() {
	list<int> l1;
	list<int> l2(6,3);
	list<int> l3(l2);

	int temp[] = {8,4,1,3};
	l1.insert(l1.end(), temp, temp+4);
	l3.insert(l3.begin(), temp, temp+3);
	cout << "List #1: " << l1 << endl;
	cout << "List #2: " << l2 << endl;
	cout << "List #3: " << l3 << endl;
	l3.splice(l3.begin(), l1);
	cout << "List #3 after splice: " << l3 << endl;
	l3.remove(1);
	cout << "List #3 w/t 1: " << l3 << endl;
	l3.sort();
	cout << "List #3 after sort: " << l3 << endl;
	l3.unique();
	cout << "List #3 after unique: " << l3 << endl;
	l1.insert(l1.end(), temp, temp+4);
	l1.sort();
	l3.merge(l1);
	cout << "List #3 after merge: " << l3 << endl;
	l3.unique();
	cout << "List #3 after unique: " << l3 << endl;

	return 0;
}

Run the program and you should pretty much understand each line of output. List provides functions such as merge() and sort() which can prove helpful at times.

One example is that a group of 10 people want to buy lottery, which consists of 6 numbers. You can receive 6 numbers from each of them and then use sort(), merge(), and unique() to get a clean sequence of unique numbers, which come from all 10 people’s opinions.

Another example is that you have two or more dictionaries and you want to combine them all into one single dictionary by removing identical entries via sort(), merge(), and unique().

Next we’ll take a look at queue and stack, two of the rudimentary STL container classes which exhibit important computing concepts!◀ Vector and List - Part 1▶ Queue and Stack