Question

I need help implemeting the remove_repetitions()

Here is a brief outline of an algorithm:

A node pointer p steps through the bag

For each Item, define a new pointer q equal to p

While the q is not the last Item in the bag

If the next Item has data equal to the data in p, remove the next Item

Otherwise move q to the next Item in the bag.

I also need help creating a test program

_____________________________________________________________________________________________________________________________________________________

#ifndef NODE2_H

#define NODE2_H

// FILE: node2.h (part of the namespace main_savitch_6B)

// PROVIDES: A template class for a node in a linked list, and list manipulation

// functions. The template parameter is the type of the data in each node.

// This file also defines a template class: node_iterator<Item>.

// The node_iterator is a forward iterators with two constructors:

// (1) A constructor (with a node<Item>* parameter) that attaches the iterator

// to the specified node in a linked list, and (2) a default constructor that

// creates a special iterator that marks the position that is beyond the end of a

// linked list. There is also a const_node_iterator for use with

// const node<Item>* .

//

// TYPEDEF for the node<Item> template class:

// Each node of the list contains a piece of data and a pointer to the

// next node. The type of the data (node<Item>::value_type) is the Item type

// from the template parameter. The type may be any of the built-in C++ classes

// (int, char, ...) or a class with a default constructor, an assignment

// operator, and a test for equality (x == y).

// NOTE:

// Many compilers require the use of the new keyword typename before using

// the expression node<Item>::value_type. Otherwise

// the compiler doesn't have enough information to realize that it is the

// name of a data type.

//

// CONSTRUCTOR for the node<Item> class:

// node(

// const Item& init_data = Item(),

// node* init_link = NULL

// )

// Postcondition: The node contains the specified data and link.

// NOTE: The default value for the init_data is obtained from the default

// constructor of the Item. In the ANSI/ISO standard, this notation

// is also allowed for the built-in types, providing a default value of

// zero. The init_link has a default value of NULL.

//

// NOTE about two versions of some functions:

// The data function returns a reference to the data field of a node and

// the link function returns a copy of the link field of a node.

// Each of these functions comes in two versions: a const version and a

// non-const version. If the function is activated by a const node, then the

// compiler choses the const version (and the return value is const).

// If the function is activated by a non-const node, then the compiler choses

// the non-const version (and the return value will be non-const).

// EXAMPLES:

// const node<int> *c;

// c->link( ) activates the const version of link returning const node*

// c->data( ) activates the const version of data returning const Item&

// c->data( ) = 42; ... is forbidden

// node<int> *p;

// p->link( ) activates the non-const version of link returning node*

// p->data( ) activates the non-const version of data returning Item&

// p->data( ) = 42; ... actually changes the data in p's node

//

// MEMBER FUNCTIONS for the node<Item> class:

// const Item& data( ) const <----- const version

// and

// Item& data( ) <----------------- non-const version

// See the note (above) about the const version and non-const versions:

// Postcondition: The return value is a reference to the data from this node.

//

// const node* link( ) const <----- const version

// and

// node* link( ) <----------------- non-const version

// See the note (above) about the const version and non-const versions:

// Postcondition: The return value is the link from this node.

//

// void set_data(const Item& new_data)

// Postcondition: The node now contains the specified new data.

//

// void set_link(node* new_link)

// Postcondition: The node now contains the specified new link.

//

// FUNCTIONS in the linked list toolkit:

// template <class Item>

// void list_clear(node<Item>*& head_ptr)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: All nodes of the list have been returned to the heap,

// and the head_ptr is now NULL.

//

// template <class Item>

// void list_copy

// (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)

// Precondition: source_ptr is the head pointer of a linked list.

// Postcondition: head_ptr and tail_ptr are the head and tail pointers for

// a new list that contains the same items as the list pointed to by

// source_ptr. The original list is unaltered.

//

// template <class Item>

// void list_head_insert(node<Item>*& head_ptr, const Item& entry)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: A new node containing the given entry has been added at

// the head of the linked list; head_ptr now points to the head of the new,

// longer linked list.

//

// template <class Item>

// void list_head_remove(node<Item>*& head_ptr)

// Precondition: head_ptr is the head pointer of a linked list, with at

// least one node.

// Postcondition: The head node has been removed and returned to the heap;

// head_ptr is now the head pointer of the new, shorter linked list.

//

// template <class Item>

// void list_insert(node<Item>* previous_ptr, const Item& entry)

// Precondition: previous_ptr points to a node in a linked list.

// Postcondition: A new node containing the given entry has been added

// after the node that previous_ptr points to.

//

// template <class Item>

// size_t list_length(const node<Item>* head_ptr)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: The value returned is the number of nodes in the linked

// list.

//

// template <class NodePtr, class SizeType>

// NodePtr list_locate(NodePtr head_ptr, SizeType position)

// The NodePtr may be either node<Item>* or const node<Item>*

// Precondition: head_ptr is the head pointer of a linked list, and

// position > 0.

// Postcondition: The return value is a pointer that points to the node at

// the specified position in the list. (The head node is position 1, the

// next node is position 2, and so on). If there is no such position, then

// the null pointer is returned.

//

// template <class Item>

// void list_remove(node<Item>* previous_ptr)

// Precondition: previous_ptr points to a node in a linked list, and this

// is not the tail node of the list.

// Postcondition: The node after previous_ptr has been removed from the

// linked list.

//

// template <class NodePtr, class Item>

// NodePtr list_search

// (NodePtr head_ptr, const Item& target)

// The NodePtr may be either node<Item>* or const node<Item>*

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: The return value is a pointer that points to the first

// node containing the specified target in its data member. If there is no

// such node, the null pointer is returned.

//

// DYNAMIC MEMORY usage by the toolkit:

// If there is insufficient dynamic memory, then the following functions throw

// bad_alloc: the constructor, list_head_insert, list_insert, list_copy.

#include <cstdlib> // Provides NULL and size_t

#include <iterator> // Provides iterator and forward_iterator_tag

template <class Item>

class node

{

public:

// TYPEDEF

typedef Item value_type;

// CONSTRUCTOR

node(const Item& init_data=Item( ), node* init_link=NULL)

{ data_field = init_data; link_field = init_link; }

// MODIFICATION MEMBER FUNCTIONS

Item& data( ) { return data_field; }

node* link( ) { return link_field; }

void set_data(const Item& new_data) { data_field = new_data; }

void set_link(node* new_link) { link_field = new_link; }

// CONST MEMBER FUNCTIONS

const Item& data( ) const { return data_field; }

const node* link( ) const { return link_field; }

private:

Item data_field;

node *link_field;

};

// FUNCTIONS to manipulate a linked list:

template <class Item>

void list_clear(node<Item>*& head_ptr);

template <class Item>

void list_copy

(const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);

template <class Item>

void list_head_insert(node<Item>*& head_ptr, const Item& entry);

template <class Item>

void list_head_remove(node<Item>*& head_ptr);

template <class Item>

void list_insert(node<Item>* previous_ptr, const Item& entry);

template <class Item>

std::size_t list_length(const node<Item>* head_ptr);

template <class NodePtr, class SizeType>

NodePtr list_locate(NodePtr head_ptr, SizeType position);

template <class Item>

void list_remove(node<Item>* previous_ptr);

template <class NodePtr, class Item>

NodePtr list_search(NodePtr head_ptr, const Item& target);

// FORWARD ITERATORS to step through the nodes of a linked list

// A node_iterator of can change the underlying linked list through the

// * operator, so it may not be used with a const node. The

// node_const_iterator cannot change the underlying linked list

// through the * operator, so it may be used with a const node.

// WARNING:

// This classes use std::iterator as its base class;

// Older compilers that do not support the std::iterator class can

// delete everything after the word iterator in the second line:

template <class Item>

class node_iterator : public std::iterator<std::forward_iterator_tag, Item>

{

public:

node_iterator(node<Item>* initial = NULL){ current = initial; }

  

Item& operator *( ) const { return current->data( ); }

  

node_iterator& operator ++( ) // Prefix ++

{

current = current->link( );

return *this;

}

  

node_iterator operator ++(int) // Postfix ++

{

node_iterator original(current);

current = current->link( );

return original;   

}

  

bool operator ==(const node_iterator other) const { return current == other.current; }

  

bool operator !=(const node_iterator other) const { return current != other.current; }

private:

node<Item>* current;

};

template <class Item>

class const_node_iterator : public std::iterator<std::forward_iterator_tag, const Item>

{

public:

const_node_iterator(const node<Item>* initial = NULL) { current = initial; }

  

const Item& operator *( ) const { return current->data( ); }

  

const_node_iterator& operator ++( ) // Prefix ++

{

current = current->link( );

return *this;

}

  

const_node_iterator operator ++(int) // Postfix ++

{

const_node_iterator original(current);

current = current->link( );

return original;

}

  

bool operator ==(const const_node_iterator other) const { return current == other.current; }

  

bool operator !=(const const_node_iterator other) const { return current != other.current; }

private:

const node<Item>* current;

};

#include "node2.template"

#endif // NODE2_H

_________________________________________________________________________________________________________

include <cassert> // Provides assert

#include <cstdlib> // Provides NULL and size_t

template <class Item>

void list_clear(node<Item>*& head_ptr)

// Library facilities used: cstdlib

{

while (head_ptr != NULL)

list_head_remove(head_ptr);

}

template <class Item>

void list_copy(

const node<Item>* source_ptr,

node<Item>*& head_ptr,

node<Item>*& tail_ptr

)

// Library facilities used: cstdlib

{

head_ptr = NULL;

tail_ptr = NULL;

// Handle the case of the empty list

if (source_ptr == NULL)

return;

// Make the head node for the newly created list, and put data in it

list_head_insert(head_ptr, source_ptr->data( ));

tail_ptr = head_ptr;

// Copy rest of the nodes one at a time, adding at the tail of new list

source_ptr = source_ptr->link( );

while (source_ptr != NULL)

{

list_insert(tail_ptr, source_ptr->data( ));

tail_ptr = tail_ptr->link( );

source_ptr = source_ptr->link( );

}

}

  

template <class Item>

void list_head_insert(node<Item>*& head_ptr, const Item& entry)

{

head_ptr = new node<Item>(entry, head_ptr);

}

template <class Item>

void list_head_remove(node<Item>*& head_ptr)

{

node<Item> *remove_ptr;

remove_ptr = head_ptr;

head_ptr = head_ptr->link( );

delete remove_ptr;

}

template <class Item>

void list_insert(node<Item>* previous_ptr, const Item& entry)

{

node<Item> *insert_ptr;

  

insert_ptr = new node<Item>(entry, previous_ptr->link( ));

previous_ptr->set_link(insert_ptr);

}

template <class Item>

std::size_t list_length(const node<Item>* head_ptr)

// Library facilities used: cstdlib

{

const node<Item> *cursor;

std::size_t answer;

answer = 0;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))

++answer;

return answer;

}

template <class NodePtr, class SizeType>

NodePtr list_locate(NodePtr head_ptr, SizeType position)

// Library facilities used: cassert, cstdlib

{

NodePtr cursor;

SizeType i;

  

assert(0 < position);

cursor = head_ptr;

for (i = 1; (i < position) && (cursor != NULL); ++i)

cursor = cursor->link( );

return cursor;

}

template <class Item>

void list_remove(node<Item>* previous_ptr)

{

node<Item> *remove_ptr;

remove_ptr = previous_ptr->link( );

previous_ptr->set_link(remove_ptr->link( ));

delete remove_ptr;

}

template <class NodePtr, class Item>

NodePtr list_search(NodePtr head_ptr, const Item& target)

// Library facilities used: cstdlib

{

NodePtr cursor;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))

if (target == cursor->data( ))

return cursor;

return NULL;

}

_________________________________________________________________________________________________________________________________

#ifndef BAG5_H

#define BAG5_H

// FILE: bag5.h (part of the namespace main_savitch_chapter6)

// TEMPLATE CLASS PROVIDED:

// bag<Item> (a collection of items; each item may appear multiple times)

//

// TYPEDEFS for the bag<Item> template class:

// bag<Item>::value_type

// This is the Item type from the template parameter.

// It is the data type of the items in the bag. It may be any

// of the C++ built-in types (int, char, etc.), or a class with a default

// constructor, a copy constructor, an assignment

// operator, and a test for equality (x == y).

//

// bag<Item>::size_type

// This is the data type of any variable that keeps track of how many items

// are in a bag

//

// bag<Item>::iterator and bag<Item>::const_iterator

// Forward iterators for a bag or a const bag.

//

// CONSTRUCTOR for the bag<Item> class:

// bag( )

// Postcondition: The bag is empty.

//

// MODIFICATION MEMBER FUNCTIONS for the bag<Item> class:

// size_type erase(const Item& target)

// Postcondition: All copies of target have been removed from the bag.

// The return value is the number of copies removed (which could be zero).

//

// bool erase_one(const Item& target)

// Postcondition: If target was in the bag, then one copy of target has

// been removed from the bag; otherwise the bag is unchanged. A true

// return value indicates that one copy was removed; false indicates that

// nothing was removed.

//

// void insert(const Item& entry)

// Postcondition: A new copy of entry has been inserted into the bag.

//

// void operator +=(const bag& addend)

// Postcondition: Each item in addend has been added to this bag.

//

// CONSTANT MEMBER FUNCTIONS for the bag<Item> class:

// size_type count(const Item& target) const

// Postcondition: Return value is number of times target is in the bag.

//

// Item grab( ) const

// Precondition: size( ) > 0.

// Postcondition: The return value is a randomly selected item from the bag.

//

// size_type size( ) const

// Postcondition: Return value is the total number of items in the bag.

//

// STANDARD ITERATOR MEMBER FUNCTIONS (provide a forward iterator):

// iterator begin( )

// const_iterator begin( ) const

// iterator end( )

// const iterator end( ) const

//

// NONMEMBER FUNCTIONS for the bag<Item> class:

// template <class Item>

// bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)

// Postcondition: The bag returned is the union of b1 and b2.

//

// VALUE SEMANTICS for the bag<Item> class:

// Assignments and the copy constructor may be used with bag objects.

//

// DYNAMIC MEMORY USAGE by the bag<Item>:

// If there is insufficient dynamic memory, then the following functions throw

// bad_alloc: The constructors, insert, operator +=, operator +, and the

// assignment operator.

#include <cstdlib> // Provides NULL and size_t and NULL

#include "node2.h" // Provides node class

template <class Item>

class bag

{

public:

// TYPEDEFS

typedef std::size_t size_type;

typedef Item value_type;

typedef node_iterator<Item> iterator;

typedef const_node_iterator<Item> const_iterator;

// CONSTRUCTORS and DESTRUCTOR

bag( );

bag(const bag& source);

~bag( );

// MODIFICATION MEMBER FUNCTIONS

size_type erase(const Item& target);

bool erase_one(const Item& target);

void insert(const Item& entry);

void operator +=(const bag& addend);

void operator =(const bag& source);

void print_value_range(const Item& x, const Item& y);

void remove_repetitions();

// CONST MEMBER FUNCTIONS

size_type count(const Item& target) const;

Item grab( ) const;

size_type size( ) const { return many_nodes; }

// FUNCTIONS TO PROVIDE ITERATORS

iterator begin( )

{ return iterator(head_ptr); }

const_iterator begin( ) const

{ return const_iterator(head_ptr); }

iterator end( )

{ return iterator( ); } // Uses default constructor

const_iterator end( ) const

{ return const_iterator( ); } // Uses default constructor

private:

node<Item> *head_ptr; // Head pointer for the list of items

size_type many_nodes; // Number of nodes on the list

};

// NONMEMBER functions for the bag

template <class Item>

bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2);

// The implementation of a template class must be included in its header file:

#include "bag5.template"

#endif // BAG5_H

___________________________________________________________________________________________________________________

/// FILE: bag5.template

// CLASS implemented: bag (see bag5.h for documentation)

// NOTE:

// Since bag is a template class, this file is included in node2.h.

// INVARIANT for the bag class:

// 1. The items in the bag are stored on a linked list;

// 2. The head pointer of the list is stored in the member variable head_ptr;

// 3. The total number of items in the list is stored in the member variable

// many_nodes.

#include <cassert> // Provides assert

#include <cstdlib> // Provides NULL, rand

#include "node2.h" // Provides node

template <class Item>

bag<Item>::bag( )

// Library facilities used: cstdlib

{

head_ptr = NULL;

many_nodes = 0;

}

template <class Item>

bag<Item>::bag(const bag<Item>& source)

// Library facilities used: node2.h

{

node<Item> *tail_ptr; // Needed for argument of list_copy

list_copy(source.head_ptr, head_ptr, tail_ptr);

many_nodes = source.many_nodes;

}

template <class Item>

bag<Item>::~bag( )

// Library facilities used: node2.h

{

list_clear(head_ptr);

many_nodes = 0;

}

template <class Item>

typename bag<Item>::size_type bag<Item>::count(const Item& target) const

// Library facilities used: cstdlib, node2.h

{

size_type answer;

const node<Item> *cursor;

answer = 0;

cursor = list_search(head_ptr, target);

while (cursor != NULL)

{

// Each time that cursor is not NULL, we have another occurrence of

// target, so we add one to answer, and move cursor to the next

// occurrence of the target.

++answer;

cursor = cursor->link( );

cursor = list_search(cursor, target);

}

return answer;

}

template <class Item>

typename bag<Item>::size_type bag<Item>::erase(const Item& target)

// Library facilities used: cstdlib, node2.h

{

size_type answer = 0;

node<Item> *target_ptr;

target_ptr = list_search(head_ptr, target);

while (target_ptr != NULL)

{

// Each time that target_ptr is not NULL, we have another occurrence

// of target. We remove this target using the same technique that

// was used in erase_one.

++answer;

--many_nodes;

target_ptr->set_data( head_ptr->data( ) );

target_ptr = target_ptr->link( );

target_ptr = list_search(target_ptr, target);

list_head_remove(head_ptr);

}

return answer;

}

  

template <class Item>

bool bag<Item>::erase_one(const Item& target)

// Library facilities used: cstdlib, node2.h

{

node<Item> *target_ptr;

target_ptr = list_search(head_ptr, target);

if (target_ptr == NULL)

return false; // target isn't in the bag, so no work to do

target_ptr->set_data( head_ptr->data( ) );

list_head_remove(head_ptr);

--many_nodes;

return true;

}

template <class Item>

Item bag<Item>::grab( ) const

// Library facilities used: cassert, cstdlib, node2.h

{

size_type i;

const node<Item> *cursor;

assert(size( ) > 0);

i = (std::rand( ) % size( )) + 1;

cursor = list_locate(head_ptr, i);

return cursor->data( );

}

template <class Item>

void bag<Item>::insert(const Item& entry)

// Library facilities used: node2.h

{

list_head_insert(head_ptr, entry);

++many_nodes;

}

template <class Item>

void bag<Item>::operator +=(const bag<Item>& addend)

// Library facilities used: node2.h

{

node<Item> *copy_head_ptr;

node<Item> *copy_tail_ptr;

if (addend.many_nodes > 0)

{

list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);

copy_tail_ptr->set_link( head_ptr );

head_ptr = copy_head_ptr;

many_nodes += addend.many_nodes;

}

}

template < class Item >

void bag< Item> :: print_value_range(const Item& x, const Item& y){

const node <Item> * cursor;

const node <Item> * cursor2;

cursor= list_search(head_ptr,x);

if (cursor != NULL)

{

if ( cursor= cursor2){

std::cout << cursor -> data() << std::endl;

}

cursor2= list_search(head_ptr,y);

while ( cursor != cursor2 && cursor != NULL){

std::cout << cursor -> data() << std::endl;

cursor = cursor -> link();

}

}

}

template < class Item >

void bag < Item> :: remove_repetitions() {

  

// implement the function

  

  

  

}

  

template <class Item>

void bag<Item>::operator =(const bag<Item>& source)

// Library facilities used: node2.h

{

node<Item> *tail_ptr; // Needed for argument to list_copy

if (this == &source)

return;

list_clear(head_ptr);

many_nodes = 0;

list_copy(source.head_ptr, head_ptr, tail_ptr);

many_nodes = source.many_nodes;

}

template <class Item>

bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)

{

bag<Item> answer;

answer += b1;

answer += b2;

return answer;

}

Answer 1

node.template

#include <cassert>    // Provides assert
#include <cstdlib>    // Provides size_t
#include "node.h"

template<typename Item>
void list_clear(node<Item> *&head_ptr) {
    while (head_ptr != nullptr)
        list_head_remove(head_ptr);
}

template<typename Item>
void list_copy(const node<Item> *source_ptr, node<Item> *&head_ptr, node<Item> *&tail_ptr) {
    head_ptr = nullptr;
    tail_ptr = nullptr;

    // check if empty list
    if (source_ptr == nullptr)
        return;

    // Make the head node for the newly created list, and put data in it
    list_head_insert(head_ptr, source_ptr->data());
    tail_ptr = head_ptr;

    // Copy rest of the nodes one at a time, adding at the tail of new list
    source_ptr = source_ptr->link();
    while (source_ptr != nullptr) {
        list_insert(tail_ptr, source_ptr->data());
        tail_ptr = tail_ptr->link();
        source_ptr = source_ptr->link();
    }
}

template<typename Item>
void list_head_insert(node<Item> *&head_ptr, const Item &entry) {
    head_ptr = new node<Item>(entry, head_ptr);
}

template<typename Item>
void list_head_remove(node<Item> *&head_ptr) {
    node<Item> *remove_ptr;

    remove_ptr = head_ptr;
    head_ptr = head_ptr->link();
    delete remove_ptr;
}

template<typename Item>
void list_insert(node<Item> *previous_ptr, const Item &entry) {
    node<Item> *insert_ptr;
    insert_ptr = new node<Item>(entry, previous_ptr->link());
    previous_ptr->set_link(insert_ptr);
}

template<typename Item>
std::size_t list_length(const node<Item> *head_ptr) {
    const node<Item> *cursor;
    std::size_t answer = 0;

    for (cursor = head_ptr; cursor != nullptr; cursor = cursor->link())
        ++answer;

    return answer;
}

template<class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position) {
    NodePtr cursor;
    SizeType i;

    assert(position > 0);
    cursor = head_ptr;
    for (i = 1; (i < position) && (cursor != nullptr); ++i)
        cursor = cursor->link();
    return cursor;
}

template<typename Item>
void list_remove(node<Item> *previous_ptr) {
    node<Item> *remove_ptr = previous_ptr->link();
    previous_ptr->set_link(remove_ptr->link());
    delete remove_ptr;
}

template<class NodePtr, class Item>
NodePtr list_search(NodePtr head_ptr, const Item &target) {
    for (NodePtr cursor = head_ptr; cursor != nullptr; cursor = cursor->link())
        if (target == cursor->data())
            return cursor;
    return nullptr;
}

main.cpp

#include <cstdlib>
#include <iostream>
#include <set>
#include <algorithm>
#include "node.h"
#include "bag.h"

using namespace std;
template<class Item, class SizeType, class MessageType>
void get_items(bag<Item> &collection, SizeType n, MessageType description) {
    Item user_input; // An item typed by the program's user
    SizeType i;

    cout << "Please type " << n << " " << description;
    cout << ", separated by spaces.\n";
    cout << "Press the <return> key after the final entry:\n";
    for (i = 0; i < n; ++i) {
        cin >> user_input;
        std::cout << i + 1 << " item(s) added to bag...\n";
        collection.insert(user_input);
    }
    cout << endl;
}

int main() {
    //demonstrate how to use set template class
    set<string> actors1;
    set<string> actors2;
    set<string>::iterator role;
    actors1.insert("moe");
    actors1.insert("curly");
    actors2.insert("larry");
    actors2.insert("curly");

    cout << "set 1 ";
    for (role = actors1.begin(); role != actors1.end(); ++role)
        cout << *role << " ";
    cout << endl;

    cout << "set 2";
    for (role = actors2.begin(); role != actors2.end(); ++role)
        cout << *role << " ";
    cout << endl;

    // Notice how we create the output iterator for the fifth argument:
    set<string> result;
    set_union(actors1.begin(), actors1.end(),
              actors2.begin(), actors2.end(),
              inserter(result, result.begin()));
    for (role = result.begin(); role != result.end(); ++role) {
        cout << *role << " ";
    }
    cout << endl;

    //demonstrate how to use node iterator for node template class
    node<int> *head_ptr = new node<int>(); // default val = 0
    list_head_insert(head_ptr, 42);
    list_head_insert(head_ptr, 13);
    list_head_insert(head_ptr, 67);

    node_iterator<int> start(head_ptr);
    node_iterator<int> finish;
    node_iterator<int> position;

    for (position = start; position != finish; ++position)
        cout << *position << " ";
    cout << endl;

    //demonstrate bag template class
    bag<int> bag_of_int;
    bag<string> bag_of_string;

    bag_of_int.insert(3);
    bag_of_string.insert("hello");
    bag_of_string.insert("goodbye");
    bag_of_string.insert("auf wiedersehen");
    bag_of_string.insert("goodbye");
    bag_of_string.insert("hello");
    bag_of_string.insert("goodbye");

    cout << "count of goodbye: " << bag_of_string.count("goodbye") << endl;
    cout << "count of guten morgen: " << bag_of_string.count("guten morgen") << endl;
    cout << "count of 3: " << bag_of_int.count(3) << endl;

    for (bag<string>::iterator cursor = bag_of_string.begin(); cursor != bag_of_string.end(); ++cursor)
        cout << *cursor << " ";
    cout << endl << endl;

    // NEW EXAMPLE
    // generate coffee bag
    bag<int> coffee_bag;
    int data[] = {7, 7, 1, 6, 5, 4, 3, 2, 1, 1};

    cout << "coffee bag with repetitions...\n";
    for (int i = 0; i < 10; i++) {
        coffee_bag.insert(data[i]);
    }
    for (bag<int>::iterator it = coffee_bag.begin(); it != coffee_bag.end(); ++it) {
        cout << *it << " ";
    }
    cout << '\n';

    cout << "Coffee bag without repetitions...\n";
    coffee_bag.remove_repetitions();
    for (auto it = coffee_bag.begin(); it != coffee_bag.end(); ++it) {
        cout << *it << " ";
    }
    cout << '\n';

    cout << "Items currently in coffee bag...\n";
    for (auto m : coffee_bag) cout << m << ' ';
    cout << '\n';
    cout << "Testing value range function using numbers 1-7..." << endl;
    coffee_bag.print_value_range(1, 7);
    cout << "Between range 2 - 5..." << endl;
    coffee_bag.print_value_range(2, 5);
    cout << "Between range 8 - 5..." << endl;
    coffee_bag.print_value_range(8, 5);
    cout << "Between range 1 - 16 (x to remainder of bag)..." << endl;
    coffee_bag.print_value_range(1, 16);

    // test get_items()
    cout << '\n';
    get_items(coffee_bag, 5, "numbers for coffee");

    cout << "coffee bag size: " << coffee_bag.size() << endl;
    for (auto m : coffee_bag) cout << m << ' ';
    cout << '\n';

    return 0;
}

bag.h

#ifndef BAG_H
#define BAG_H

#include <cstdlib>   // Provides size_t
#include "node.h"

template<typename Item>
class bag {
public:
    // TYPEDEFS
    typedef std::size_t size_type;
    typedef Item value_type;
    typedef node_iterator<Item> iterator;
    typedef const_node_iterator<Item> const_iterator;

    // CONSTRUCTORS and DESTRUCTOR
    bag();

    bag(const bag &source);

    ~bag();

    // MODIFICATION MEMBER FUNCTIONS
    size_type erase(const Item &target);

    bool erase_one(const Item &target);

    void insert(const Item &entry);

    void operator+=(const bag &addend);

    void operator=(const bag &source);

    void print_value_range(const Item &x, const Item &y);

    void remove_repetitions();

    // CONST MEMBER FUNCTIONS
    size_type count(const Item &target) const;

    Item grab() const;

    size_type size() const { return many_nodes; }

    // FUNCTIONS TO PROVIDE ITERATORS
    iterator begin() { return iterator(head_ptr); }

    const_iterator begin() const { return const_iterator(head_ptr); }

    iterator end() { return iterator(); } // nullptr, see constructor

    const_iterator end() const { return const_iterator(); }

private:
    node<Item> *head_ptr;
    size_type many_nodes;
};

// NONMEMBER functions for the bag
template<typename Item>
bag<Item> operator+(const bag<Item> &b1, const bag<Item> &b2);

// The implementation of a template class must be included in its header file:
#include "bag.template"

#endif // BAG_H

bag.template

#include <iostream>
#include <cassert> // Provides assert
#include "node.h"   // Provides node
#include "bag.h"

template<typename Item>
bag<Item>::bag() {
    head_ptr = nullptr;
    many_nodes = 0;
}

template<typename Item>
bag<Item>::bag(const bag<Item> &source) {
    node<Item> *tail_ptr; // Needed for argument of list_copy
    list_copy(source.head_ptr, head_ptr, tail_ptr);
    many_nodes = source.many_nodes;
}

template<typename Item>
bag<Item>::~bag() {
    list_clear(head_ptr);
    many_nodes = 0;
}

template<typename Item>
typename bag<Item>::size_type bag<Item>::count(const Item &target) const {
    size_type answer = 0;
    const node<Item> *cursor;

    cursor = list_search(head_ptr, target);
    while (cursor != nullptr) {
        ++answer;
        cursor = cursor->link();
        cursor = list_search(cursor, target);
    }
    return answer;
}

template<typename Item>
typename bag<Item>::size_type bag<Item>::erase(const Item &target) {
    size_type answer = 0;
    node<Item> *target_ptr;

    target_ptr = list_search(head_ptr, target);
    while (target_ptr != nullptr) {
        ++answer;
        --many_nodes;
        target_ptr->set_data(head_ptr->data());
        target_ptr = target_ptr->link();
        target_ptr = list_search(target_ptr, target);
        list_head_remove(head_ptr);
    }
    return answer;
}

template<typename Item>
bool bag<Item>::erase_one(const Item &target) {
    node<Item> *target_ptr;

    target_ptr = list_search(head_ptr, target);
    if (target_ptr == NULL)
        return false; // target isn't in the bag
    target_ptr->set_data(head_ptr->data());
    list_head_remove(head_ptr);
    --many_nodes;
    return true;
}

template<typename Item>
Item bag<Item>::grab() const {
    size_type i;
    const node<Item> *cursor;

    assert(size() > 0);
    i = (std::rand() % size()) + 1;
    cursor = list_locate(head_ptr, i);
    return cursor->data();
}

template<typename Item>
void bag<Item>::insert(const Item &entry) {
    list_head_insert(head_ptr, entry);
    ++many_nodes;
}

template<typename Item>
void bag<Item>::operator+=(const bag<Item> &addend) {
    node<Item> *copy_head_ptr;
    node<Item> *copy_tail_ptr;

    if (addend.many_nodes > 0) {
        list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
        copy_tail_ptr->set_link(head_ptr);
        head_ptr = copy_head_ptr;
        many_nodes += addend.many_nodes;
    }
}

template<typename Item>
void bag<Item>::operator=(const bag<Item> &source) {
    node<Item> *tail_ptr; // Needed for argument to list_copy

    if (this == &source)
        return;

    list_clear(head_ptr);
    many_nodes = 0;

    list_copy(source.head_ptr, head_ptr, tail_ptr);
    many_nodes = source.many_nodes;
}

template<typename Item>
bag<Item> operator+(const bag<Item> &b1, const bag<Item> &b2) {
    bag<Item> answer;

    answer += b1;
    answer += b2;
    return answer;
}

template<typename Item>
void bag<Item>::print_value_range(const Item &x, const Item &y) {
    if (list_search(head_ptr, x) == nullptr) {
        std::cout << "The starting value " << x << " is NOT in the list\n";
        return;
    }
    node<Item> *first_elem = list_search(head_ptr, x); // can use auto
    node<Item> *last_elem = list_search(head_ptr, y);
    while (first_elem != nullptr && first_elem != last_elem) {
        std::cout << first_elem->data() << ' ';
        if (first_elem == last_elem) break;
        first_elem = first_elem->link();
    }
    std::cout << '\n';
}

/**
* Removes all repetitions from the bag.
*/
template<typename Item>
void bag<Item>::remove_repetitions() {
    node<Item> *p;
    for (p = head_ptr; p != nullptr; p = p->link()) {
        node<Item> *q = p;
        while (q->link() != nullptr) {
            if (q->data() == p->data()) {
                list_remove(q);
            }
            q = q->link();
        }
    }
}

node.h

#ifndef NODE_H
#define NODE_H

#include <iterator> // Provides iterator and forward_iterator_tag

template<typename Item>
class node {
public:
    // TYPEDEF
    typedef Item value_type;

    // CONSTRUCTOR
    node(const Item &init_data = Item(), node *init_link = nullptr) {
        data_field = init_data;
        link_field = init_link;
    }

    // MODIFICATION MEMBER FUNCTIONS
    Item &data() { return data_field; }

    node *link() { return link_field; }

    void set_data(const Item &new_data) { data_field = new_data; }

    void set_link(node *new_link) { link_field = new_link; }

    // CONST MEMBER FUNCTIONS
    const Item &data() const { return data_field; }

    const node *link() const { return link_field; }

private:
    Item data_field;
    node *link_field;
};

// FUNCTIONS to manipulate a linked list:
template<typename Item>
void list_clear(node<Item> *&head_ptr);

template<typename Item>
void list_copy(const node<Item> *source_ptr, node<Item> *&head_ptr, node<Item> *&tail_ptr);

template<typename Item>
void list_head_insert(node<Item> *&head_ptr, const Item &entry);

template<typename Item>
void list_head_remove(node<Item> *&head_ptr);

template<typename Item>
void list_insert(node<Item> *previous_ptr, const Item &entry);

template<typename Item>
std::size_t list_length(const node<Item> *head_ptr);

template<class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position);

template<typename Item>
void list_remove(node<Item> *previous_ptr);

template<class NodePtr, class Item>
NodePtr list_search(NodePtr head_ptr, const Item &target);

template<typename Item>
class node_iterator : public std::iterator<std::forward_iterator_tag, Item> {
public:
    // CONSTRUCTOR
    node_iterator(node<Item> *initial = nullptr) { current = initial; }

    Item &operator*() const { return current->data(); }

    // Prefix ++
    node_iterator &operator++() {
        current = current->link();
        return *this;
    }

    // Postfix ++
    node_iterator operator++(int) {
        node_iterator original(current);
        current = current->link();
        return original;
    }

    bool operator==(const node_iterator other) const { return current == other.current; }

    bool operator!=(const node_iterator other) const { return current != other.current; }

private:
    node<Item> *current;
};

template<typename Item>
class const_node_iterator : public std::iterator<std::forward_iterator_tag, const Item> {
public:
    // CONSTRUCTOR
    const_node_iterator(const node<Item> *initial = nullptr) { current = initial; }

    const Item &operator*() const { return current->data(); }

    // Prefix ++
    const_node_iterator &operator++() {
        current = current->link();
        return *this;
    }

    // Postfix ++
    const_node_iterator operator++(int) {
        const_node_iterator original(current);
        current = current->link();
        return original;
    }

    bool operator==(const const_node_iterator other) const { return current == other.current; }

    bool operator!=(const const_node_iterator other) const { return current != other.current; }

private:
    const node<Item> *current;
};

#include "node.template"

#endif // NODE_H