Статья Автор: Лебедев Дмитрий

Конспект 7. Контейнер vector


C++_Контейнер vector.Часть 1

В C++ существует специальный контейнер для хранения последовательности переменных одного типа данных. Такой контейнер называется vector.

Удобно представить себе vector как набор из nn «коробочек», каждая может хранить переменную указанного типа данных. Все «коробочки» пронумерованы от 0 до n−1.

Рассмотрим работу с вектором на примере задачи.

Задача

Дана последовательность из n чисел. Выведите её в обратном порядке.

Решение

#include <iostream>
#include <vector> // Библиотека для работы с векторами
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> v(n); // создаём вектор из n чисел
    for (int i = 0; i < n; ++i){
        cin >> v[i]; // считываем i-й элемент вектора
    }
    for (int i = n - 1; i >= 0; --i){ // цикл от n - 1 до 0
        cout << v[i] << " "; // выводим i-й элемент вектора
    }
    return 0;
}
 

Данную задачу можно решить иначе. Переставим элементы в векторе v так, чтобы они шли в обратном порядке.

Решение 2

Поменяем v0 с vn−1, v1 с vn−2 и так далее до середины вектора.

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }
    for (int i = 0; i < n / 2; ++i){
        int temp = v[i];
        v[i] = v[n - 1 - i];
        v[n - 1 - i] = temp;
    }
    for (int i = 0; i < n; ++i){
        cout << v[i] << " ";
    }
    return 0;
}
 

У вектора есть специальный метод push_back. Данный метод позволяет добавить элемент в конец вектора. Также у вектора существует специальный метод size(), с помощью которого можно узнать размер вектора. Рассмотрим применение данных методов на примере задачи.

Задача

Дана последовательность из n чисел. Разделите её на две последовательности: в первой храните все неотрицательные числа из исходной последовательности, а во второй — все отрицательные. Выведите полученные последовательности на экран, каждую на отдельной строке.

Решение

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> pos, neg; // создаём два пустых вектора pos и neg
    for (int i = 0; i < n; ++i)
    {
        int now;
        cin >> now; // считываем элементы исходной последовательности
        if (now >= 0){
            pos.push_back(now); // неотрицательное число добавляем в конец вектора pos
        } else {
            neg.push_back(now); // отрицательное число добавляем в конец вектора neg
        }
    }
    for (int i = 0; i < pos.size(); ++i) { // идём циклом по всем элементам вектора pos
        cout << pos[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < neg.size(); ++i) { // идём циклом по всем элементам вектора neg
        cout << neg[i] << " ";
    }
    return 0;
}

C++_Контейнер vector.Часть 2

Задача

Дана последовательность из n элементов. Поменяйте местами минимальный и максимальный элементы последовательности.

Решение

Найдём индексы минимального и максимального элемента (imnи imx) и поменяем местами элементы последовательности с данными индексами.

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }
    int imn = 0, imx = 0;
    for (int i = 0; i < n; ++i){
        if (v[i] < v[imn]){
            imn = i;
        }
        if (v[i] > v[imx]){
            imx = i;
        }
    }
    swap(v[imn], v[imx]); // меняем местами элементы с индексами imn и imx
    for (int i = 0; i < n; ++i){
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}
 

Заметим, что если бы мы меняли переменные v[imx] и v[imn] с помощью арифметических операций (без использования третьей переменной), то программа работала бы некорректно при imn=imx. В этом случае происходит обмен переменной с самой собой, и легко заметить, что такой подход будет работать неправильно. Поэтому для обмена переменных нужно использовать функцию swap или алгоритм с дополнительной переменной.

C++_Контейнер vector.Часть 3

Задача

В школе ученики получают оценки от 1 до 5. Вам дан список всех оценок одного ученика. Посчитайте, сколько оценок каждого вида он получил.

Решение

Заведём вектор, в котором для каждой оценки будем хранить, сколько раз она встречалась в списке. Для упрощения кода вектор будет иметь 6 элементов, из которых будут использоваться только последние 5 элементов, так как оценки 0 не существует. Заметим, что такой способ хранения нельзя использовать, когда интервал оценок находится достаточно далеко от 0, так как в этом случае будет зарезервировано слишком много неиспользуемой памяти.

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> grades(6); // создаём вектор из 6 чисел, заполненный нулями
    for (int i = 0; i < n; ++i){
        int now;
        cin >> now;
        ++grades[now];
    }
    for (int i = 1; i <= 5; ++i){
        cout << i << " " << grades[i] << endl;
    }
    return 0;
}

C++_Контейнер vector.Часть 4

Задача

Дана последовательность из n чисел. Необходимо удалить повторяющиеся элементы в последовательности: для каждого значения оставить только первое его вхождение.

Например, для последовательности из 5 элементов: 1, 2, 1, 2, 1 — небходимо оставить только два элемента: 1, 2.

Решение

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }
    for (int i = 0; i < n; ++i){
        bool flag = false;
        for (int j = 0; j < i; ++j){
            if (v[i] == v[j]){
                flag = true;
            }
        }
        if (!flag){
            cout << v[i] << " ";
        }
    }
    return 0;
}

C++_Контейнер vector.Часть 5

Задача

Дан список из nn целых чисел, число k и значение x. Необходимо вставить в список на позицию с индексом k элемент, равный x, сдвинув все элементы, имевшие индекс не менее k, вправо.

Решение

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }
    int k, x;
    cin >> k >> x;
    v.push_back(0);
    ++n;
    for (int i = n - 1; i > k; --i){
        v[i] = v[i - 1];
    }
    v[k] = x;
    for (int i = 0; i < n; ++i){
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

C++_Контейнер vector.Часть 6

Задача

На математической олимпиаде было три задачи. По каждой из задач участник получает от 0 до 10 баллов. Победителем считается участник, набравший наибольшее количество баллов в сумме по трём задачам. Вам дан протокол проверки олимпиады (n строк по три числа в каждой). Выведите баллы по каждой из задач, которые набрал победитель. Гарантируется, что победитель определяется однозначно.

Решение

В этой задаче, помимо максимальной суммы баллов у участника, необходимо поддерживать вектор его оценок.

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n, maxsum = -1;
    vector<int> now(3), best(3);
    cin >> n;
    for (int i = 0; i < n; ++i){
        int nowsum = 0;
        for (int j = 0; j < 3; ++j){
            cin >> now[j];
            nowsum += now[j];
        }
        if (nowsum > maxsum){
            maxsum = nowsum;
            best = now;
        }
    }
    for (int i = 0; i < 3; ++i){
        cout << best[i] << " ";
    }
    return 0;
}
 

На примере данной задачи видно, что векторы можно присваивать друг другу. При присваивании одного вектора другому осуществляется поэлементное копирование. Поэтому чем больше элементов в векторе, значения которого мы копируем, тем дольше будет работать присваивание. При присваивании векторов друг другу не обязательно, чтобы они имели одинаковый размер; операция будет работать корректно в любом случае.

Задачи для тренировки

1) Чётные индексы

  
2) Чётные элементы  
3) Статистика  
4) Наименьший положительный  
5) Домашнее задание  
6) Цифры  
7) Уникальные элементы  
8) Удаление элемента  
9) Циклический сдвиг  
10) Максимальное произведение  

Печать