Lab 7 Assignment - STL Vector and Algorithms

This assignment will familarize you with the C++ STL

Introduction*

The Standard Template Libraries (STL's) are a set of C++ template classes to provide common programming data structures and functions such as doubly linked lists (list), paired arrays (map), expandable arrays (vector), large string storage and manipulation (rope), etc. The STL library is available from the STL Documentation. This is also your best detailed reference for all of the STL class functions available.

STL can be categorized into the following groupings:

  • Container classes:
    • Sequences:
      • vector : (this tutorial) Dynamic array of variables, struct or objects. Insert data at the end.
      • deque: Array which supports insertion/removal of elements at beginning or end of array
      • list : (this tutorial) Linked list of variables, struct or objects. Insert/remove anywhere.
    • Associative Containers:
      • set (duplicate data not allowed in set), multiset (duplication allowed): Collection of ordered data in a balanced binary tree structure. Fast search.
      • map (unique keys), multimap (duplicate keys allowed): Associative key-value pair held in balanced binary tree structure.
    • Container adapters:
      • stack LIFO
      • queue FIFO
      • priority_queue returns element with highest priority.
    • String:
      • string : Character strings and manipulation
      • rope: String storage and manipulation
    • bitset: Contains a more intuitive method of storing and manipulating bits.
  • Operations/Utilities:
    • iterator: (examples in this tutorial) STL class to represent position in an STL container. An iterator is declared to be associated with a single container class type.
    • algorithm: Routines to find, count, sort, search, ... elements in container classes
    • auto_ptr: Class to manage memory pointers and avoid memory leaks.

vector: Dynamic array of variables, struct or objects. Insert data at the end.

Simple example of storing STL strings in a vector. This example shows three methods of accessing the data within the vector:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

main()
{
   vector<string> SS;

   SS.push_back("The number is 10");
   SS.push_back("The number is 20");
   SS.push_back("The number is 30");

   cout << "Loop by index:" << endl;

   int ii;
   for(ii=0; ii < SS.size(); ii++)
   {
      cout << SS[ii] << endl;
   }

   cout << endl << "Constant Iterator:" << endl;

   vector<string>::const_iterator cii;
   for(cii=SS.begin(); cii!=SS.end(); cii++)
   {
      cout << *cii << endl;
   }

   cout << endl << "Reverse Iterator:" << endl;

   vector<string>::reverse_iterator rii;
   for(rii=SS.rbegin(); rii!=SS.rend(); ++rii)
   {
      cout << *rii << endl;
   }

   cout << endl << "Sample Output:" << endl;

   cout << SS.size() << endl;
   cout << SS[2] << endl;

   swap(SS[0], SS[2]);
   cout << SS[2] << endl;
}
                

Experiment

Create a project, and compile and run. Complete:

  1. What is your output?
  2. What is the difference between each of the three access method?
  3. Modify the code to operate on integers rather then strings.
  4. Make a loop to push 20 random numbers in the integer vector using the rand() function, documented here.
  5. Review STL Algorithms.
  6. Use the STL min_element algorithm to find the minimum element. Display it.(Follow the link to see a description and an exmple of it's use)
  7. Use sort algorithm to sort the vector. Display the sorted array. (Again, folow the link)
  8. Write a loop that asks the user for a number, and use the binary_search algorithm check for it's existance. Terminate the loop when the user searches for a 0.

What to turn in on _BlackBoard_

The laboratory report should include the following elements:

  1. Brief statement of the objectives of the lab and a description of what you did during the lab session (A paragraph or two).
  2. Lab results such as program listings, input and/or output files, tables of data produced, answers to specific questions posed, etc. as appropriate to the lab assignment. If there were no results, indicate this with “No Results.”
  3. Discussion of any difficulties you encountered and what you did to resolve them (A paragraph or two).
  4. Discussion of what you learned or how the lab experience reinforced things you already knew (A paragraph or two).
  5. Your overall rating of the lab on a scale of 1-4 and an explanation of your rating. Ratings are as follows:

*Based on: http://www.yolinux.com/TUTORIALS/LinuxTutorialC++STL.html

-- JimSkon - 2010-04-28

Topic revision: r6 - 2011-04-22 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback