UTK Notes

Home / CS102 / EthanNotes / Lab 10 - Vectors From Scratch

• Lab 10 - Vectors From Scratch
  • Table of contents
  • Introduction
  • Methods
    • doublevector()
    • ~doublevector()
    • doublevector::resize(int new_size, double initial_value)
    • doublevector::push_back(double value)
    • doublevector::at(int index)
    • Tips
  • Restrictions
  • More on memory leaks
  • Testing
    • Prerequisite
    • The Makefile
    • make
    • make test
    • make leak
      • example memory leak output
    • make clean
  • That’s it

Lab 10 - Vectors From Scratch

Table of contents

• Lab 10 - Vectors From Scratch
  • Table of contents
  • Introduction
  • Methods
    • doublevector()
    • ~doublevector()
    • doublevector::resize(int new_size, double initial_value)
    • doublevector::push_back(double value)
    • doublevector::at(int index)
    • Tips
  • Restrictions
  • More on memory leaks
  • Testing
    • Prerequisite
    • The Makefile
    • make
    • make test
    • make leak
      • example memory leak output
    • make clean
  • That’s it

Introduction

In this lab, you will implement the std::vector class from scratch.

If you didn’t know already, std::vector is a class that represents a dynamic array. So from like from lab 9, you’re creating a dynamic array, but this time we’ll utilize the true power of what makes arrays dynamic by implementing resizing capabilities.

Methods

doublevector()

This is the constructor. It should initialize the vector to have an initial size of 0 (mNumValues), and set its pointer (mValues) to nullptr. This is a keyword in C++ basically means “nothing”. It’s a special value that is used to represent a null pointer.

~doublevector()

This is the destructor., it is automatically called behind the scenes whenever your doublevector object is destroyed i.e. goes out of scope. It should free the memory that the vector is using (just one pointer to an array) delete[], just like in lab 9.

Short

The constructor and destructor are pretty self-explanatory, so I won’t go into them much more.

doublevector::resize(int new_size, double initial_value)

This is the meat of the lab. This method should resize the vector to have a new size of new_size. If the new size is smaller than the current size, then the vector should be truncated to that size. If the new size is larger than the current size, then the vector should be resized and the new elements should be initialized.

The methodology for this is simple. To effectively “resize”, what we really do is create new array with the new size. Then we copy over the old values from the current array to the new array. Then we delete the old array and set the current array pointer to the new array.

Steps:

1. Create a new array with the new size
2. Copy over the old values from the current array to the new array
3. Delete the old array
4. Set the current array pointer to the new array

Pretty simple honestly.

doublevector::push_back(double value)

This method should add a new value to the end of the vector. It should do this by first resizing the vector to be one element larger, and then setting the last element to the new value. Make sure you’re not just re-implementing resize() here. You can just call it and then set the last element to the new value.

doublevector::at(int index)

This method should return the value at the given index. Make sure you’re handling if the vector is empty or if the index is out of bounds (hint: use size()). If either of those is the case, you should print an error Invalid Index #x, where x is the index that was passed in.

Tips

• Whenever you “dereference” a pointer, make sure you check if it’s nullptr first. If it is, then you’re doing something wrong. nullptr basically means you haven’t assigned an address to the pointer you’re trying to dereference yet. So whenever you dereference a pointer using * or ->, make sure you check to see if it points to anything first with pointer == nullptr.

• Whenever you’re creating a new array, make sure you delete the old one first. If you don’t, you’ll have a memory leak, which means your program is still using memory for something you don’t need anymore.

• Most of the diffculty in this lab is making sure you chose new and delete correctly. You’ll rarely want a nullptr lying around.

• Do the constructor, size(), and at() first. Then do resize(), then do push_back() (in that order). resize() will use at(), and push_back() use resize().

Restrictions

• No C-style memory allocation (malloc or free).

• All methods are written beneath main().

• No memory leaks.

• No additional headers other than what’s included.

• No modifying the class or anything in main().

Must compile with

g++ -Wall -std=c++11 -O0 -g -o lab10 lab10.cpp

More on memory leaks

It’s not very clear whether or not your program has a memory leak without some sort of tooling to identify it. So once you’ve completed the whole lab, you can download the Makefile in the Testing section and run make test to see if your program has any memory leaks. If it does, it will print out the line number where the memory leak occurred.

---

Testing

Prerequisite

Unix environment (MacOS, Linux, WSL, etc.)

make installed. Should be installed by default on MacOS and Linux.

unzip package. Should be installed but if not, run sudo apt install unzip on Ubuntu/WSL, or brew install unzip on MacOS.

The Makefile

You can download the makefile with the following command:

curl -L https://raw.githubusercontent.com/Ethan0429/cs102-writeups/main/lab10/Makefile --output Makefile

or

curl -L https://utknotes.pisaucer.com/CS102/EthanNotes/Lab10/Makefile.txt --output Makefile

This will download th makefile to your current directory

make

This will compile your program. That is it.

make

make test

This will test your program for the inputs shown on Canvas, as well as print the diff’ed output between the two.

make test

make leak

This will compile your program and run it through valgrind to check for memory leaks. If there are no memory leaks, it will print out No memory leaks. If there are memory leaks, it will print out the line number of your program where the memory leak occurred. It will show you how many bytes you’ve lost (usually around the same size as your array in bytes), and the trace of where the leak occurred. The trace is the path that lead to the memory leak, starting from the bottom up.

example memory leak output

==8446== 0 bytes in 1 blocks are definitely lost in loss record 1 of 2
==8446== at 0x4C2E80F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8446== by 0x4028F5: doublevector::resize(int, double) (lab10.cpp:121)
==8446== by 0x402418: main (lab10.cpp:61)
==8446== definitely lost: 0 bytes in 1 blocks

As you can see, it starts from main, goes to resize(), line 121, and then finally shows the cause of the leak, which is operator new[](unsigned long). This is the line that actually allocates the memory for the array. So the leak is in resize().

The output above shows 0 bytes were lost, but that’s just because the example input resizes the leaking array to 0, so technically no bytes were lost. If you resize the array to a non-zero size, then you’ll see the bytes lost. However, the pointer is still dangling, so it will still show up as a memory leak.

In particular, this command can only be run on a Linux machine, so only run it if you’re on the lab machine or are running a Linux distribution on your own machine. This is because the leak checking requires valgrind to be installed, which is only available on Linux.

make leak

make clean

This will remove the executable and test files.

make clean

---

That’s it