动态数组 - 查找容量

Question

我一直在查看 std::vectors 源代码并查看其容量 (vector.capacity()) 函数的工作原理，我不太了解如何将其实现到我的 Dynamic数组源代码。我不会只是返回当前的容器大小。例如 dynarray.size()。 ,谢谢

#include <iostream>
#include <vector>
#include <iterator> 
#pragma once
template<typename T>
class DynamicArrayIter
{
public:
    DynamicArrayIter(T* data) : newData(data) { }
    //DynamicArrayIter(const DynamicArrayIter& o);                   // Copy constructor
    //DynamicArrayIter& operator=(const DynamicArrayIter& o);        // Assignment operator
    DynamicArrayIter operator++() { DynamicArrayIter i = *this;newData++; return i;}
    DynamicArrayIter operator++(int junk) {newData++;return *this; }
    T&   operator*() {return *newData; }                   
    bool operator==(const DynamicArrayIter& rhs) {return newData == rhs.newData; }
    bool operator!=(const DynamicArrayIter& rhs) { return newData != rhs.newData;}
    DynamicArrayIter<T> operator+(int _i)
    {
        DynamicArrayIter<T> iter = *this;
        for (int i = 0; i < _i; ++i)
        {
            if (iter.newData) //If there's something to move onto...
                ++iter;
            else
                break;
        }
        return iter; //Return regardless of whether its valid...
    }
private:
    T* newData;
};

template<typename T>
class DynamicArray
{
public:
    DynamicArray<T> operator=(const DynamicArray<T>&);//Dynamic Array equals Dynamic Array
    DynamicArray();//Constructor
    ~DynamicArray();//Destructor
    void push_back(const T&);//Push back a new element into the DynArray
    void pop_back();//Pop an element off the back of the DynArray
    void print();//Prints out what is in the container
    bool empty();//Empty the DynArray container
    void reserve(int);//Reserver a size of which the Dynarray can reach, once it reachers the limit it will increase etc.
    void resize(int);//resize the Dynrray container data will be carried into the new size either cutting off eccess data or reserving space for more.
    void swap(DynamicArray<T>);//Swap the contents in the Dynarray with another Dynarray containers.
    void assign(size_t,T);//Assign new content to the Dynarray, replacing the current elements and changing its size accordingly
    void assign(DynamicArrayIter<T>, DynamicArrayIter<T>);//Assign new content to the Dynarray, replacing the current elements and changing its size accordingly
    void insert(DynamicArrayIter<T>,T);//Insert a element at a certain positon elements will be moved and adjusted accordingly
    void erase(DynamicArrayIter<T>);//Erase an element at a certain postion
    void erase(DynamicArrayIter<T>,DynamicArrayIter<T>);//Erase an element at a certain postion
    T& at(int );// Element postion at index
    T& front();//elements t postion
    T& back();//elements back position
    T& operator[] (int);//subscript location access
    size_t capacity();//capacity of the container
    size_t max_size();//max size of the vontainer
    DynamicArrayIter<T> begin();//Begin on the container/DynArray - Iterator uses this to grab the begin of the Dynarray
    DynamicArrayIter<T> end();//End on the container/DynArray - Iterator uses this to grab the End of the Dynarray
    void clear();//Clear the whole container
    int size();//Size of the current container returns sizeofarray
private:
    T* myArray;//Where data is stored
    int sizeofarray = 0;//size of the current container
};

template<typename T>
inline DynamicArray<T> DynamicArray<T>::operator=(const DynamicArray<T>&newDynArray)
{
    myArray = new T[newDynArray.size()];
    for (size_t i = 0; i < newDynArray.size(); i++)//will make the current array the size of the new one
    {
        myArray[i] = newDynArray.myArray[i];//Current Dynarray = the pass in Dynarray - Steps through changign each element
    }
    return newDynArray;//return the passed data
}

template<typename T>
inline DynamicArray<T>::DynamicArray()
{
    myArray = new T[sizeofarray];//Creating a new Dynarray of size
}

template<typename T>
inline DynamicArray<T>::~DynamicArray()
{
    delete[] myArray;//deleting the Dynarray
}

template<typename T>
inline void DynamicArray<T>::push_back(const T& pusheddata)
{
        T *temp = myArray;//Creating a temp array with the value of the current Dynarray
        myArray = new T[++sizeofarray];//Dynarray = new Dynarray of current size + 1 // Size is being incremented from this
        myArray[sizeofarray - 1] = pusheddata;//Pushing the element onto the back of the Array
        for (int i = 0; i < sizeofarray - 1; ++i)//It is sizearray - 1 as we dont the temp does not have the data we just pushed onto the back
        {
            myArray[i] = temp[i];//going through a loop putting the data from the temp we created back into the DynArray.
        }

        delete[] temp;//delete the temp

}

template<typename T>
inline void DynamicArray<T>::pop_back()
{
    T *temp = myArray;//Creating a temp array with the value of the current Dynarray
    myArray = new T[sizeofarray--];//Dynarray = new Dynarray of current size - 1 // Size is being decreased from this
    for (int i = 0; i < sizeofarray; ++i)
    {
        myArray[i] = temp[i];//Dynarray equals the temp values
    }
    delete[] temp;//Delete the temp

}

template<typename T>
inline void DynamicArray<T>::print()
{
    for (size_t i = 0; i < sizeofarray; i++)
    {
        std::cout << myArray[i] << std::endl;//Just looping through and printing the element until it hits size.
    }

}

template<typename T>
inline bool DynamicArray<T>::empty()
{
    if (size() == 0)
    {
        return true;//return true if size is 0
    }
    return false;//return flase if size >=1
}

template<typename T>
inline void DynamicArray<T>::reserve(int r_size)
{
    sizeofarray = r_size;//size = the reserve size

}

template<typename T>
inline void DynamicArray<T>::resize(int newsize)
{
    T *temp = myArray;//Creating a temp with the current Dynarray inside of it
    myArray = new T[newsize];//Dynarray = a new Dynarray of size (newsize)
    for (int i = 0; i < newsize; ++i) 
    {
        myArray[i] = temp[i];//Setting the Dynarrays elements to the temps
    }
    for (int i = sizeofarray; i < newsize; i++)
    {
        myArray[i] = NULL;//Set the elements outside the size allowed to NULL
    }
    sizeofarray = newsize;//Size = new size
    delete[] temp;//delete the temp
}

template<typename T>
inline void DynamicArray<T>::swap(DynamicArray<T> newSwap)
{
    clear();//clear the current Dynarray
    for (size_t i = 0; i < newSwap.sizeofarray; i++)
    {
        myArray[i] = newSwap.myArray[i];//Newly cleared Dynarray elements = passed in swapped data
        sizeofarray++;//increment the size
    }
}

template<typename T>
inline void DynamicArray<T>::assign(size_t n, T val)
{
    clear();//Clear the Dynarray
    myArray = new T[n];//Dynarray = new Dynarray of size_t n
    for (size_t i = 0; i < n; i++)//for i < size_t n
    {
        myArray[i] = val;//Dynarray  = val passed through
        sizeofarray++;//increment the size of the Dynarray
    }
}

template<typename T>
inline void DynamicArray<T>::assign(DynamicArrayIter<T> first, DynamicArrayIter<T> last)
{
    int n = 0;//temp size holder
    for (DynamicArrayIter<T> iter = first; iter != last; ++iter) {
        n++;//increment the temp size holder
    }
    clear();//clear the Dynarray
    myArray = new T[n];//Make a new Dynarray and its size is the temp size holders
    for (DynamicArrayIter<T> newiter = first; newiter != last; ++newiter) {
        myArray[sizeofarray] = *newiter;//Iterate through and set each element to the value passed in
        sizeofarray++;//incremenet the size
    }
}

template<typename T>
inline void DynamicArray<T>::insert(DynamicArrayIter<T> position, T val)
{
    int sizeofthis = 0;//temp size holder for iter
    int j = 0;//Index position // increments when position is meet
    for (DynamicArrayIter<int> iter = begin(); iter != position; ++iter){
        ++sizeofthis;//increase the temp size holder fo riter
    }
    T *temp = myArray;//Create a new temp Dynarray
    sizeofarray += 1;//temp size hodler + 1
    myArray = new T[sizeofarray];//Dynarray = new Dynarray of temp size holder for iter
    for (size_t i = 0; i < sizeofarray; i++)
    {
        if (i == sizeofthis)//if the for loops i = tempsize holders
        {
            myArray[sizeofthis] = val;//Dynarray element = val being passed in
            j++;//Index pos ++
        }
        myArray[i + j] = temp[i];//Dynarray = Temps values // Will change when inserted pos is reached // dynamically chagne size
    }
    delete[] temp;//delete temp
}

template<typename T>
inline void DynamicArray<T>::erase(DynamicArrayIter<T> position)
{
    int sizeofthis = 0;//temp size holder for iter
    int j = 0;//index pos//increments wehn pos is met
    for (DynamicArrayIter<int> iter = begin(); iter != position; ++iter) {
        ++sizeofthis;//increment the temp size holder
    }
    T *temp = myArray;//temp = current Dynarray
    sizeofarray -= 1;//size decreased by 1
    myArray = new T[sizeofarray];//new Dynarray of the new size
    for (size_t i = 0; i < sizeofarray; i++)
    {
        if (i == sizeofthis)//if the loops i reaches the temp size holders value
        {
            myArray[sizeofthis] = myArray[sizeofthis + 1];//Dynarray at sizeoftihs = Dynarrays next element
            j++;//index pos ++
        }
        myArray[i] = temp[i + j];//Dynarray = the temp[idexpos will be greater > 0 if i == sizeofthis]

    }
    delete[] temp;//delete the temp

}

template<typename T>
inline void DynamicArray<T>::erase(DynamicArrayIter<T> first, DynamicArrayIter<T> last)
{
    int sizeofthis = 0;
    for (DynamicArrayIter<int> iter = first; iter != last; ++iter) {
        ++sizeofthis;
    }
    T *temp = myArray;
    sizeofarray = sizeofarray - sizeofthis - 1;
    myArray = new T[sizeofarray];
    for (size_t i = 0; i < sizeofarray; i++)
    {
        if (i < sizeofthis)
        {
            myArray[sizeofthis - 1 + i] =NULL;
        }
        myArray[i] = temp[i];

    }
    delete[] temp;

}

template<typename T>
inline T & DynamicArray<T>::at(int place)
{
    return myArray[place];//return the element at place
}

template<typename T>
inline T & DynamicArray<T>::front()
{
    return myArray[0];//return the first element in the array
}

template<typename T>
inline T & DynamicArray<T>::back()
{
    return myArray[sizeofarray];//return the last element in the array
}

template<typename T>
inline T & DynamicArray<T>::operator[](int place)
{
    return myArray[place];//return  the element at place using subscript operator instead of dynarray.at()
}

template<typename T>
inline size_t DynamicArray<T>::capacity()
{
    return back() - front();//
}

template<typename T>
inline size_t DynamicArray<T>::max_size()
{
    return std::numeric_limits<T>::max();
}

template<typename T>
inline DynamicArrayIter<T> DynamicArray<T>::begin()
{
    return DynamicArrayIter<T>(myArray);
}

template<typename T>
inline DynamicArrayIter<T> DynamicArray<T>::end()
{
    return DynamicArrayIter<T>(myArray + sizeofarray - 1);
}


template<typename T>
inline void DynamicArray<T>::clear()
{
    sizeofarray = 0;
    myArray = new T[sizeofarray];
    myArray[0] = NULL;
}

template<typename T>
inline int DynamicArray<T>::size()
{
    return sizeofarray;
}

Answer 1

size() returns 容器容纳的元素数量，而 capacity 是在必须分配更多 space 之前它可以容纳的元素数量。所以容量可以大于向量的大小。

在您的实现中，您必须再创建一个成员 capacity 来存储分配数组的实际大小，而 size 将保存容器所包含的元素数。

动态数组 - 查找容量

Dynamic Array - Finding Capacity

c++

stdvector

dynamic-arrays