1 Introduction

The array (Fig. 1↓) is the simplest storage in C or C++; novices can use only a few instructions to create an array to store a series of data. However, the array has several drawbacks: 1) If the array is dynamic, users should remember to release the allocated memory space to avoid memory leakage, 2) growing or shrinking an array, compared to other data structures such as linked lists, is neither flexible nor efficient, 3) no protection is imposed on the data stored in an array; users can simply access any valid data members through the corresponding memory addresses, and 4) according to ANSI C standards, only the default constructor is allowd to be called to create an array of objects.
figure array.png
Figure 1 The array. Only the default constructor of a class (symbolized as T()) can be used to construct the elements in the array.
The first three shortcomings are well-understood, but the last one appears unfamiliar. Imagine that a user wants to create an array for storing objects of a class “A” whose fields contain dynamically allocated memory. Because only the default constructor is allowed to be used and since the default constructor is usually not configured to be responsible for the dynamic memory allocation, the user cannot avoid calling the default constructor first and then using other member functions to configure the memory, which is redundant and less efficient than the direct use of a constructor of class A that jointly performs the aforementioned two steps.
In this project, we design a container more sophisticated than the array. On the one hand, this container should be configured to own the advantanges of the array; on the other hand, it should be designed to avoid the drawbacks mentioned above. The container is referred to as “Vector” to reflect its similarity to the STL vector.

2 Container design

Compared to the array (as illustrated in Fig. 1↑), the structure of the Vector is depicted in Fig. 2↓, in which an array is encapsulated as a private data member in a class. With appropriate designs of the class, the first three drawbacks mentioned above can be overcome. However, the last issue requires a special approach to resolve: “placement new and delete” (sometimes referred to as “in-place new and delete”).
The placement new offers a user to construct an object at an allocated memory address, and the placement delete allows a user to explicitly call the destructor of an object at a known memory address. Therefore, we use “malloc” to allocate memory storage, in which all the contents inside are invalid, and use placement new to construct objects (not necessarily through the default constructor) to form valid data at specified allocated position. Likewise, we use placement delete to destruct objects in the storage and eventually free (using the “free” command) it. With the collaboration of the C-style memory management (malloc and free) and C++-style data configuration (the placement new and delete), a user can always reserve more space than the required space of valid data, such as the red elements shown in Fig. 2↓, for memory allocation and deallocation are usually slow.
figure vector.png
Figure 2 Vector. Unlike the array, only a portion of allocated memory is occupied by valid data.

2.1 Methods

Since the storage of data is encapsulated in a class, as shown in Fig. 2↑, the access of the stored data requires a special class—the iterator. In practical applications, a container usually has more than one type of iterator and the classes of the iterators are usually designed as nested classes of the container. However, we only implement an iterator needed by some specific methods (demonstrated below). Moreover, to simplify the implementation of Vector, we can separately design the patterns of the iterator and the container and declare the container as the friend class of the iterator.
The implementation of some methods of Vector is illustrated as follows:

2.1.1 Insert

This purpose of this method is to insert an element to an address referenced to by the iterator. If the reserved space accommodates an additional data member, as illustrated in Fig. 3↓, the element referenced to by the iterator and other following elements are moved backward by one unit; the inserted element is constructed at the spared space.
figure insert_space_enough.png
Figure 3 Insert
By constrast, if the reserved space is not enough for one more data element, as illustrated in Fig. 4↓, a new array is allocated to store all original elements and the one intended to be inserted. Note that the reserved space of the newly allocated storage is usually twice as large as that of the current demand.
figure insert_space_insufficient.png
Figure 4 Insert (under the condition that the reserved space is not sufficient for one more data element)

2.1.2 Erase

This purpose of this method is to erase an element referenced to by the iterator. As shown in Fig. 5↓, the specified element is destructed using placement delete and the following elements are sequentially moved toward by one unit (using placement new and delete, too).
figure erase.png
Figure 5 Erase

2.1.3 Push_back

This purpose of this method is to push an element to the end of the valid data. Depending on the space left in the reserved memory, two possible implementation is discussed in the following figures (Figs. 6↓ and 7↓). This method is a special case of the “Insert” method.
figure push_back_enough.png
Figure 6 Push_back (under the condition that the reserved space accommodates one more data element).
figure push_back_insufficient.png
Figure 7 Push_back (under the condition that the reserved space can NOT accomodate one more data element).

2.1.4 Push_front

This purpose of this method is to push an element to the very front of the valid data. Two possible implementation is discussed in the following figures (Figs. 8↓ and 9↓). This method is a special case of the “Insert” method.
figure push_front_enough.png
Figure 8 Push_front (under the condition that the reserved space accomodates one more data element).
figure push_front_insufficient.png
Figure 9 Push_front (under the condition that the reserved space can NOT accomodate one more data element).

2.1.5 Pop_back

This purpose of this method is to pop out the last valid data. As shown in Fig. 10↓, this method is a special case of the “Erase” method.
figure pop_back.png
Figure 10 Pop_back

2.1.6 Pop_front

This purpose of this method is to pop out the first valid data. As shown in Fig. 11↓, this method is a special case of the “Erase” method.
figure pop_front.png
Figure 11 Pop_front

3 Miscellaneous

To avoid design flaws of our container, we use Valgrind to scrutinize possible memory leaks of our program. By entering “valgrind --leak-check=full --log-file=vglog ./_name_of_executable,” we export the analyses of the memory usage completed by valgrind to the file “vglog.” If the “All heap blocks were freed — no leaks are possible” is shown at the end of vglog, then the container performs correct allocation and deallocation during its use. Otherwise, Valgrind prints out the clues of the lines that memory leaks take place.