C++ vector

#include <iostream>
using namespace std;
#include <vector>
int main()
{
	vector<int> v{ 1,2,3,4,5,6 };
	auto it = v.begin();
	v.assign(100, 3);
	//因为这里扩容过，所以迭代器肯定失效
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

解决这个办法就是更新一下迭代器即可正常使用。

看看其他例子：

int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// 使用find查找3所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据，导致pos迭代器失效。
	v.erase(pos);
	cout << *pos << endl; // 此处会导致非法访问
	return 0;
}

int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}
 
	return 0;
}

int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			it = v.erase(it);
		else
		{
			++it;
		}
	}
	for (auto& e : v)
	{
		cout << e << endl;
	}
	return 0;
}

// 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了
int main()
{
	vector<int> v{ 1,2,3,4,5 };
	for (size_t i = 0; i < v.size(); ++i)
		cout << v[i] << " ";
	cout << endl;
	auto it = v.begin();
	cout << "扩容之前，vector的容量为: " << v.capacity() << endl;
	// 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效 
	v.reserve(100);
	cout << "扩容之后，vector的容量为: " << v.capacity() << endl;
 
	// 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux下不会
	// 虽然可能运行，但是输出的结果是不对的
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        //先开辟空间
        vector<vector<int>> vv;
        vv.resize(numRows);
        for(size_t i= 0 ;i<vv.size();++i)
        {
           vv[i].resize(i+1,0);
           vv[i][0] = vv[i][vv[i].size()-1] = 1;
        }
        //把剩下为0的位置处理以下
        for(size_t i= 0;i<vv.size();++i)
        {
            for(size_t j = 0;j<vv[i].size();++j)
            {
                if(vv[i][j] == 0)
                {
                    vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
                }
            }
        }
        return vv;
    }
};

2.力扣

这道题如果使用哈希表的话就超出了这个空间复杂度了，用暴力查找的方式又不符合题意，这里有一个思路非常巧妙：

我们可以利用位运算来解决，因为这个除了这个数字其他的数字都出现过3次，我们可以把数组中的每一个数字的二进制位加起来，然后让结果%3就可以得到我们所想要的二进制位了，（不论是0还是1，%3的结果都是我们想要的那个数的二进制位），最后我们用ret每次接受一下要的到二进制位，就可以得到答案。

代码实现：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //我们可以把所有的二进制位全部加起来，然后%3就可以得到所求的数字的二进制位了
        int ret = 0;//我们要求的数字
        for(int i = 0;i<32;++i)
        {
            int sum = 0;
            for(auto e:nums)
            {
                sum += ((e>>i) & 1);
            }
            //把要求的数字的二进制位找出来
            if(sum%3)
            {
                ret |= (1<<i);
            }
        }
        return ret;
    }
};

3.数组中出现次数超过一半的数字_牛客题霸_牛客网

思路：因为所出现的元素的个数超过了一般半，我们就可以通过计数的方式记录它，如果是这个元素就++，不是就--，最后得到的那个数一定是我们想要的数，另外，我们还可以拓展一下：如果这个数不一定存在那要怎么处理？

我们可以对这个记录一下这个数，然后再遍历一次数组，通过计数的方式去确认是否存在。

代码实现：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    //因为所出现的元素的个数超过了一般半，我们就可以通过计数的方式记录它，如果是这个元素就++，不是就--
    //这样的话就可以在最后的时候找到这个元素
    int tmp = numbers[0];//记录我们要求的数据
    int times = 1;
    for(int i = 1;i<numbers.size();++i)
    {
        //如果次数减到0就把tmp换成下一个元素
        if(times == 0)
        {
            tmp = numbers[i];
            times = 1;
        }
        if(numbers[i] == tmp)
        {
            ++times;
        }
        else{
            --times;
        }
    }
    //到这里就已经找到了就是tmp
    return tmp;
    }
    
};

4.力扣

这一题的难度比较大，运用到了回溯算法

思路：

我们可以通过一个数组来记录数字与字母之间的映射关系，然后利用回溯算法（递归）就解决像这种组合问题，下面通过这题来大概讲解一下回溯：

 这个很像二叉树的遍历，但又复杂一点，这个可以看成多叉树的遍历方式。我们可以通过每一层的递归来达到一个组合的效果。

代码实现：

class Solution {
    //映射数组
    string numstr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    //递归子函数
    void combine(string& digits,int i,vector<string>& vcombine,string retstr)
    {
        if(i == digits.size())
        {
            vcombine.push_back(retstr);
            return;
        }
        //找到对应的字母
        int num = digits[i]- '0';
         string str = numstr[num];
         //遍历串中的所有字符，然后进入下一层
         for(auto ch:str)
         {
             combine(digits,i+1,vcombine,retstr+ch);
         }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> vcombine;
        if(digits.empty())
        {
            return vcombine;
        }
        int i = 0;
        string retstr;//用来每次加，然后最后加到vcombine中 
        //递归
        combine(digits,i,vcombine,retstr);
        return vcombine;
    }
};

下面通过画递归展开图再来看看其中的细节：

2.vector深度剖析及模拟实现

使用memcpy拷贝问题

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中

2. 如果拷贝的是自定义类型的元素， memcpy 既高效又不会出错，但 如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

这个和之前讲拷贝构造的时候很像，都是浅拷贝导致的问题。 可能会引起内存泄漏甚至程序崩溃。

动态二维数组理解

在前面就已经看过了二维数组的题了，这里不过多介绍，还是介绍一下memcpy也会使内存崩溃的结果：

 要解决这个问题，我们还是要进行深拷贝，这是下面的reserve的模拟实现代码来解决这个问题：

 我们可以通过这个一个对象赋值的方式来进行深拷贝

模拟实现vector：

template<class T>
    class vector
    {
    public:
        // Vector的迭代器是一个原生指针
            typedef T* iterator;
            typedef const T* const_iterator;
 
            iterator begin()
            {
                return _start;
            }
            iterator end()
            {
                return _end;
            }
            const_iterator cbegin()
            {
                return _start;
            }
            const_iterator cend() const
            {
                return _end;
            }
 
            // construct and destroy
 
            vector()
                :_start(nullptr)
                ,_end(nullptr)
                ,_endOfStorage(nullptr)
            {}
 
            vector(int n, const T& value = T())
                :_start(nullptr)
                , _end(nullptr)
                , _endOfStorage(nullptr)
            {
                reserve(n);
                for (int i = 0; i < n; ++i)
                {
                    push_back(value);
                }
            }
 
            template<class InputIterator>
 
            vector(InputIterator first, InputIterator last)
                :_start(nullptr)
                , _end(nullptr)
                , _endOfStorage(nullptr)
            {
                while (first != last)
                {
                    push_back(*first);
                    ++first;
                }
            }
 
            vector(const vector<T>& v)
                :_start(nullptr)
                , _end(nullptr)
                , _endOfStorage(nullptr)
            {
                //找个工具人
                vector<T> tmp(v._start, v._end);
                swap(tmp);
            }
 
            vector<T>& operator= (vector<T> v)
            {
                swap(v);
                return *this;
            }
 
            ~vector()
            {
                delete[] _start;
                _start = _end = _endOfStorage = nullptr;
            }
 
            // capacity
 
            size_t size() const
            {
                return _end - _start;
            }
 
            size_t capacity() const
            {
                return _endOfStorage - _start;
            }
 
            void reserve(size_t n)
            {
                //坚持不缩容
                if (n > capacity())
                {
                    //开辟新的空间，然后赋值过去
                    T* tmp = new T[n];
                    size_t oldsize = size();
                    if (_start)
                    {
                        for (size_t i = 0; i < oldsize; ++i)
                        {
                            tmp[i] = _start[i];
                        }
                        delete[]_start;
                    }
               
                    _start = tmp;
                    _end = _start + oldsize;
                    _endOfStorage = _start + n;
                }
            }
 
            void resize(size_t n, const T& value = T())
            {
                //要扩容
                if (n > capacity())
                {
                    int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
                    reserve(newcapacity);
                }
    
                if (n > size())
                {
                    while (_end != _start + n)
                    {
                        push_back(value);
                    }
                }
                else
                {
                    _end = _start + n;
                }
            }
 
 
 
            ///access///
 
            T& operator[](size_t pos)
            {
                assert(pos < size());
                return _start[pos];
            }
 
            const T& operator[](size_t pos)const
            {
                assert(pos < size());
                return _start[pos];
            }
 
 
 
            ///modify/
 
            void push_back(const T& x)
            {
                if (size() == capacity())
                {
                    int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
                    reserve(newcapacity);
                }
                *_end = x;
                ++_end;
            }
 
            void pop_back()
            {
                assert(_end > _start);
                --_end;
            }
 
            void swap(vector<T>& v)
            {
                std::swap(_start, v._start);
                std::swap(_end, v._end);
                std::swap(_endOfStorage, v._endOfStorage);
            }
 
            iterator insert(iterator pos, const T& x)
            {
                assert(_start <= pos);
                assert(_end > pos);
                //判断增容
                int distance = pos - _start;
                if (_end == _endOfStorage)
                {
                    int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
                    reserve(newcapacity);
                    //这里的扩容不处理会导致迭代器失效
                    pos = _start + distance;
                }
                //挪动数据，插入
                auto end = _end -1;
                while (end >= pos)
                {
                    *(end+1) = *end;
                    --end;
                }
                *pos = x;
                ++_end;
                return pos;
            }
 
            iterator erase(iterator pos)
            {
                assert(pos >= _start);
                assert(pos < _end);
                //挪动数据
                iterator  ret = pos + 1;
                while (ret < _end)
                {
                    *(ret - 1) = *ret;
                    ++ret;
                }
                --_end;
                return pos;
            }
 
    private:
        iterator _start; // 指向数据块的开始
        iterator _end; // 指向有效数据的尾
        iterator _endOfStorage; // 指向存储容量的尾
    };

其中实现过程中最容易错误的就是insert以及erase扩容问题，这是最容易出错的。

扩容是防止浅拷贝，所有把利用赋值来实现深拷贝。insert以及erase要注意更新迭代器，防止迭代器失效。