Content

Arrays in C & C++ Containers Bounds Checking Array <- Go Back

EECS 281: Data Structures and Algorithms

Section 05

Arrays and Container Classes

University of Michigan at Ann Arbor

Last Edit Date: 06/03/2023

Disclaimer and Term of Use:

1. We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

2. This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.

3. This work is licensed under a Creative Commons Attribution 4.0 International License.

---

Arrays in C & C++

 1     char a[] = {'A', 'E', 'C', 'S'};
 2     a[0] = 'E';
 3     char c = a[2];     // now c contains 'C'
 4     char *p = a;       // now p points to the first 'E' in a
 5     p = &a[1];         // now p points to the second 'E' in a

Try it out:

Open in new window

Some properties of array:

• Allows random access in $O(1)$ time

• Index numbering always starts at 0

• Size of array must be separately stored

• No bounds checking

1D and 2D Arrays Conversion

1D Array	2D Array
int a1D[9];	int a2D[3][3];
column = index % num_columns; row = index / num_columnd;	index = row * num_columns + column;

Fixed Size 2D Arrays in C / C++

The following is a C-style fixed size 2D array:

 1     const size_t ROWS = 3, COLS = 3;
 2     int arr[ROWS][COLS];
 3     size_t r, c;
 4     int val = 0;
 5     for (r = 0; r < ROWS; ++r) {
 6         for (c = 0; c < COLS; ++c) {
 7             arr[r][c] = val++;
 8         }
 9     }

The following is a C++ fixed szie 2D array

 1     int a[3][3] = {{0, 1, 2},
 2                    {3, 4, 5},
 3                    {6, 7, 8}};

• No pointers used - safer code

• Size of 2D array set on initialization

• Uses less memory than pointer version

• g++ extension: can use variable as size declarator

2D Arrays with Double Pointers

 1     size_t rows, cols, r, c;
 2     cin >> rows >> cols;
 3     int **a = new int * [rows];
 4     for (r = 0; r < rows; ++r) {
 5         a[r] = new int[cols];
 6     }
 7     int val = 0;
 8     for (r = 0; r < rows; ++r) {
 9         for (c = 0; c < cols; ++c) {
10             a[r][c] = val++;
11         }
12     }
13
14     // Deleting data
15     for (r = 0; r < rows; ++r) {
16         delete[] a[r];
17     }
18     delete[] a;

Try it out:

Open in new window

Pros and Cons

i. Fixed

Allocated on the stake.

• Pros:

  • Deallocated when it goes out of scope (no delete)
  • a[i][j] uses one memory operation, not two

• Cons:

  • Does not work for large n, may crash
  • Size fixed at compile time
  • Difficult to pass as arguments to functions

• Avoid fixed-length buffers for variable-length input

  • This is a common source of security breaches

ii. Dynamic

Double-pointer arrays are allocated on the heap.

• Pros:

  • Support triangular arrays
  • Allow copying, swapping rows quickly
  • Size can be changed at runtime

• Cons:

  • Requires matching delete; can crash, leak memory
  • a[i][j] is slower than with build-in arrays

• C++ STL offers cleaner solutions such as vector<>

Containers

i. Introduction

• Objects that contain multiple data items (ex: ints, doubles or objects)

• Allow for control / protection over editing of objects

• Can copy / edit / sort / order many objects at once

• Used in creating more complex data structures

  • Containers within containers

  • Useful in searching through data

  • Databases can be viewed as fancy containers

• Example: vector, list, stack, queue, deque, map

• Use STL (standard template library)

• Container Class Operations

  • Constructor

  • Destructor

  • Add an element

  • Remove an element

  • Get an element

  • Get the size

  • Copy

  • Assign an element

ii. Accessing Container Items

• Sequential

• Finds n-th item by starting at beginning

  • Ex: linked list

• Used by disks in computers (slow)

• Random Access

• Finds n-th item by going directly n-th item

• Used by arrays to access data

• Used by main memory in computers (fast)

• Arrays can still proceed sequentially to copy, compare contents, etc.

iii. Copying an Array

1. Use pointer

 1     const size_t SIZE = 4;
 2     double src_ar[] = {3, 5, 6, 1};
 3     double dest_ar[SIZE];
 4
 5     for (size_t i = 0; i < SIZE; i++) {
 6         dest_ar[i] = src_ar[i];
 7     } 

Try it out:

Open in new window

2. No pointer

 1     const size_t SIZE = 4;
 2     double src_ar[] = {3, 5, 6, 1};
 3     double dest_ar[SIZE];
 4
 5     double *sptr = src_ar;
 6     double *dptr = dest_ar;
 7
 8     while (sptr != src_ar + SIZE) {
 9         *dptr++ = *sptr++;
10     }

Try it out:

Open in new window

iv. What to Store in a Container (Data Type)

	Value	Pointer	Reference
Example	char data;	char* data;	char &data(c);
Data ownership	Only container edits / deletes	Container or other object	None: cannot delete by reference
Drabacks	Large objects take time to copy	Unsafe	Must be initialized but cannot be assigned to
Usage	Most common	Used for char*, shared data	Impractical in most cases

v. What to Get from a Container (Return Type)

	Value	Ptr, Const ptr	Reference, const ref
Example	char getElt(int);	char *getElt(int);	char &getElt(int);
Notes	Costly for copying lage objects	Unsafe, pointer may be invalid	Usually a good choice

vi. Memory Ownership

1. Issues

• Options for copy-construction and assignment

  • Duplicate objects are created

  • Duplicate pointers to objects are created

    • Multiple containers will point to the same object

• Default copy-constructor duplicates pointers

• Idea 1: Each object owned by a single container

• Idea 2: Use no ownership

  • Objects expire when no longer needed

    • Program must be watched by a "big brother"

    • Garbage collector - potential performance overhead

  • Automatic garbage collection in Java

    • Possible in C++ with additional libraries or "smart objects"

2. Pointers

• Objects could be owned by another container

  • Container may not allow access to objects (privacy, safety)

  • Trying to delete same chunck of memory twice may crash the program

• Destructor may need to delete each object

  • Inability to delete objects could cause memory leak

Safty Tip:

Do not use delete ptr solely. Instead, use:

delete ptr;
ptr = nullptr;

v. Memory Leak

• When your program finishes, all memory should be deallocated

  • The remaining memory is "leaked"

  • C++ runtime may or may not complain

  • The OS will deallocate the memory

• Your code shoule be reuseable in a larger system

  • If your code is called 100 times and leaks memory, it will exhaust all available memory and crash

Bounds Checking Array

i. Creating Objects & Dynamic Arrays in C++

• new calls default constructor to create an object

• new[] calls default constructor for each object in an array

  • No constructor calls when dealing with basic types (int, double)

  • No initialization either

• delete invokes destructor to dispose of the object

• delete[] invokes destructor on each object in an array

  • No destructor calls when dealing with basic types (int, double)

• Use delete on memory allocated with new

• Use delete[] on memory allocated with new[]

ii. The Big 5 to Implement

• Destructor

• Copy Constructor

• Overloaded operator=()

• Copy Constructor from r-value

• Overloaded operator=() from r-value

Adding Bounds Checking to Arrays

 1     class Array {
 2         size_t length = 0;
 3         double *data = nullptr;
 4    
 5     public:
 6         Array(size_t len) : length{len},
 7                             data{new double[length]} {}
 8         ~Array {
 9             delete[] data;
10             data = nullptr;
11         }
12    
13         size_t size() const {
14             return length;
15         }
16     };

Copy Constructor

The following implementation does a deep copy.

Array(const Array &a) : length{a.length},                 // 1 step
                        data{new double[length]} {        // 1 step
    for (size_t i = 0; i < length; i++) {                 // n times
        data[i] = a.data[i];                              // c steps
    }
}

Total steps: 1 + 1 + 1 + (n * (2 + c)) + 1 = $O(n)$

Best case, average case, worst case: $O(n)$

Better Copying

 1     void copyFrom(const Array &other) { // deep copy
 2         delete[] data; // safe to delete even if nullptr
 3         length = other.length;
 4         data = new double[length];
 5
 6         // Copy array
 7         for (size_t i = 0; i < length; ++i)
 8             data[i] = other.data[i];
 9     } // copyFrom()
10
11     Array(const Array &other) {
12         copyFrom(other);
13     } // Array()
14
15     Array &operator=(const Array &other) {
16         if (this != &other) // idiot check
17             copyFrom(other);
18         return *this;
19     } // operator=(

Best Copying

Use std::swap in <utility>.

 1     #include <utility> // Access to swap
 2
 3     Array(const Array &other) : length{other.length},
 4                                 data{new double[length]} {
 5         // copy array contents
 6         for (size_t i = 0; i < length; ++i)
 7             data[i] = other.data[i];
 8     } // Array()
 9
10     Array &operator=(const Array &other) { // Copy-swap method
11             Array temp(other); // use copy constructor to create object
12
13         // swap this object's data and length with those from temp
14         std::swap(length, temp.length);
15         std::swap(data, temp.data);
16
17         return *this; // delete original, return copied object
18     } // operator=()

operator[]

1. Non-const version

double &operator[] (size_t i) {
    if (i < length)
        return data[i];
    throw runtime_error("bad i");
}

2. const version

const double &operator[] (size_t i) const {
    if (i < length)
        return data[i];
    throw runtime_error("bad index");
}

• Declares read-only access

  • Compiler enforced

  • Returned reference don't allow modification

• Automatically selected by the compiler when an array being access is const

• Helps compiler optimize code for speed

Note: We need the const version, because only the const version can access read-only data.

Inserting an Element

bool Array::insert(size_t index, double val) {
    if (index >= length)
        return false;
    for (size_t i = length - 1; i > index; i--)
        data[i] = data[i - 1];
    data[index] = val;
    return true;
}

Complexity analysis:

• Best case: $O(1)$

  • Inserting after existing data

  • No data shifted

• Average case: $O(n)$

• Worst case: $O(n)$

  • Inserting before all existing data

  • All data shifted

© Sample Academy