顺序容器之vector

1、内存结构

内存结构
这就是vector的内存结构模型,这里最需要注意的是end()是指向最后一个元素的下一个位置,不是刚好指向最后一个元素

在想要得到vector数组中的首元素和末元素的时候请使用front()和back()。如果使用begin()和end()则会报错。因为begin()和end()返回类型是迭代器。

使用vector的时候要包含头文件#include <vector> ,要使用命名空间std。

2、vector常用API

注:以下中的E均代表基本类型或者类,c、c1、c2代表vector生成的对象。pos代表位置,即一般情况下使用begin()和end()。n代表个数,elem也代表类型,initlist代表初始化列表。

下面的API都比较简单,自行测试即可

初始化相关API

OperationEffect
vector<E> cDefault constructor; creates an empty vector without anyelements
vector<E> c(c2)Copy constructor; creates a new vector as a copy of c2 (allelements are copied)
vector<E> c = c2Copy constructor; creates a new vector as a copy of c2 (allelements are copied)
vector<E> c(rv)Move constructor; creates a new vector, taking the contents of the rvalue rv (since C++11)
vector<E> c = rvMove constructor; creates a new vector, taking the contents of the rvalue rv (since C++11)
vector<E> c(n)Creates a vector with n elements created by the defaultconstructor
vector<E> c(n,elem)Creates a vector initialized with n copies of element elem
vector<E> c(beg,end)Creates a vector initialized with the elements of the range [beg,end)
vector<E> c(initlist)Creates a vector initialized with the elements of initializer list initlist (since C++11)
vector<E> c = initlistCreates a vector initialized with the elements of initializer list initlist (since C++11)
c.~vector()Destroys all elements and frees the memory

大小及比较相关API:

OperationEffect
c.empty()Returns whether the container is empty (equivalent to size()==0 but might be faster)
c.size()Returns the current number of elements
c.max_size()Returns the maximum number of elements possible
c.capacity()Returns the maximum possible number of elements without reallocation
c.reserve(num)Enlarges capacity, if not enough yet
c.shrink_to_fit()Request to reduce capacity to fit number of elements (since C++11)
c1 == c2Returns whether c1 is equal to c2 (calls == for the elements)
c1 != c2Returns whether c1 is not equal to c2 (equivalent to !(c1==c2))
c1 < c2Returns whether c1 is less than c2
c1 > c2Returns whether c1 is greater than c2 (equivalent to c2<c1)
c1 <= c2Returns whether c1 is less than or equal to c2 (equivalent to !(c2<c1))
c1 >= c2Returns whether c1 is greater than or equal to c2 (equivalent to !(c1<c2))

注意:类对象使用这些==,> , < , <= , >=符号的时候要自己进行重载

赋值相关API:

OperationEffect
c = c2Assigns all elements of c2 to c
c = rvMove assigns all elements of the rvalue rv to c (since C++11)
c = initlistAssigns all elements of the initializer list initlist to c (since C++11)
c.assign(n,elem)Assigns n copies of element elem
c.assign(beg,end)Assigns the elements of the range [beg,end)
c.assign(initlist)Assigns all the elements of the initializer list initlist
c1.swap(c2)Swaps the data of c1 and c2
swap(c1,c2)Swaps the data of c1 and c2

存取值相关API:

OperationEffect
c[idx]Returns the element with index idx (no range checking)
c.at(idx)Returns the element with index idx (throws range-error exception if idx is out of range)
c.front()Returns the first element (no check whether a first element exists)
c.back()Returns the last element (no check whether a last element exists)

迭代器相关API:

OperationEffect
c.begin()Returns a random-access iterator for the first element
c.end()Returns a random-access iterator for the position after the last element
c.cbegin()Returns a constant random-access iterator for the first element (since C++11)
c.cend()Returns a constant random-access iterator for the position after the last element (since C++11)
c.rbegin()Returns a reverse iterator for the first element of a reverse iteration
c.rend()Returns a reverse iterator for the position after the last element of a reverse iteration
c.crbegin()Returns a constant reverse iterator for the first element of a reverse iteration (since C++11)
c.crend()Returns a constant reverse iterator for the position after the last element of a reverse iteration (since C++11)

这里的rend()、rbegin()是反向的意思,此时的rbegin()指向最后一个元素,rend()指向最开始元素之前的一个元素。
cend()和cbegin()是const的意思,不可以改变。

还要注意:这样写

vector<int>::iterator itr = vi.rbegin();
for(;itr != vi.rend(); ++itr)
{
    cout << *itr << endl;
}

这样写是通不过的,r换成c也通不过,用auto可以解决。而且上面的那种写法已经落后了,下面的才是时髦的。

for(auto itr = vi.rbegin();itr != vi.rend(); ++itr)
{
    cout << *itr << endl;
}

插入删除相关API:

OperationEffect
c.push_back(elem)Appends a copy of elem at the end
c.pop_back()Removes the last element (does not return it)
c.insert(pos,elem)Inserts a copy of elem before iterator position pos and returns the position of the new element
c.insert(pos,n,elem)Inserts n copies of elem before iterator position pos and returns the position of the first new element (or pos if there is no new element)
c.insert(pos,beg,end)Inserts a copy of all elements of the range [beg,end) before iterator position pos and returns the position of the first new element (or pos if there is no new element)
c.insert(pos,initlist)Inserts a copy of all elements of the initializer list initlist before iterator position pos and returns the position of the first new element (or pos if there is no new element; since C++11)
c.emplace(pos,args...)Inserts a copy of an element initialized with args before iterator position pos and returns the position of the new element (since C++11)
c.emplace_back(args...)Appends a copy of an element initialized with args at the end (returns nothing; since C++11)
c.erase(positr)Removes the element at iterator position pos and returns the position of the next element
c.erase(begitr,enditr)Removes all elements of the range [beg,end) and returns the position of the next element
c.resize(num)Changes the number of elements to num (if size() grows new elements are created by their default constructor)
c.resize(num,elem)Changes the number of elements to num (if size() grows new elements are copies of elem)
c.clear()Removes all elements (empties the container)

3、vector高级主题

关于vector的size和capasize、resize、reserve的区别

size是指容器当前拥有元素的个数,而capacity是指容器在必须分配新的存储空间之前可以存放的元素总数vector<int> vi(10),vi.capacity()=vi.size()=0,当你向vi中插入元素时,只要没有超过十个,那么capacity就不变,而size为你插入的元素的个数。当你插入第十个时,capacity=size=10,当再插入一个,即第十一个数据时,容器重新分配存储空间:vi.capacity()=20,而vi.size()=11,即容器重新分配空间的话是现有空间的2倍进行分配,以保证vector的效率。

resize 可以改变 size 的大小,变大等价于调用 push_back(),变小等于 pop_back() ,resize 不可以改变 capacity 的大小。reserve 只可变大 vector 的 capacity 而不可以使其减小。

我们在写程序之前最好实现预估内存容量,先reserve好,防止后面内存不够申请空间浪费时间。resize 会调用构造器,而 reserve 则不会调用构造器。事先 reserve 出空间来,可以大量的减少不必要的内存拷贝。

圧入对象与对象指针

当向容器中压的是类对象成员时,最好要保证无参构造器的存在,类似于数组中的类对象一样。在必要的情况下,要自实现拷贝构造和拷贝赋值。压入栈中的对象元素在堆中,所申请的内存己托管,无需再次打理。

容器有内存托管的功能,但仅限于,被压入的实体元素。若元素为指针类型,则指针被托管。而不是指针所指向的空间被托管。需要手动delete。

高效的插入与删除

尾部的插入和删除是高效的O(1),其它位置则是低效的。故对于 vector 而言,提倡使用 push_back()和 pop_back(),仅量少用 insert() 和 erase()。使用 insert() 和 erase()在头部插入和删除会进行大量的拷贝,非常低效。

无效的迭代器

比如我想删除vector容器中的偶数,使用下面的代码,看似没有什么毛病,实则是不可行的。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> vi;
    int data[10] = {1,8,3,2,5,7,9,4,6,10};
    vi.assign(data,data+10);
    vector<int>::iterator itr = vi.begin();
    for(;itr != vi.end(); ++itr)
    {
        if(*itr%2==0)
            vi.erase(itr);
        else
        {
            cout<<*itr<<endl;
        }
    } 
    return 0;
}

失效原因

vector 是一个顺序容器, 在内存中是一块连续的内存, 当删除一个元素后, 内存中的数据会发生移动, 以保证数据的紧凑。 所以删除一个数据后, 其他数据的地址发生了变化, 之前获取的迭代器根据原有的信息就访问不到正确的数据。插入一个元素, 会导致迭代器失效吗? 比如在奇数元素的位置插入 100?当然也会,insert()会返回新插入的那个位置
上面代码的解决方案

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> vi;
    int data[10] = {1,8,3,2,5,7,9,4,6,10};
    vi.assign(data,data+10);
    vector<int>::iterator itr = vi.begin();
    for(;itr != vi.end();)
    {
        if(*itr%2==0)
            itr = vi.erase(itr);
        else
        {
            cout<<*itr<<endl;
            ++itr;
        }
    } 
    return 0;
}

4、二维及多维空间

通过vector生成二维及多维空间,用 vector 中嵌套 vector, 注意嵌套的语法格式。

这是规规矩矩的二维空间,每个维度的长度一样。

vector <int> t(5);
vector <vector <int>> tt(5,t);

下面这种就是可以实现每个维度不一样:

int main()
{
    srand(time(NULL));
    vector <int> t;
    vector <vector <int>> tt(5,t);
    for(i=0;i<5;i++)
    {
        for(j=0;j<rand()%20;j++)
        {
            tt[i] = push_back(j);
        }
    }

    //打印数组内容
    for(int i=0; i<5; i++)
    {
        for(int j =0;j<tt[i].size();j++)
        {
            cout << tt[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

5、编程注意

在vector中删除元素其实最好不要使用erase()。用下面的方法才是老司机所为

删除vector中的元素为5的元素:

vector<int> vi = {8,4,6,5,2,6,3};
vi.erase(remove(vi.begin(),vi.end(),5),vi.end());

这里的remove是移除元素,全局函数,非成员函数,实际上空间大小不会改变,后面的会覆盖移除的元素。返回的位置是移除元素的那个位置。

remove_if详解

#include <algorithm>
forward_iterator remove_if( forward_iterator start, forward_iterator end, Predicate p ); 

函数remove_if()移除序列[start, end)中所有应用于谓词p返回true的元素. 此函数返回一个指向被修剪的序列的最后一个元素迭代器. 记住, remove_if()并不会实际移除序列[start, end)中的元素; 如果在一个容器上应用remove_if(), 容器的长度并不会改变(remove_if()不可能仅通过迭代器改变容器的属性), 所有的元素都还在容器里面. 实际做法是, remove_if()将所有应该移除的元素都移动到了容器尾部并返回一个分界的迭代器. 移除的所有元素仍然可以通过返回的迭代器访问到. 为了实际移除元素, 你必须对容器自行调用erase()以擦除需要移除的元素. 这也是erase-remove idiom名称的由来:

container.erase(remove_if(container.begin(), container.end(), pred), container.end()); 
vector<int> vt;
int arr[9] = {1,2,3,4,5,6,7,8,9};
vt.assign(arr,arr+9);
vector<int>::iterator pos;
pos = remove_if(vt.begin(),vt.end()),compose2(logical_and<bool>(),bind2nd(greater<int>(),4),bind2nd(less<int>(),7))); //删除比4大且比7小的数
vt.erase(pos,vt.end()); //全部移动到末尾了
//结果1,2,3,4,7,8,9

remove_if()类似于partition(), 但有两点不同: 1) 它们使用的谓词条件刚好相反. 2) remove_if只强调前面部分(第二部分不再需要了)
remove_if()以线性时间(linear time)运行.
remove_if()不能用于关联容器如set<>或map<>.

Last modification:September 3rd, 2019 at 04:30 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment