logo

UTK Notes


Lab 10: Vectors from Scratch

Assignment

You will be creating the “vector” class manually by using pointers and dynamic memory (new/delete). It will be called doublevector, and it will support most of the member functions used in the regular vector class. Notice that the <> are NOT used for this class. These are used for “templates”, which have not been used in this course.

NOTICE: You will NOT be writing any set-up code or int main(). Those have already been written for you in the lab 10 template. You are just required to write the appropriate member functions for the doublevector class.

Template

The following must be used for your doublevector class. It (and the testing code) can be downloaded through Canvas: lab10.cpp



1
2
3
4
5
6
7
8
9
10
11
12
13



class doublevector {
     static constexpr double DOUBLE_DEFAULT_VALUE = -5.55;
     double *mValues;
     int mNumValues;
public:
     doublevector();
     ~doublevector();
     void resize(int new_size, double initial_value=DOUBLE_DEFAULT_VALUE);
     void push_back(double value);
     double &at(int index);
     const double &at(int index) const;
     unsigned long size() const;
};

Members



1



double *mValues

All of the data will be stored in mValues. Remember, you can treat a pointer as an array! This variable must be treated gingerly since dereferencing a nullptr will cause segmentation faults–your program crashes. NEVER dereference a pointer with 0 values.



1



int mNumValues

This stores how many values will be inside of mValues. This will be 0 if mValues is set to nullptr.



1



doublevector() { }

This is a constructor. This will construct a new doublevector whose size is 0. DO NOT allocate any dynamic memory for mValues! Make sure you set mValues = nullptr; for a subsequent check.



1



~doublevector() { }

This is a deconstructor. It is called automatically when “delete” is used on an object. This will destruct your double vector. It is responsible for freeing any resources in mValues. MAKE SURE you check the validity of mValues PRIOR to deleting it!



1



void resize(int new_size, double initial_value) { }

This will resize the doublevector to the given new_size. Do nothing if new_size is < 0. If new_size is 0, free all memory related to mValues. Remember to ALWAYS check the validity of your pointer before using it or freeing it!. Otherwise, if new_size > size, then you will need to create new memory, copy the old to the new, delete the old, and then set the initial values of the NEW values to initial_value. Lastly, if new_size < size, then all you need to do is create a smaller double pointer, copy new_size elements over, and then delete the larger mValues pointer. REMEMBER: to reset mValues = your new pointer and reset mNumValues to the new_size!!



1



void push_back(double value) { }

This member function will increase the size of the vector by 1, adding value to the bottom of the vector.



1



double &at(int index) { }

This member function will return a reference to the value at the given index. Make sure you write the following to check the validity of index. You don’t have to know what is happening here, but the actual out_of_range class is documented here: http://www.cplusplus.com/reference/stdexcept/out_of_range/



1
2
3
4
5



if (index >= mNumValues) {
       ostringstream sout;
       sout << "Invalid index #" << index;
       throw out_of_range(sout.str());
}





1



const double &at(int index) const { }

This member function will return a read-only reference to the value at the given index. This member function will perform the exact same operation as the non-read-only version. The reason this is necessary is because C++ will choose one over the other depending on whether your class is constant or not.



1



unsigned long size() const { }

This member function will typecast your mNumValues into an unsigned long and return it.

Example Interaction



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49



~$ ./lab10
Enter a command ('quit' to quit): get 0
Value at 0 = Invalid index #0     <-- You might only get "Invalid index #0" on Tesla
Enter a command ('quit' to quit): set 0 10
Invalid index #0
Enter a command ('quit' to quit): print
Vector is empty.
Enter a command ('quit' to quit): push_back 10
Pushed back 10.0000
Enter a command ('quit' to quit): push_back 33.4
Pushed back 33.4000
Enter a command ('quit' to quit): get 0
Value at 0 = 10.0000
Enter a command ('quit' to quit): get 1
Value at 1 = 33.4000
Enter a command ('quit' to quit): print
[000] = 10.0000
[001] = 33.4000
Enter a command ('quit' to quit): resize 10
Enter a command ('quit' to quit): get 0
Value at 0 = 10.0000
Enter a command ('quit' to quit): print
[000] = 10.0000
[001] = 33.4000
[002] = -5.5500
[003] = -5.5500
[004] = -5.5500
[005] = -5.5500
[006] = -5.5500
[007] = -5.5500
[008] = -5.5500
[009] = -5.5500
Enter a command ('quit' to quit): set 2 22.14
SET: 2 = 22.1400
Enter a command ('quit' to quit): print
[000] = 10.0000
[001] = 33.4000
[002] = 22.1400
[003] = -5.5500
[004] = -5.5500
[005] = -5.5500
[006] = -5.5500
[007] = -5.5500
[008] = -5.5500
[009] = -5.5500
Enter a command ('quit' to quit): resize 0
Enter a command ('quit' to quit): print
Vector is empty.
Enter a command ('quit' to quit): quit

Hints

  1. Work on doublevector(), ~doublevector(), at() [both of them], and size() first. These functions are fairly simple and do not require a lot of code. Remember that both at() functions have an error check, but that code has been provided for you. resize() will be the only function that contains more than one line, and it should take the majority share of your time on this lab.

  2. push_back() is essentially resize(mNumValues + 1, value).

  3. When you resize, there are three conditions: new_size > size, new_size < size, or new_size == size.

3a. If new_size > size, your job is to grow the vector. This means you need to copy over size values to a new pointer that contains new_size values. After you’ve copied over size values, you set new_size - size values to the initial value. REMEMBER to delete the old mValues if it exists (!= nullptr) and reset it with the value of the new pointer.

3b. If new_size < size, you need to shrink the vector. This is simpler than 3a because all you need to do is create a new pointer, copy over new_size values, and then reset mValues and mNumValues to the new pointer and new_size values.

3c. If new_size == size, then there is nothing to do.

  1. Segmentation faults will abound if you misuse a pointer. You can use gdb ./lab10 then type run . Should you encounter a segmentation fault, it will tell you which line it was caused by ASSUMING you used the command line shown under the Submission section.

  2. Never let your pointers dangle! Before ever losing your pointer information, make sure it is deleted! Also, you’re using the pointer as an array, so make sure you use the proper new and delete operators. Remember, there are two versions of the new operator and two versions of the delete operator.

  3. In your pointer check, you will notice that mNumValues will be 0 when mValues is nullptr. You are permitted to use either member to do your pointer check. The point is that you must never delete or dereference a null pointer!

Restrictions

  1. You may NOT use malloc(), calloc(), free() or any other C-style memory allocation (if you don’t know what that is - that’s normal, we haven’t talked about C in this class).

  2. You MUST use the proper versions of new and delete.

  3. The doublevector member functions MUST be written below int main().

  4. You must NOT have any memory leaks. Make sure you delete all memory when you’re done using it.

  5. You do NOT need to check if new returned a valid memory value. If you use the proper value, it will throw an exception. You do NOT need to handle this exception, either.

  6. You may NOT include any additional headers than what are specified in lab10.cpp.

  7. You may NOT modify the template’s class prototype, print_all function, and int main function.

GDB Example



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25



~$ g++ -Wall -std=c++11 -O0 -g -o lab10 lab10.cpp
~$ gdb ./lab10
GNU gdb (GDB) 8.2
Copyright (C) 2018 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./lab13...done.
(gdb) run
Starting program: /home/smarz/Develop/cs102/labs/lab10/lab10

Program received signal SIGSEGV, Segmentation fault.
0x0000555555556edf in doublevector::at (this=0x0, index=0) at lab10.cpp:174
174             if (index >= mNumValues) {
(gdb) quit

This tells me that line 174 in lab10.cpp is faulty. Also, notice that the implicit ‘this’ parameter is 0x0, which means that it is nullptr. So, whenever I try to get this->mNumValues, it causes a segmentation fault!

Submission

Use the following command to compile your file:



1



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

Submit your lab10.cpp. Make sure that it compiles and can be tested using the Tesla machines and the command above!