第 16.4 節

Vector and deque containers

0瀏覽次數0訪問次數--跳出率--平均停留

vector container

Basic concepts of vector

Features:

  • The vector data structure is very similar to an array, also referred to as a single-ended array.

Difference between vector and ordinary arrays:

  • The difference lies in that arrays occupy static memory while vectors can dynamically extend.

Dynamic Extension:

  • Rather than appending a new space after the original, it searches for a larger memory space, then copies the original data to the new space and frees the original space.

Description: 2015-11-10_151152

  • Vector container iterators support random access.

Vector Constructor

Description:

  • Create a vector container

Function prototype:

  • vector<T> v; // Implemented using template implementation class, default constructor
  • vector(v.begin(), v.end()); //Copies elements from the range [begin(), end()) to itself.
  • vector(n, elem); //The constructor copies n elements to itself.
  • vector(const vector &vec); //Copy constructor.

Example:

#include <vector>

void printVector(vector<int>& v) {

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

void test01()
{
    vector<int> v1; //无参构造
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    printVector(v1);

    vector<int> v2(v1.begin(), v1.end());
    printVector(v2);

    vector<int> v3(10, 100);
    printVector(v3);
    
    vector<int> v4(v3);
    printVector(v4);
}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary: The various construction methods of vectors are not comparable; use flexibly as needed.

vector assignment operation

Description:

  • 给vector容器赋值可以通过多种方式实现，以下是一些常见方法：

1. 使用初始化列表（最直观）

std::vector<int> vec;
vec = {1, 2, 3, 4, 5}; // C++11及以上

2. 使用assign()成员函数

std::vector<int> vec;
vec.assign(5, 10); // 5个元素，值均为10
vec.assign({1, 2, 3}); // 使用初始化列表

// 从另一个vector的迭代器范围赋值
std::vector<int> source = {4, 5, 6};
vec.assign(source.begin(), source.begin() + 2); // 取前两个元素

3. 使用拷贝赋值运算符

std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2;
vec2 = vec1; // vec2成为vec1的副本

4. 使用花括号初始化

std::vector<int> vec{10, 20, 30}; // 直接初始化

5. 填充赋值

std::vector<int> vec(5); // 先创建5个元素的vector
std::fill(vec.begin(), vec.end(), 42); // 全部填充为42

注意事项：

  • 赋值操作会替换vector中的原有内容
  • 使用assign()可以更灵活地控制新内容
  • 从其他容器赋值时，确保迭代器范围有效

根据具体需求选择合适的赋值方式即可。

Function prototype:

  • vector& operator=(const vector &vec);//overload the equality operator
  • assign(beg, end); // Copies the data in the range [beg, end) to itself.
  • assign(n, elem); // Copies n elements to itself.

Example:

#include <vector>

void printVector(vector<int>& v) {

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

//赋值操作
void test01()
{
    vector<int> v1; //无参构造
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    printVector(v1);

    vector<int>v2;
    v2 = v1;
    printVector(v2);

    vector<int>v3;
    v3.assign(v1.begin(), v1.end());
    printVector(v3);

    vector<int>v4;
    v4.assign(10, 100);
    printVector(v4);
}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary: Vector assignment is quite straightforward, using either operator= or the assign method.

Vector capacity and size

Description:

  • Operations on the capacity and size of vector containers

Function prototype:

  • empty(); //Determine whether the container is empty
  • capacity(); //Capacity of the container
  • size(); // Returns the number of elements in the container
  • resize(int num); //Reassign the container's length to num; if the container lengthens, fill the new positions with default values.

// If the container becomes shorter, elements at the end that exceed the container length are deleted.

  • resize(int num, elem); // Resize the container to length num, filling any new positions with the value of elem if the container expands.

//if the container becomes shorter, elements at the end that exceed the container length are deleted

Example:

#include <vector>

void printVector(vector<int>& v) {

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

void test01()
{
    vector<int> v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    printVector(v1);
    if (v1.empty())
    {
        cout << "v1为空" << endl;
    }
    else
    {
        cout << "v1不为空" << endl;
        cout << "v1的容量 = " << v1.capacity() << endl;
        cout << "v1的大小 = " << v1.size() << endl;
    }

    //resize 重新指定大小 ，若指定的更大，默认用0填充新位置，可以利用重载版本替换默认填充
    v1.resize(15,10);
    printVector(v1);

    //resize 重新指定大小 ，若指定的更小，超出部分元素被删除
    v1.resize(5);
    printVector(v1);
}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary:

  • Check if empty --- empty
  • return element count --- size
  • Return the container capacity
  • Resize

vector insertion and deletion

Description:

  • Performing insertion and deletion operations on a vector container
  • Insertion:
    • push_back(): Adds an element to the end of the vector.
    • insert(): Inserts elements at a specified position within the vector.
    • emplace(): Constructs an element directly in the vector at a given position.
  • Deletion:
    • pop_back(): Removes the last element from the vector.
    • erase(): Deletes elements at a specified position or within a range.
    • clear(): Removes all elements from the vector, leaving it empty.

Note: Insertions and deletions in the middle of a vector may cause shifts in elements, affecting performance. For frequent insertions/deletions, consider alternatives like std::list or std::deque. Always ensure iterators remain valid after modifications.

Function prototype:

  • push_back(ele); //insert element ele at the tail
  • pop_back(); //delete the last element
  • insert(const_iterator pos, ele); // Insert element ele at position pos using the iterator
  • insert(const_iterator pos, int count,ele);//Inserts count elements at the iterator position pos with value ele
  • erase(const_iterator pos); // Delete the element pointed to by the iterator
  • erase(const_iterator start, const_iterator end);//Delete elements between start and end iterators
  • clear(); //Remove all elements from the container

Example:


#include <vector>

void printVector(vector<int>& v) {

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

//插入和删除
void test01()
{
    vector<int> v1;
    //尾插
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);
    printVector(v1);
    //尾删
    v1.pop_back();
    printVector(v1);
    //插入
    v1.insert(v1.begin(), 100);
    printVector(v1);

    v1.insert(v1.begin(), 2, 1000);
    printVector(v1);

    //删除
    v1.erase(v1.begin());
    printVector(v1);

    //清空
    v1.erase(v1.begin(), v1.end());
    v1.clear();
    printVector(v1);
}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary:

  • Tail insertion --- push_back
  • Pop back --- pop_back
  • Insert --- insert (position iterator)
  • Erase --- erase (position iterator)
  • clear

vector data access

Description:

  • Access and modification operations on data in a vector

Function prototype:

  • at(int idx); // Returns the data pointed to by index idx
  • operator[]; // Returns the data pointed to by index idx
  • front(); // Return the first data element in the container
  • back(); //returns the last data element in the container

Example:

#include <vector>

void test01()
{
    vector<int>v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }

    for (int i = 0; i < v1.size(); i++)
    {
        cout << v1[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < v1.size(); i++)
    {
        cout << v1.at(i) << " ";
    }
    cout << endl;

    cout << "v1的第一个元素为： " << v1.front() << endl;
    cout << "v1的最后一个元素为： " << v1.back() << endl;
}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

    test01();


    // 返回 0 表示程序正常结束。
    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary:

  • Apart from using iterators to access elements in a vector container, and at can also be used.
  • The front returns the first element of the container.
  • back returns the last element of the container.

Swap vectors

Description:

  • Implement swapping elements between two containers.

Function prototype:

  • swap(vec); // Swap elements of vec with itself

Example:

#include <vector>

void printVector(vector<int>& v) {

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

void test01()
{
    vector<int>v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    printVector(v1);

    vector<int>v2;
    for (int i = 10; i > 0; i--)
    {
        v2.push_back(i);
    }
    printVector(v2);

    //互换容器
    cout << "互换后" << endl;
    v1.swap(v2);
    printVector(v1);
    printVector(v2);
}

void test02()
{
    vector<int> v;
    for (int i = 0; i < 100000; i++) {
        v.push_back(i);
    }

    cout << "v的容量为：" << v.capacity() << endl;
    cout << "v的大小为：" << v.size() << endl;

    v.resize(3);

    cout << "v的容量为：" << v.capacity() << endl;
    cout << "v的大小为：" << v.size() << endl;

    //收缩内存
    vector<int>(v).swap(v); //匿名对象

    cout << "v的容量为：" << v.capacity() << endl;
    cout << "v的大小为：" << v.size() << endl;
}

int main() {

    test01();

    test02();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary: The swap function can exchange two containers, effectively allowing you to practically reclaim memory.

vector reserved space

Description:

  • 减少vector在动态扩展容量时的扩展次数。

Function prototype:

  • //The container reserves len elements without initialization, making the reserved positions inaccessible.
    ​

Example:

#include <vector>

void test01()
{
    vector<int> v;

    //预留空间
    v.reserve(100000);

    int num = 0;
    int* p = NULL;
    for (int i = 0; i < 100000; i++) {
        v.push_back(i);
        if (p != &v[0]) {
            p = &v[0];
            num++;
        }
    }

    cout << "num:" << num << endl;
}

int main() {

    test01();
    

    return 0;
}

Running/Observing the results: After running, the example will print variable values or addresses; address values depend on the runtime environment, so focus on observing the relative positioning and pointer changes of similar objects.

Summary: If the data volume is large, you can start by using reserve to pre-allocate space.

deque container

deque container basic concept

Features:

  • Double-ended array, which can perform insertion and deletion operations on the head end.

deque与vector的区别：

deque (double-ended queue) 和 vector 都是C++标准模板库（STL）中的序列容器，但它们在内部结构和性能特性上有显著不同：

  1. 内存布局：
    • Vector：维护一块连续的内存空间来存储所有元素。这使得它支持高效的随机访问（通过下标）。
    • Deque：通常被实现为一系列分段连续的内存块（称为中控器/映射器）。每个块存储一部分元素，这些块本身可以不连续。这使得它支持在头部和尾部都进行高效的插入和删除。
  2. 性能特点：
    • Vector：
      • 尾部操作：在尾部添加或删除元素是平摊常数时间 O(1)。
      • 头部或中间操作：在头部或中间插入/删除元素是线性时间 O(n)，因为需要移动后续的所有元素。
      • 随机访问：operator[] 和 at() 是常数时间 O(1)。
    • Deque：
      • 头部和尾部操作：在头部或尾部添加或删除元素都是常数时间 O(1)。
      • 中间操作：在中间插入/删除元素是线性时间 O(n)，且通常比 vector 更慢，因为它涉及移动两个方向的元素。
      • 随机访问：operator[] 和 at() 是常数时间 O(1)，但比 vector 稍慢，因为需要额外的指针解引用。
  3. 内存分配与开销：
    • Vector：通常更节省内存，因为只有一块连续的内存和少量管理开销。但重新分配内存时（当容量不足时），成本很高，需要分配新空间并移动所有元素。
    • Deque：通常有更高的内存开销（需要管理多个块和一个映射结构），但重新分配内存的成本较低，只需为新块分配内存，而无需移动所有现有元素。
  4. 迭代器：
    • Vector：迭代器是随机访问迭代器，因为内存是连续的。
    • Deque：迭代器也是随机访问迭代器，但比 vector 迭代器更复杂。

使用场景总结：

  • 当你主要需要高效的随机访问，并且元素主要从尾部添加或删除时，使用 vector。
  • 当你需要在头部和尾部都进行高效的插入和删除操作（例如实现队列、滑动窗口），且对内存连续性要求不高时，使用 deque。
  • Vectors have low efficiency for insertions and deletions at the beginning, and this inefficiency increases with larger data volumes.
  • Compared to vector, deque offers faster insertion and deletion operations at the head.
  • Accessing elements in a vector is faster than in a deque, which is related to their internal implementations.

Note: 2015-11-19_204101

deque内部工作原理：

deque（双端队列）是一种支持在两端进行高效插入和删除操作的线性数据结构。与 vector 不同，deque 不仅在末尾，而且在头部也能以摊销常数时间复杂度（amortized constant time）进行插入和删除。

核心思想

deque 通常通过一个由固定大小数组（或块）组成的序列来实现，并通过一个中央控制结构（通常是一个指针数组或类似的索引结构）来管理这些块。这种设计允许在两端动态增长，而无需像 vector 那样在每次容量改变时重新分配和复制整个内存块。

关键组件

  1. 块（Blocks）：deque 将内存划分为多个固定大小的块。每个块内部是一个数组，用于存储实际的元素。
  2. 地图（Map）：一个中央控制数组（指针数组），其中每个条目指向一个数据块。地图本身可以根据需要增长。
  3. 头部指针和尾部指针：记录了第一个和最后一个有效块在地图中的索引，以及当前块内元素的起始和结束位置。

操作原理

push_front 和 push_back

  • push_back：如果最后一个块未满，则直接在该块末尾添加元素。如果已满，则在地图中分配一个新的块，并更新尾部指针。
  • push_front：类似地，检查第一个块的头部是否有空间。如果没有，则在地图的前端分配一个新块（可能需要重新分配和复制地图），并更新头部指针。

索引访问 (operator[] 或 at)

  1. 根据给定索引计算出它位于哪个块（通过地图索引）以及块内的偏移量。
  2. 通过地图指针跳转到对应的块，然后返回该块内偏移位置的元素。

优势

  • 两端操作高效：在头部和尾部插入/删除元素的平均时间复杂度为 O(1)。
  • 缓存友好：块内元素在内存中是连续的，有利于缓存局部性。
  • 容量增长灵活：无需像 vector 那样为容纳新元素而重新分配和复制所有现有数据。

与 vector 的对比

特性dequevector
头部插入/删除O(1)O(n)
尾部插入/删除O(1) 摊销O(1) 摊销
随机访问O(1)O(1)
内存连续性各块内连续，块间不一定连续完全连续
实时性保证插入操作可能导致地图重分配仅在尾部增长时可能重分配

简化示意图

地图 (指针数组):
[ ptr_to_block_0 | ptr_to_block_1 | ptr_to_block_2 | ... ]

块 0 (内存连续):  [元素0, 元素1, 元素2]
块 1 (内存连续):  [元素3, 元素4, 元素5]
块 2 (内存连续):  [元素6, 元素7, 元素8]

通过计算索引：索引 5 -> 位于块 1，块内偏移 2

这种结构是 std::deque 在 C++ STL 等标准库中的常见实现方式。

Inside deque, there is a central controller that manages the content in each segment of the buffer, where the actual data is stored.

The central controller maintains the addresses of each buffer, making it feel like a contiguous memory space when using deque.

clip_image002-1547547896341

  • The iterator of a deque container also supports random access.

deque constructor

Description:

  • deque container construction

Function prototype:

  • deque<T> deqT; //default constructor form
  • deque(beg, end); //The constructor copies the elements in the range [beg, end) to itself.
  • deque(n, elem); //The constructor copies n elements to itself.
  • deque(const deque &deq); //copy constructor

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";

    }
    cout << endl;
}
//deque构造
void test01() {

    deque<int> d1; //无参构造函数
    for (int i = 0; i < 10; i++)
    {
        d1.push_back(i);
    }
    printDeque(d1);
    deque<int> d2(d1.begin(),d1.end());
    printDeque(d2);

    deque<int>d3(10,100);
    printDeque(d3);

    deque<int>d4 = d3;
    printDeque(d4);
}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary: The construction methods for the deque container and the vector container are almost identical; use them flexibly.

Assignment Operations in deque

Description:

  • Assign values to a deque container

Function prototype:

  • deque& operator=(const deque &deq); //overloading the equality operator
  • assign(beg, end); // Copies the data in the range [beg, end) to itself.
  • assign(n, elem); // Copies n elements to itself.

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";

    }
    cout << endl;
}
//赋值操作
void test01()
{
    deque<int> d1;
    for (int i = 0; i < 10; i++)
    {
        d1.push_back(i);
    }
    printDeque(d1);

    deque<int>d2;
    d2 = d1;
    printDeque(d2);

    deque<int>d3;
    d3.assign(d1.begin(), d1.end());
    printDeque(d3);

    deque<int>d4;
    d4.assign(10, 100);
    printDeque(d4);

}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary: The deque assignment operation is the same as that of the vector, and must be mastered.

deque size operations

Description:

  • Manipulating the size of a deque container.

Function prototype:

  • deque.empty(); //Determine whether the container is empty
  • deque.size(); // Returns the number of elements in the container
  • deque.resize(num); //Reset the length of the container to num. If the container becomes longer, fill the new positions with default values.

// If the container becomes shorter, elements at the end that exceed the container length are deleted.

  • deque.resize(num, elem); //Reassign the container's length to num. If the container grows, fill the new positions with the value of elem.

// If the container becomes shorter, elements at the end that exceed the container length are deleted.

​

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";

    }
    cout << endl;
}

//大小操作
void test01()
{
    deque<int> d1;
    for (int i = 0; i < 10; i++)
    {
        d1.push_back(i);
    }
    printDeque(d1);

    //判断容器是否为空
    if (d1.empty()) {
        cout << "d1为空!" << endl;
    }
    else {
        cout << "d1不为空!" << endl;
        //统计大小
        cout << "d1的大小为：" << d1.size() << endl;
    }

    //重新指定大小
    d1.resize(15, 1);
    printDeque(d1);

    d1.resize(5);
    printDeque(d1);
}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary:

  • Deque doesn't have the concept of capacity.
  • Check if empty --- empty
  • return element count --- size
  • Reset the count --- resize

Deque allows insertion and deletion at both ends.

Description:

  • Insert and delete data in deque container

Function prototype:

Insert operation at both ends:

  • push_back(elem); //Add data to the end of the container
  • push_front(elem); // Insert data at the head of the container
  • pop_back(); //Delete the last data of the container
  • pop_front(); //Delete the first data from the container

Specified location operation:

  • insert(pos,elem); // Inserts a copy of the elem at the pos position, returning the position of the new data.
  • insert(pos,n,elem); //Inserts n elements of elem data at position pos, returns nothing.
  • Inserts data within the range [beg, end) at the specified position pos, with no return value.
  • clear(); // Clear all data from the container
  • erase(beg,end); //Delete data in the range [beg,end), return the position of the next data.
  • erase(pos); // Deletes the data at position, returning the location of the next data.
    ​
    ​

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";

    }
    cout << endl;
}
//两端操作
void test01()
{
    deque<int> d;
    //尾插
    d.push_back(10);
    d.push_back(20);
    //头插
    d.push_front(100);
    d.push_front(200);

    printDeque(d);

    //尾删
    d.pop_back();
    //头删
    d.pop_front();
    printDeque(d);
}

//插入
void test02()
{
    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_front(100);
    d.push_front(200);
    printDeque(d);

    d.insert(d.begin(), 1000);
    printDeque(d);

    d.insert(d.begin(), 2,10000);
    printDeque(d);

    deque<int>d2;
    d2.push_back(1);
    d2.push_back(2);
    d2.push_back(3);

    d.insert(d.begin(), d2.begin(), d2.end());
    printDeque(d);

}

//删除
void test03()
{
    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_front(100);
    d.push_front(200);
    printDeque(d);

    d.erase(d.begin());
    printDeque(d);

    d.erase(d.begin(), d.end());
    d.clear();
    printDeque(d);
}

int main() {

    //test01();

    //test02();

    test03();
    

    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary:

  • Insert and delete the provided position with iterators!
  • Tail insertion --- push_back
  • Pop back --- pop_back
  • push_front --- 头插
  • delete from front --- pop_front

deque data access

Description:

  • Operations for accessing and storing data in a deque.

Function prototype:

  • at(int idx); // Returns the data pointed to by index idx
  • operator[]; // Returns the data pointed to by index idx
  • front(); // Return the first data element in the container
  • back(); //returns the last data element in the container

Example:

#include <deque>

void printDeque(const deque<int>& d) 
{
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";

    }
    cout << endl;
}

//数据存取
void test01()
{

    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_front(100);
    d.push_front(200);

    for (int i = 0; i < d.size(); i++) {
        cout << d[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < d.size(); i++) {
        cout << d.at(i) << " ";
    }
    cout << endl;

    cout << "front:" << d.front() << endl;

    cout << "back:" << d.back() << endl;

}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary:

  • Besides using iterators to access elements in a deque container, the operator and the at() method can also be used.
  • The front returns the first element of the container.
  • back returns the last element of the container.

Sorting a deque

Description:

  • Implement sorting for a deque container using algorithms.

Algorithm:

  • sort(iterator beg, iterator end) // sorts elements within the interval from beg to end

Example:

#include <deque>
#include <algorithm>

void printDeque(const deque<int>& d) 
{
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";

    }
    cout << endl;
}

void test01()
{

    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_front(100);
    d.push_front(200);

    printDeque(d);
    sort(d.begin(), d.end());
    printDeque(d);

}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

    test01();


    // 返回 0 表示程序正常结束。
    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary: The sort algorithm is very practical; when using it, just include the algorithm header file.

Case - Judge Scoring

Case Description

There are five contestants: A, B, C, D, and E. Ten judges score each contestant, excluding the highest score and the lowest score among the judges, and then calculate the average score.

Implementation Steps

  1. Create five contestants and put them into the vector.
  2. Iterate through the vector container, retrieve each contestant, and execute a for loop to store the 10 ratings into a deque container.
  3. Sort the fractions in the deque container and remove the highest and lowest scores.
  4. Iterate through the deque container once to accumulate the total score.
  5. get the average score

Example code:

//选手类
class Person
{
public:
    Person(string name, int score)
    {
        this->m_Name = name;
        this->m_Score = score;
    }

    string m_Name; //姓名
    int m_Score;  //平均分
};

void createPerson(vector<Person>&v)
{
    string nameSeed = "ABCDE";
    for (int i = 0; i < 5; i++)
    {
        string name = "选手";
        name += nameSeed[i];

        int score = 0;

        Person p(name, score);

        //将创建的person对象 放入到容器中
        v.push_back(p);
    }
}

//打分
void setScore(vector<Person>&v)
{
    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
    {
        //将评委的分数 放入到deque容器中
        deque<int>d;
        for (int i = 0; i < 10; i++)
        {
            int score = rand() % 41 + 60;  // 60 ~ 100
            d.push_back(score);
        }

        //cout << "选手： " << it->m_Name << " 打分： " << endl;
        //for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
        //{
        //  cout << *dit << " ";
        //}
        //cout << endl;

        //排序
        sort(d.begin(), d.end());

        //去除最高和最低分
        d.pop_back();
        d.pop_front();

        //取平均分
        int sum = 0;
        for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
        {
            sum += *dit; //累加每个评委的分数
        }

        int avg = sum / d.size();

        //将平均分 赋值给选手身上
        it->m_Score = avg;
    }

}

void showScore(vector<Person>&v)
{
    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << "姓名： " << it->m_Name << " 平均分： " << it->m_Score << endl;
    }
}

int main() {

    //随机数种子
    srand((unsigned int)time(NULL));

    //1、创建5名选手
    vector<Person>v;  //存放选手容器
    createPerson(v);

    //测试
    //for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
    //{
    //  cout << "姓名： " << (*it).m_Name << " 分数： " << (*it).m_Score << endl;
    //}

    //2、给5名选手打分
    setScore(v);

    //3、显示最后得分
    showScore(v);


    return 0;
}

Run/Observation Results: The execution results may include random numbers or time-related content, which could vary with each run. Focus on observing the generation and processing flow.

Summary: Choosing different containers to operate on data can improve code efficiency.

音乐页