1. Basic Concepts 2. The Standard Library Container Class 3. Vectors and Component Reuse 4. Lists: A Dynamic Data Structure 5. Stacks and Queues

6. Sets and Multisets 7. Trees 8. Hashing

1. Container Classes

   holding quantities of similar objects

   vectors

   A vector is a fixed-length group of elements of uniform type, indexed by integer keys

   v[0], v[1], v[2], ... , v[n-2], v[n-1]

   Access ~ O(1)     ( e.g. v[i] = 2 )

   Remove an element ~ O(n)

   X

   ←

   binary search ~ O( log n )

   strings

   a vector of character values

   e.g. "CSUSB Nice"

   C

   S

   U

   S

   B

   N

   i

   c

   e

   lists

   values of uniform type

   

   stacks

   LIFO, delete and insert at the top push, pop

   queues

   
   FIFO

   delete at the front ( head )
   enter ( insert ) at the rear ( tail )

   useful in communication models

   deque       double-ended queues -- insert and delete can occur at both ends

   sets

   a simple collection of unique values

   1     2 3     4

   multiset

   may have multiple copies of same element

   1     2 3     4     2

   priority queue

   each element is associated with a priority

   delete → sorted sequence

   maps

   A dictionary or a table

   association of keys

   key₁ → value₁
   key₂ → value₂
   ....
   key_n → value_n

   multimap -- allows duplicate keys

2. Iterators

   used to traverse a container without exposing the often complex internal structure of the collection class

   Abstractly, an iterator is simply a pointer-like object used to scan through all the elements stored in a container object

   begin() ↓ cards	cards+1		cards+50	cards+51	end() ↓ cards+52
   ↓	↓		↓	↓	↓
   Cards[0]	Cards[1]	...	Cards[50]	Cards[51]

   vector v(4);

   vector::iterator it;

   for ( it = v.begin(); it != v.end(); ++it )
       *it = 2;

   iterator find ( iterator first, iterator last, T &value ) { while ( first != last && *first != value ) ++first; return first; }

   int data[100]; . . int *p; p = find ( data, data+100, 8 ); *p = 9; //replace the value by 9

   list aList; ... list::iterator it; it = find ( aList.begin(), aList.end(), 8 );

3. String Class

   An implementation

   //str.h #ifndef STR_H #define STR_H class String { protected: char *str; public: //constructors String(); //create an empty string String ( char *init ); //initializes str to string init int length(); //returns length of this string void prints(); //prints this string bool operator < ( String s ); //if this String < String s returns true //else false int find_pat( String pattern );//returns an index i such that pattern //matches the substring of this string that //begins at position i, returns -1 if no match }; #endif

   //str.cpp #include <iostream.h> #include <string.h> #include "str.h" String::String() { str = new char[1]; //points to new node *str = 0; //initializes to NULL string } String::String( char *s ) { str = new char[ strlen( s ) + 1 ]; strcpy( str, s ); } int String::length() { return( strlen( str ) ); } void String::prints() { cout << str << "\n"; } bool String::operator < ( String s ) { return ( strcmp( str, s.str ) < 0 ); }

   -----------------------------------------------------------------------

   An application: sorting example

   //sorting example, a dumb_sort //dumb_sort.cpp #include "str.h" #include <iostream.h> #include <stdio.h> void sort ( String *a, int n ) { int changed; String temp; do { changed = 0; for ( int i = 0; i < n - 1; i++ ) { if ( a[i+1] < a[i] ) { temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; changed = 1; } } } while ( changed ); } void input ( String *a, int limit, int &i ) //value of i will be passed out as size { static char buffer[100]; cout << "\nenter data:"; for ( i = 0; i < limit; i++ ) if ( scanf( "%s", buffer ) == EOF ) break; else a[i] = String ( buffer ); } void output( String *a, int size ) { // cout << a[0].str; //illegal because str is private cout << "\nlist : "; for ( int i = 0; i < size; i++ ) a[i].prints(); cout << endl; } const int max = 10; String list[max]; int size = 0; void main() { String x, y; input ( list, max, size ); sort ( list, size ); output ( list, size ); /* String ss; ss.str = NULL; //illegal, because ss is private */ }

   Extending the String class

   //strs.h #ifndef STR1_H #define STR1_H #include "str.h" //note need to make it str protected instead of private //so that it can be used here class Strings: public String { public: typedef char *iterator; //define iterator Strings (); //constructors cannot be inherited but can call Strings ( char * ); Strings ( Strings & ); ~Strings (); //destructor //member functions iterator begin(); iterator end(); bool isEmpty(); void insert ( unsigned int, Strings & ); void remove ( unsigned int, unsigned int ); //operators char operator [] ( unsigned int ); void operator = ( Strings & ); }; #endif

   //strs.cpp #include <assert.h> #include <string.h> #include "strs.h" Strings::Strings():String() { /* str = new char[1]; //points to new node *str = 0; //initializes to NULL string */ } Strings::Strings( char *s ):String( s ) { // str = new char[ strlen( s ) + 1 ]; // strcpy( str, s ); } Strings::Strings( Strings &s ) { str = new char[s.length() +1]; assert ( str ); strcpy ( str, s.str ); } Strings::~Strings() //called implicitly when a string is about to be deleted //free the memory associated with str { delete [] str; } void Strings::operator = ( Strings &s ) { char *p = new char[s.length() +1]; assert ( p ); delete [] str; //return memory to pool, otherwise memory leak str = p; strcpy ( str, s.str ); } char Strings::operator [] ( unsigned int i ) { assert ( i < length() ); return str[i]; } bool Strings::isEmpty() { return ( *str == 0 ); } char *Strings::begin() { return str; } char *Strings::end() { return str + length(); } void Strings::remove( unsigned int start, unsigned int len ) { int stop = start + len; int strlen = length(); while ( ( stop < strlen ) && ( str[stop] != 0 ) ) str[start++] = str[stop++]; str[start] = 0; } void Strings::insert( unsigned int pos, Strings &newText ) { int len = length(); //current length assert ( pos <= len ); int addLen = newText.length(); //additional length int newLen = len + addLen; //new length char *p = new char[newLen +1]; assert ( p ); int i; for ( i = 0; i < pos; ++i ) p[i] = str[i]; for ( i = 0; i < addLen; ++i ) //copy newtext p[i+pos] = newText[i]; for ( i = pos; i <= len; ++i ) //copy remaining p[i+addLen] = str[i]; delete [] str; str = p; }

   -----------------------------------------------------------------------

   //strs_demo.cpp #include <iostream> #include "strs.h" void main() { Strings s1( "testing" ); char c; c = s1[2]; cout << c << endl; //s Strings s2; s2 = s1; s2.prints(); //testing Strings::iterator start = s2.begin(); Strings::iterator stop = s2.end(); for ( ; start != stop; ++start ) //testing cout << *start; cout << endl; Strings temp( " eat" ); s2.insert( 4, temp ); s2.prints(); //test eating }