[C++]vector的介绍及使用

目录

C++：vector的使用

                1.vector的定义方式

                2.vector的空间增长

                        size和capacity

                        reserve和resize

                        empty

                3.vector的迭代器使用

                       begin和end

                       rbegin和rend

                4.vector的增删查改

                        push_back和pop_back

                        insert、erase和find

                        swap

                        元素访问

                5.vector的迭代器失效问题

                        迭代器失效的两种方式

                        迭代器失效问题举例

                        迭代器失效解决办法

vector相关习题讲解：

                1.只出现一次的数字I

                2.杨辉三角

                3.删除排序数组中的重复项

                4.只出现一次的数字II

                5.只出现一次的数字III

                6.数组中出现次数超过一半的数字

                7.电话号码字母组合

C++：vector的使用

vector的介绍：

1.vector是表示可变大小数组的序列容器.

2.就像数组一样，vector也采用的连续存储空间来存储元素，也就意味着可以采用下标对vector的元素进行访问，和数组一样高效，但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理.

3.本质讲，vector使用动态分配数组来存储它的元素，当新元素插入时，这个数组需要重新分配大小，为了增加存储空间，其做法是，分配一个新的数组，然后将全部元素移到这个数组，就时间而言，这是一个相对代价高的任务，因此每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小.

4.vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因此存储空间比实际需要的存储空间要大，不同的库采用不同的策略权衡空间的使用和重新分配，以保证在末尾插入一个元素的时候是在常数的时间复杂度完成的.

5.由于vector采用连续的空间来存储元素，与其他动态序列容器相比，vector在访问元素的时候更加高效，在其末尾添加和删除元素相对高效，而对于不在其末尾进行的删除和插入操作效率则相对较低.

vector的使用：

1.vector的定义方式

vector的定义：

void TestVector1()
{
    vector<int> v1;                                
    vector<int> v2(4, 100);                       
    vector<int> v3(v2.begin(), v2.end());  
    vector<int> v4(v3);    
    int myints[] = { 16,2,77,29 };
    vector<int> v5(myints, myints + sizeof(myints) / sizeof(int));
    cout << "The contents of fifth are:";
    vector<int>::iterator it = v5.begin();
    while (it != v5.end())
    {
        cout << *it << ' ';
        ++it;
    }
    cout << endl;
}

2.vector的空间增长

size和capacity

void TestVector3()
{
	vector<int> v;
	size_t sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << endl;
		}
	}
	cout << "size = " << v.size() << endl;
}

reserve和resize

void TestVector4()
{
	vector<int> v;
	for (int i = 1; i < 10; i++)
	{
		v.push_back(i);
	}
	v.resize(5);
	v.resize(8, 100);
	v.resize(12);

	cout << "v contains:";
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << ' ';
	}
	cout << endl;
}

void TestVector5()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100);   
	cout << "making v grow: ";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << endl;
		}
	}
}

empty

3.vector的迭代器使用

begin和end

void PrintVector(const vector<int>& v)
{
	vector<int>::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
void TestVector2()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	it = v.begin();
	while (it != v.end())
	{
		*it *= 2;
		++it;
	}

	vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	PrintVector(v);
}

rbegin和rend

void PrintVector(const vector<int>& v)
{
	vector<int>::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
void TestVector2()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	it = v.begin();
	while (it != v.end())
	{
		*it *= 2;
		++it;
	}

	vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	PrintVector(v);
}

4.vector的增删查改

push_back和pop_back

void TestVector6()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	v.pop_back();
	v.pop_back();

	it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

insert和erase和find

void TestVector7()
{
	vector<int> v{ 1, 2, 3, 4 };
	vector<int>:: iterator pos = find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
		v.insert(pos, 30);
	}

	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	pos = find(v.begin(), v.end(), 3);
	v.erase(pos);

	it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

swap

int main()
{
	vector<int> v1;
	vector<int> v2;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	swap(v1, v2);
	return 0;
}

元素访问

void TestVector8()
{
	vector<int> v{ 1, 2, 3, 4 };
	// 通过[]读写第0个位置。
	v[0] = 10;
	cout << v[0] << endl;
	// 1. 使用for+[]下标方式遍历
	for (size_t i = 0; i < v.size(); ++i)
	{
		cout << v[i] << " ";
	}
	cout << endl;
	// 2. 使用迭代器遍历
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	// 3. 使用范围for遍历
	for (auto x : v)
	{
		cout << x << " ";
	}
	cout << endl;
}

assign：

void TestVector9()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.assign(10, 1);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v.assign(v1.begin(), v1.end());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	string str("hello world");
	v.assign(str.begin(), str.end());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.assign(++str.begin(), --str.end());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

shrink_to_fit：

5.vector的迭代器失效问题

迭代器的主要作用就是让我们在使用各个容器时，不用关心其底层的数据结构，而vector的迭代器在底层实际上就是一个指针。迭代器失效就是指迭代器底层对应指针所指向的空间被销毁了，而指向的是一块已经被释放的空间，如果继续使用已经失效的迭代器，程序可能会崩溃。

迭代器失效的两种方式：

1.会引起其底层空间改变的操作，都有可能使迭代器失效，比如：resize、reserve、insert、assign、push_back等.

2.指定位置元素的删除操作 — erase

erase删除pos位置元素后，pos位置之后的元素往前移动，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是_finish的位置，而_finish位置位置是没有元素的，那么pos位置就失效了，因此删除vector中任意位置上元素时，VS就认为该位置迭代器失效了.

迭代器失效问题举例

实例一：

实例二：

迭代器失效解决办法

方法：切记！每次使用前，对迭代器进行重新赋值

实例一解决办法：

实例二解决办法：

vector相关习题讲解：

1.只出现一次的数字I

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;
        for(auto e : nums)
        {
            ret ^= e;
        }
        return ret;
    }
};

2.杨辉三角

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;
		}
		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] + vv[i - 1][j - 1];
				}
			}
		}
		return vv;
	}
};

3.删除排序数组中的重复项

//方法一:使用erase删除重复数据，不过会导致数据挪动，时间复杂度为O(N*N)
class Solution {
public:
  int removeDuplicates(vector<int>& nums) 
  {
    if(nums.size() == 1)
      return 1;
    vector<int>::iterator it = nums.begin();
    vector<int>::iterator it1 = it;
    it1++;

    while(it != nums.end())
    {
      while(it1!=nums.end() && *it1==*it)
        it1++;
      it = nums.erase(++it, it1);
      it1 = it;
      it1++;
    }
    return nums.size();
  }
};

//方二:时间复杂度为O(N)
int removeDuplicates(int* nums, int numsSize)
{
  int src1 = 0, src2 = 1;
  int dst = 0;
  // 跟上题的思路一致，相同的数只保留一个，依次往前放
  while(src2 < numsSize)
  {
    nums[dst] = nums[src1];
    ++dst;
		//如果两个指针指向的元素不重复，则指针同时向后移动
    if(nums[src1] != nums[src2])
    {
      ++src1;
      ++src2;
    }
    else
    {
      //如果重复，找到第一个不重复的元素
      while(src2 < numsSize && nums[src1] == nums[src2])
      {
        ++src2;
      }
      //更新指针
      src1 = src2;
      ++src2;
    }
  }
  if(src1 < numsSize)
  {
      nums[dst] = nums[src1];
      ++dst;
  }
  return dst;
}

4.只出现一次的数字II

5.只出现一次的数字III

class Solution
{
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<int> res;
        int i = 0;
        for (; i < nums.size() - 1; )
        {
            if (nums[i] == nums[i + 1])
            {
                i += 2;
            }
            else
            {
                res.push_back(nums[i]);
                i += 1;
            }
        }
        if (i < nums.size())
        {
            res.push_back(nums[i]);
        }
        return res;
    }
};

6.数组中出现次数超过一半的数字

class Solution
{
public:
    int MoreThanHalfNum_Solution(vector<int> numbers)
    {
        if (numbers.empty())
        {
            return 0;
        }
        sort(numbers.begin(), numbers.end()); // 排序，取数组中间那个数
        int middle = numbers[numbers.size() / 2];
        int count = 0; // 出现次数
        for (int i = 0; i < numbers.size(); ++i)
        {
            if (numbers[i] == middle)
            {
                ++count;
            }
        }
        //返回符合条件的数
        return (count > numbers.size() / 2) ? middle : 0;
    }
};

7.电话号码字母组合

文章来源地址https://www.toymoban.com/news/detail-719185.html

class Solution
{
    string _numStr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    void Combine(const string& digits, int i, vector<string>& vCombine,string combinStr)
    {
	    if (i == digits.size())
	    {
		    vCombine.push_back(combinStr);
		    return;
	    }
	    int num = digits[i] - '0';
	    string str = _numStr[num];
	    for(auto ch:str)
	    {
		   Combine(digits, i + 1, vCombine, combinStr + ch);
	    }
    }
    vector<string> letterCombinations(string digits)
    {
	    vector<string> vCombine;
	    if (digits.empty())
	    {
		    return vCombine;
	    }
	    size_t i = 0;
	    string str;
	    Combine(digits, i, vCombine, str);
	    return vCombine;
    }
};

到了这里，关于[C++]vector的介绍及使用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！