Building a Dictionary with an Array-Based Bag in C++: A Step-by-Step Guide

Introduction

In CSIS 215, one of the key assignments is to implement a dictionary using an array-based bag. This project helps you understand data structure composition and ADT implementation in C++. In this tutorial, we'll walk through the approach, breaking down the bag and dictionary ADTs, and provide tips for testing and debugging. We'll also connect the concepts to a trending topic: building a leaderboard for a viral gaming app like Wordle or Connections.

Understanding the Bag ADT

A bag is a collection that allows duplicates and has no specific order. Think of it like a bag of Scrabble tiles—you can add tiles, remove them, and check if a tile is present. For our assignment, we'll create an array-based implementation of the bag ADT. The key functions include:

• addItem(const T& item) – inserts an item
• removeItem(const T& item) – removes one occurrence
• contains(const T& item) – checks existence
• size() – returns count of items
• isEmpty() – checks if bag is empty

We'll use a dynamic array internally, resizing when full. This is similar to how a gaming app stores player scores in a list—each score is an item, and duplicates are allowed if players tie.

Implementing the Array-Based Bag

Start by creating the ABag class that inherits from Bag. The provided template handles inheritance. Your implementation should include a private array and a count variable. For example:

template <typename T>
class ABag : public Bag<T> {
private:
    T* arr;
    int capacity;
    int itemCount;
public:
    ABag(int cap = 100);
    ~ABag();
    bool addItem(const T& item) override;
    bool removeItem(const T& item) override;
    bool contains(const T& item) const override;
    int size() const override;
    bool isEmpty() const override;
};

Implement addItem by appending to the array and increasing itemCount. For removeItem, find the item, shift elements left, and decrement count. Use a for loop to locate the index.

Building the Dictionary ADT

A dictionary stores key-value pairs. In our assignment, we use KVpair to hold the key and value. The dictionary must support:

• insert(KVpair<Key, E>& kv)
• remove(Key k)
• find(Key k)
• size()
• isEmpty()

We'll implement the dictionary using our bag. For example, insert calls bag.addItem(kv). find iterates through the bag to locate the key. This composition approach is like a gaming app that stores player profiles (key = player ID, value = score) in a bag—you can quickly add, remove, or look up a player.

Testing Your Implementation

Use the provided bagtestmain.cpp to test all functions. For each dictionary function, print a description and the result. For instance:

cout << "Testing insert: " << endl;
dict.insert(KVpair<int, string>(1, "Alice"));
cout << "Size after insert: " << dict.size() << endl;

Make sure to test edge cases: inserting duplicates, removing non-existent keys, and checking empty dictionary. If a function isn't fully implemented, modify the test to only call completed ones—but aim to implement all for full credit.

Debugging Tips

Debugging is a major part of this assignment. Use Visual Studio 2017's debugger to step through your code. Check pointer values in array-based bag to ensure you're not accessing out-of-bounds. For the dictionary, verify that find correctly compares keys using the == operator. Remember that KVpair requires the key type to support ==; avoid using Int type as it may not work.

Connecting to Trends

Imagine you're building the backend for a trending word game like Wordle. Each player has a unique ID (key) and their score (value). The dictionary stores these pairs, and the bag holds all pairs. When a new player joins, you insert. When they quit, you remove. You can find a player's score to display on a leaderboard. This real-world analogy makes the abstract concepts tangible.

Conclusion

By implementing the bag first and then the dictionary, you build a solid foundation in data structure composition. Test incrementally, debug patiently, and you'll succeed. Good luck with your CSIS 215 assignment!