In the previous article I explained you about the Templates in C++. C++ comes with the Standard Template Library, or STL, which includes many different types of containers, each with its own set of advantages (and disadvantages). The C++ Standard Template Library is a very large library of sometimes-complex containers. This article is considered just an overview of the power of the STL. Some programs can deal with data as it arrives and dispense with it. Most programs, however, must store data for later processing. A structure that is used to store data is known generically as a container or a collection. Array We rely heavily on the array for data storage. The array container has a couple of nice properties: It stores and retrieves things quickly. It can be declared to hold any type of object in a type-safe way. Weighed against these advantages, arrays however have the following negatives. The size of the array is fixed and must be known at the time it is created. This requirement is generally not achievable, although you will sometimes know that the number of elements cannot exceed some large value. Inserting elements anywhere within the array involves copying elements within the array. This is costly in terms of both memory and computing time. Sorting the elements within an array is even more expensive. The string Container The most common form of array is the null-terminated character string used to display text, which clearly shows both the advantages and disadvantages of the array. Consider how the following appears: cout << "This is a string"; But things go sour quickly when we try to perform an operation even as simple as concatenating two of these null-terminated strings: Code: char* concatCharString(const char* s1, const char* s2) { int length = strlen(s1) + strlen(s2) + 1; char* s = new char[length]; strcpy(s, s1); strcat(s, s2); return s; } The STL provides a string container to handle display strings. The string class provides a number of operations (including overloaded operators) to simplify the manipulation of character strings. The same concat() operation can be performed as follows using string objects: Code: string concat(const string& s1, const string& s2) { return s1 + s2; } Major Methods Of The String Class string()--->Creates an empty string object. string(const char*)--->Creates a string object from a null-terminated character array. string(const string& s)--->Creates a new string object as a copy of an existing string object s. ~string()--->Destructor returns internal memory to the heap. string& operator=(const string& s)--->Overwrites the current object with a copy of the string s. string& operator=(const string& s)--->Overwrites the current object with a copy of the string s. istream& operator>>()--->Extracts a string from the input file. Stops when after istream::width() characters read, error occurs, EOF encountered, or white space encountered. Guaranteed to not overflow the internal buffer. ostream& operator<<()--->Inserts string to the output file. string operator+(const string & s1, const string& s2)-->Creates a new string that is the concatenation of two existing strings. string& operator+= (const string& s)-->Appends a string to the end of the current string. char& operator[](size_type index)--->Returns the index'th character of the current string. bool operator==(const string& s1, const string& s2)--->Returns true if the two strings are lexographically equivalent. bool operator<(const string& s1, const string& s2)--->Returns true if s1 is lexicographically less than s2 (i.e., if s1 occurs before s2 in the dictionary). bool operator>(const string& s1, const string& s2)--->Returns true if s1 is lexicographically greater than s2 (i.e., if s1 occurs after s2 in the dictionary). string& append(const string& s)--->Appends a string to the end of the current string. char at(size_type index)--->Returns a reference to the index'th character in the current string. size_t capacity()--->Returns the number of characters the current string object can accommodate without allocating more space from the heap. int compare(const string& s)--->Returns < 0 if the current object is lexicographically less than s, 0 if the current object is equal to s, and > 0 if the current object is greater than s.* const char* data()--->Returns a pointer to the null-terminated character array string within the current object. bool empty()--->Returns true if the current object is empty. size_t find(const string& s, size_t index = 0)--->Searches for the substring s within the current string starting at the index'th character. Returns the index of the substring. Return string::npos if the substring is not found. string& insert(size_t index, const string& s)--->Inserts a string into the current string starting at offset index. size_t max_size()--->Returns the maximum number of objects that a string object can hold, ever. string& replace(size_t index, size_t num, const string& s)--->Replaces num characters in the current string starting at offset index. Enlarges the size of the current string if necessary. void resize(size_t size)--->Resizes the internal buffer to the specified length. size_t length()--->Returns the length of the current string. string substr(size_t index, size_t length)--->Returns a string consisting of the current string starting at offset index and continuing for length characters. The following STLString program demonstrates a few of the capabilities of the string class: Code: // STLString - demonstrates just a few of the features // of the string class which is part of the // Standard Template Library #include <cstdlib> #include <cstdio> #include <iostream> using namespace std; // removeSpaces - remove any spaces within a string string removeSpaces(const string& source) { // make a copy of the source string so that we // modify it string s = source; // find the offset of the first space; // search the string until no more spaces found size_t offset; while((offset = s.find(" ")) != string::npos) { // remove the space just discovered s.erase(offset, 1); } return s; } // insertPhrase - insert a phrase in the position of // <ip> for insertion point string insertPhrase(const string& source) { string s = source; size_t offset = s.find("<ip>"); if (offset != string::npos) { s.erase(offset, 4); s.insert(offset, "Ajit"); } return s; } int main(int argc, char* pArgs[]) { // create a string that is the sum of two strings cout << "string1 + string2 = " << (string("string 1") + string("string 2")) << endl; // create a test string and then remove all spaces // from it using simple string methods string s2("This is a test string"); cout << "<" << s2 << "> minus spaces = <" << removeSpaces(s2) << ">" << endl; // insert a phrase within the middle of an existing // sentence (at the location of "<ip>") string s3 = "Arun <ip> Amit"; cout << s3 + " -> " + insertPhrase(s3) << endl; system("PAUSE"); return 0; } The main() function begins by using operator+() to append two strings together, main() then calls the removeSpaces() method to remove any spaces found in the string provided. It does this by using the string.find() operation to return the offset of the first " " that it finds. Once found, removeSpaces() uses the erase() method to remove the space. The function picks up where it left off, searching for spaces and erasing them until find() returns npos, indicating that it didn't find what it was looking for. The constant npos is a constant of type size_t that is the largest unsigned value possible. It is numerically equal to -1. The insertPhrase() method uses the find() method to find the insertion point flagged by the substring "<ip>". The function then calls erase to remove the "<ip>" flag and string, insert() to insert a new string in the middle of an existing string. The resulting output is as follows: The List Container The STL list container retains objects by linking them like Lego blocks.Objects can be snapped apart and snapped back together in any order.This makes the list ideal for inserting objects, sorting, merging, and otherwise rearranging objects. Major Methods of the list Class list<T>()--->Creates an empty list of objects of class T. ~list<T>()--->Destructs the list, including invoking the destructor on any T objects remaining in the list. list operator=(const list<T>& 1)--->Replaces the contents of the current list with copies of the objects in list 1. bool operator==(const list<T>& 11, const list<T>& 12)--->Performs a lexicographic comparison between each element in the two lists. list<T>::iterator begin()--->Returns an iterator that points to the first element in the current list. void clear()---> Removes and destructs every object in the current list. bool empty()---> Returns true if the current list is empty. list<T>::iterator end()---> Returns an iterator that points to the next entry beyond the end of the current list. list<T>::iterator insert(list<T>::iterator loc, const T& object)---> Adds object to the list at the position pointed at by the iterator loc. Returns an iterator that points to the added object. void pop_front()--->Removes the last or first object from the current list. void push_front(const T& object)[/inlinecode]---> Adds an object to the end or front of the current list. list<T>::reverse_iterator rbegin()---> Returns an iterator that points to the last entry in the list (useful when iterating backward through the list, starting at the end and working toward the beginning). list<T>::reverse_iterator rend()---> Returns an iterator that points to the entry before the first entry in the list (useful when iterating backwards through the list). void remove(const T& object)---> Removes all objects from the current list that are the same as object (as determined by operator== (T&, T&)). size_t size()---> Returns the number of entries in the current list. void sort()---> Sorts the current list such that each object in the list is less than the next object as determined by operator<(T&, T&). void splice(list<T>::iterator pos, list<T>& source)---> Removes the objects from the source list and adds them to the current list in front of the object referenced by pos. void unique()---> Removes any subsequent equal objects (as determined by operator== (T&, T&)). The constructor for list<T> creates an empty list. Objects can be added either to the front or end of the list using the push_front() or push_back(). For example, the following code snippet creates an empty list of Student objects and adds two to the list: Code: list<Student> students; students.push_back(Student("Amit")); students.push_back(Student("Ajit")); Making Your Way through a List The programmer iterates through an array by providing the index of each element. However, this technique doesn't work for containers like list that don't allow for random access. One could imagine a solution based in methods such as getFirst() and getNext(). However, the designers of the Standard Template Library wanted to provide a common method for traversing any type of container. For this, the Standard Template Library defines the iterator. An iterator is an object that points to the members of a container. In general, every iterator supports the following functions: A class can return an iterator that points to the first member of the collection.The iterator can be moved from one member to the next.The program can retrieve the element pointed to by the iterator. The Standard Template Library also provides reverse iterators for moving backward through lists. Everything about iterators applies equally for reverse iterators. The code necessary to iterate through a list is different from that necessary to traverse a vector (to name just two examples). However, the iterator hides these details. The method begin() returns an iterator that points to the first element in the list. The indirection operator*() retrieves a reference to the object pointed at by the iterator. The ++ operator moves the iterator to the next element in the list. A program continues to increment its way through the list until the iterator is equal to the value returned by end(). The following code snippet starts at the beginning of a list of students and displays each of their names: Code: void displayStudents(list<Student>& students) { // allocate an iterator that points to the first // element in the list list<Student>::iterator iter = students.begin(); // continue to loop through the list until the // iterator hits the end of the list while(iter != students.end()) { // retrieve the Student the iterator points at Student& s = *iter; cout << s.sName << endl; // now move the iterator over to the next element // in the list iter++; } } Declarations for iterators can get very complex. This is probably the best justification for the auto declaration introduced with the '09 standard: Code: for(auto iter = students.end(); iter != students.end(); iter++) { cout << iter->sName << endl; } This declares iter to be an iterator of whatever type is returned by the method list<student>::end(), avoiding the declarations shown in the earlier code. Operations on an Entire List The STL library defines certain operations on the entire list. For example, the list<T&>::sort() method sorts the list if you just tell the method which objects go first. You do this by defining operator< (T&, T&). This operator is already defined for the intrinsic types and many library classes such as string. For example, you don't have to do anything to sort a list of integers: list<int> scores; scores.push_back(10); scores.push_back(1); scores.push_back(5); scores.sort(); The programmer must define her own comparison operator for her own classes if she wants C++ to sort them. For example, the following comparison sorts Student objects by their student ID: Code: bool operator<(const Students& s1, const Students& s2) { return s1.ssID < s2.ssID; } The following STLListStudents program demonstrates several functions . It creates a list of user-defined Student objects, iterates the list, and sorts the list. The program appears as follows: Code: // STLListStudents - use a list to contain and sort a // user defined class #include <cstdio> #include <cstdlib> #include <iostream> #include <list> using namespace std; // Student - some example user defined class class Student { public: Student(const char* pszS, int id) : sName(pszS), ssID(id) {} string sName; int ssID; }; // the following function is required to support the // sort operation bool operator<(const Student& s1, const Student& s2) { return s1.ssID < s2.ssID; } // displayStudents - iterate through the list displaying // each element void displayStudents(list<Student>& students) { // allocate an iterator that points to the first // element in the list list<Student>::iterator iter = students.begin(); // continue to loop through the list until the // iterator hits the end of the list while(iter != students.end()) { // retrieve the Student the iterator points at Student& s = *iter; cout << s.ssID << " - " << s.sName << endl; // now move the iterator over to the next element // in the list iter++; } } int main(int argc, char* pArgs[]) { // define a collection of students list<Student> students; // add three student objects to the list students.push_back(Student("Ajit", 10)); students.push_back(Student("Amit", 5)); students.push_back(Student("Arun", 15)); // display the list cout << "The original list:"<< endl; displayStudents(students); // now sort the list and redisplay students.sort(); cout << "\nThe sorted list:" << endl; displayStudents(students); system("PAUSE"); return 0; } This program defines a list of user-defined Student objects. Three calls to push_back() add elements to the list . The program then calls displayStudents() to display the contents of the list both before and after the list has been sorted using the template library sort() function. The original list: 10 - Ajit 5 - Amit 15 - Arun The sorted list: 5 - Amit 10 - Ajit 15 - Arun Press any key to continue . . .
