Lab 7 Sequence template using linked list

1 Introduction

In this lab we will create a simplified version of the Standard Template Librarys vector class. A sequence holds a

collection of values. Values may be added and removed from the sequence. The values in a sequence are associated

with an index but a values index may change as items are added or removed from the sequence.

Unlike the previous lab, this sequence class needs to:

use a linked list to store the sequence items

be a template class (so value

type below is a generic type)

2 Walk through

Below is a sample program that demonstrates the effect of most of the operations that we can perform on a sequence.

s e q u e n c e < int > s 1 ; / / []

s 1 . a d d ( 5 ) ; / / [5]

s 1 . a d d ( 9 ) ; / / [5 ,9]

s 1 . a d d ( 2 ) ; / / [5 ,9 ,2]

s 1 . i n s e r t ( 1 , 1 5 ) ; / / [5 ,15 ,9 ,2]

s 1 . r e m o v e ( 0 ) ; / / [15 ,9 ,2]

c o u t << s 1 . g e t ( 0 ) << e n d l ; / / would p r i n t 15

c o u t << s 1 . s i z e ( ) << e n d l ; / / would p r i n t 3

s 1 . i n s e r t ( 0 , 3 ) ; / / [3 ,15 ,9 ,2]

s 1 . i n s e r t ( 0 , 2 2 ) ; / / [22 ,3 ,15 ,9 ,2]

for ( i n t i = 0 ; i < s . s i z e ( ) ; i + + )

c o u t << s 1 . g e t ( i ) << ; / / p r i n t s 22 3 15 9 2

s e q u e n c e < int > s 2 ;

s 2 . a d d ( 7 ) ; / / s2 = [7]

s 2 . a d d ( 5 ) ; / / s2 = [7 ,5]

s e q u e n c e s 3 = s 1 + s 2 ; / / s3 = [22 ,3 ,15 ,9 ,2 ,7 ,5]

s e q u e n c e s 4 ;

s 4 . a d d ( 1 ) ; / / s4 = [1]

s 4 += s 2 ; / / s4 = [1 ,7 ,5]

s e q u e n c e < s t r i n g > s 3 ;

s 3 . a d d ( f o o ) ;

s 3 . a d d ( b a r ) ;

c o u t << s 3 . g e t ( 0 ) << e n d l ; / / foo

3 Files

Create a class named sequence and units tests in sequence tests.cpp.

4 Unit tests

All of your original sequence tests should work fine (with small modification since this is a template class) for this version of sequence. An exception would be a test that references the capacity of the sequence.

5 Operations

Implement the operations below. Use assert to check preconditions.

sequence () construct an empty sequence

sequence(const sequence& other) copy constructor

sequence () destruct the sequence

size type size () const return the number of items stored in the sequence

value type get ( size type i ) const (precondition: i > = 0 && i

void add( const value type & value) add the specified value to the end of the sequence

void insert ( size type index , const value type & value) (precondition: index > = 0 && index < = size()) insert the specified value at the specified index, shifting values to higher indexes if needed. If index == size this operation is the same as add.

void remove( size type index ) (precondition: index > = 0 && index <

size()) remove the value at the specified index, shifting other values down as needed.

sequence operator +( const sequence& s1, const sequence& s2) free function (you may implement this as a member function if you prefer) return a new sequence that is the result of appending s2 on to the end of s1

void operator +=( const sequence& other) append other onto the end of this sequence

void operator =( const sequence& other) assignment operator