C++之vector

简介

std::vector - cppreference.com

头文件 #include <vector>。

std::vector是动态数组，采用顺序存储结构，与静态数组不同，vector可以自动扩展内存空间。

向vector插入数据元素时，若vector已分配内存（vector的容量）已经用完了，就会新分配一块更大的堆空间，将原空间数据复制过去，插入新元素，释放原内存空间。

vector是 STL（Standard Template Library，标准模板库）提供的容器之一。

遍历vector动态数组

普通for循环

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values({0, 1, 2, 3, 4});
    /** 下标实现 **/
    std::cout << "--- 下标实现 ---\n";
    for(int i=0; i<values.size(); i++)
    {
        std::cout << values[i] << ' ';
    }
    std::cout << std::endl;
    /** 迭代器实现 **/
    std::cout << "--- 迭代器实现 ---\n";
    for(std::vector<int>::iterator it=values.begin(); it!=values.end(); it++)
    {
        std::cout << *it << ' ';
    }
    std::cout << std::endl;
    // auto 自动类型推导，简化复杂的迭代器定义
    for(auto it=values.begin(); it!=values.end(); it++)
    {
        std::cout << *it << ' ';
    }
    std::cout << std::endl;
    return 0;
}

for-each循环

C++中的范围循环（Range-based for loop），也称为for-each循环，是C++11引入的一种简化数组或容器遍历的循环方式。

显示声明数据类型：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values({1, 2, 3, 4, 5});

    for(int v : values)
    {
        std::cout<< v << ' ';
    }
    std::cout << '\n';

    for(int& v : values)
    {
        std::cout<< v << ' ';
    }
    std::cout << '\n';

    // const可以禁止修改元素，引用可以避免拷贝（避免内存复制）
    for(const int& v : values)
    {
        std::cout<< v << ' ';
    }
    std::cout << '\n';
    return 0;
}

auto自动推导数据类型：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values({1, 2, 3, 4, 5});

    for(auto v : values)
    {
        std::cout << v << ' ';
    }
    std::cout << '\n';
    // 引用类型，可修改vector元素
    for(auto& v : values)
    {
        v = 7;  // 修改vector元素
        std::cout << v << ' ';
    }
    std::cout << '\n';

    for(const auto& v : values)
    // for(auto const& v : values) // 同上
    {
        std::cout << v << ' ';
    }
    std::cout << '\n';
    return 0;
}

查找

find

std::find 用于查找元素，头文件#include <algorithm>。 若元素存在，则返回最先出现（第一个相等元素）的位置（迭代器），反之，返回容器最后一个元素的下一个位置（等于end()函数返回的迭代器）。

#include <iostream>
#include <vector>
#include <algorithm>


int main()
{
    std::vector<int> values({1, 2, 3, 2});
    int a = 2;

    auto it = std::find(values.begin(), values.end(), a);
    int index = it - values.begin();  // 计算元素下标
    std::cout << *it << " 的下标为：" << index << std::endl;

    // 元素不存在
    a = 66;
    auto it2 = std::find(values.begin(), values.end(), a);
    if(it2 == values.end())
    {
        std::cout << "不存在元素 " << a << std::endl;
    }
    return 0;
}

find_if

std::find_if 用于查找满足指定条件的元素，头文件#include <algorithm>。 若满足指定条件的元素存在，则返回最先出现（第一个满足条件元素）的迭代器，反之，返回容器最后一个元素的下一个位置（等于end()函数返回的迭代器）。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class Person
{
private:
    std::string m_name;
    unsigned int m_age;
    char m_sex;
public:
    Person(std::string name, unsigned int age, char sex)
    :m_name(name), m_age(age), m_sex(sex) {}

    std::string getName() { return m_name; }
    unsigned int getAge() { return m_age; }
};

int main()
{
    std::vector<Person> values({
        {"夏尔·凡多姆海威", 12, 'm'},
        {"利姆鲁·特恩佩斯特", 37, 'n'},
        {"火灵儿", 16, 'w'},
        {"Charlotte", 16, 'w'}
    });
    auto it = std::find_if(values.begin(), values.end(), [](Person a){
        if(a.getName() == "利姆鲁·特恩佩斯特") return true;
        return false;
    });
    std::cout << (*it).getName() << std::endl;

    auto it2 = std::find_if(values.begin(), values.end(), [](Person a){
        return a.getAge() == 16;
    });
    std::cout << (*it2).getName() << std::endl;

    // 元素不存在
    auto it3 = std::find_if(values.begin(), values.end(), [](Person a){
        return a.getAge() == 200;
    });
    if(it3 == values.end())
    {
        std::cout << "元素不存在" << std::endl;
    }
    return 0;
}

排序

std::sort常用于对stl容器进行排序，#include <algorithm>。

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> values = {5, 4, 1, 2, 7};
    std::sort(values.begin(), values.end());  // 默认：从小到大，升序排序
    // std::sort(values.begin(), values.end(), std::greater());  // 从大到小，降序排序
    for(const auto& v : values){
        std::cout << v << ' ';
    }
    std::cout << '\n';
    return 0;
}

对于复杂的自定义数据结构，可以自定义排序规则，示例：

#include <iostream>
#include <vector>
#include <algorithm>

class Person
{
private:
    static unsigned int count;
    unsigned int m_id;
    std::string m_name;
    unsigned int m_age;

public:
    Person(const std::string& name, const unsigned int& age)
     : m_name(name), m_age(age)
    {
        m_id = ++count;
    }
    unsigned int getId() const { return m_id; }
    std::string getName() const { return m_name; }
    unsigned int getAge() const { return m_age; }
};
unsigned int Person::count = 0;

// 根据id降序排序
bool greaterId(Person& a, Person& b)
{
    return a.getId() > b.getId();
}

// 多条件排序
bool less(const Person& a, const Person& b)
{
    if(a.getAge() < b.getAge())  // 年龄小的在前
        return true;
    else if(a.getAge() == b.getAge())  // 年龄相等，id小的在前
        return a.getId() < b.getId();
    else if(a.getAge() > b.getAge())  // 年龄大的在后
        return false;
}
int main()
{
    std::vector<Person> values({
        {"诸葛亮", 70},
        {"曹操", 80},
        {"华佗", 74},
        {"刘备", 74}
    });
    // std::sort(values.begin(), values.end(), greaterId);
    std::sort(values.begin(), values.end(), less);
    for(const auto& v : values){
        std::cout << v.getId() << " - " << v.getName() << std::endl;
    }
    return 0;
}

push_back 与 emplace_back

push_back：将一个已经构造好的对象（或值的副本）添加到向量(即vector)的末尾。

emplace_back：直接在向量的末尾构造一个对象，避免额外的拷贝或移动操作。

vector push_back源码：

_GLIBCXX20_CONSTEXPR
void
push_back(value_type&& __x)
{ emplace_back(std::move(__x)); }

vector emplace_back源码：

vector<_Tp, _Alloc>::
emplace_back(_Args&&... __args)
{
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
    {
        _GLIBCXX_ASAN_ANNOTATE_GROW(1);
        _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
                        std::forward<_Args>(__args)...);
        ++this->_M_impl._M_finish;
        _GLIBCXX_ASAN_ANNOTATE_GREW(1);
    }
    else
        _M_realloc_insert(end(), std::forward<_Args>(__args)...);
#if __cplusplus > 201402L
    return back();
#endif
}

reserve() 与 resize()

说明

reserve() 和 resize() 都用于调整vector动态数组的大小，只不过在功能上存在区别。

size() 是大小（表示已存储的元素数量），capacity() 是容量（表示最多可以存储多少个元素）。

• reserve(n) 只调整，不初始化。
  • 若n大于容量，reserve后，大小不变（不初始化），容量增加为n；
  • n小于等于容量，则不做调整（无变化）。
• resize(n) 调整，并初始化。
  • resize后，vector的大小size()即为n，若n等于size，则不做操作。
  • 若n大于size（size增加了），会对增加的部分进行初始化，若同时n大于容量，则容量和大小都增加为n；
  • 若n小于size，则删除尾部多余元素。

源码

reserve 函数声明见头文件 stl_vector.h，函数实现见文件 vector.tcc。

vector reserve源码：

template<typename _Tp, typename _Alloc>
_GLIBCXX20_CONSTEXPR
void
vector<_Tp, _Alloc>::
reserve(size_type __n)
{
    if (__n > this->max_size())
__throw_length_error(__N("vector::reserve"));
    if (this->capacity() < __n)  // __n 大于容量
    {
        const size_type __old_size = size();
        pointer __tmp;
#if __cplusplus >= 201103L
    if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
    {
        __tmp = this->_M_allocate(__n);
        _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
            __tmp, _M_get_Tp_allocator());
    }
    else
#endif
        {
            __tmp = _M_allocate_and_copy(__n,
        _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
        _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
            std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
                _M_get_Tp_allocator());
        }
        _GLIBCXX_ASAN_ANNOTATE_REINIT;
        _M_deallocate(this->_M_impl._M_start,
            this->_M_impl._M_end_of_storage
            - this->_M_impl._M_start);
        this->_M_impl._M_start = __tmp;
        this->_M_impl._M_finish = __tmp + __old_size;
        this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
    }

    // __n 小于等于容量，不做调整，啥都不干
}

resize 函数声明见头文件 stl_vector.h，函数实现也位于此文件。

vector resize源码，resize函数有两个重载：

_GLIBCXX20_CONSTEXPR
void
resize(size_type __new_size)
{
if (__new_size > size()) // 大于size
    _M_default_append(__new_size - size());
else if (__new_size < size())  // 小于size
    _M_erase_at_end(this->_M_impl._M_start + __new_size);
// 等于size，啥都不干
}

// 指定初始化值 __x
_GLIBCXX20_CONSTEXPR
void
resize(size_type __new_size, const value_type& __x)
{
if (__new_size > size())
    _M_fill_insert(end(), __new_size - size(), __x);
else if (__new_size < size())
    _M_erase_at_end(this->_M_impl._M_start + __new_size);
}

示例

#include <iostream>
#include <vector>

int main()
{
    std::cout << ">>>values" << std::endl;
    std::vector<int> values;
    values.reserve(6);
    std::cout << "values.size(): " << values.size() << std::endl;  // values.size(): 0
    std::cout << "values.capacity(): " << values.capacity() << std::endl;  // values3.capacity(): 6

    std::cout << ">>>values2" << std::endl;
    std::vector<int> values2;
    values2.resize(6);
    std::cout << "values2.size(): " << values2.size() << std::endl;  // values2.size(): 6
    std::cout << "values2.capacity(): " << values2.capacity() << std::endl;  // values3.capacity(): 6

    std::cout << ">>>values3" << std::endl;
    std::vector<int> values3;
    values3.reserve(10);
    std::cout << "values3.size(): " << values3.size() << std::endl;  // values3.size(): 0
    std::cout << "values3.capacity(): " << values3.capacity() << std::endl;  // values3.capacity(): 10
    values3.resize(6);
    std::cout << "values3.size(): " << values3.size() << std::endl;  // values3.size(): 6
    std::cout << "values3.capacity(): " << values3.capacity() << std::endl;  // values3.capacity(): 10
    return 0;
}

vector扩容机制

当容量不足时，std::vector会分配一个更大的内存块，并将原内存的元素复制到新的内存中，插入新元素，释放原内存。为了减少频繁的扩容操作，std::vector通常会将容量扩大为原来的 1.5倍 或 两倍，具体实现可能会有所不同，例如VS以1.5倍扩容（其实是 VS 使用的 MSVC 以1.5倍扩容；VS即Visual Studio 包括VS2015、VS2022等IDE），GCC的g++以2倍扩容。

• MSVC（Microsoft Visual C++ 编译器），核心编译工具是 cl.exe（C/C++ 编译器） 和 link.exe（链接器）。

• GCC（GNU Compiler Collection）。

  • MinGW 和 MinGW-w64，Windows系统，包括 gcc.exe、g++.exe 等工具。
  • gcc，Linux系统，C语言编译器。
  • g++，Linux系统，C++编译器。