Бывают случаи, когда вам нужен контейнер, содержащий только уникальные значения, упорядоченные по некоторым критериям. Эти функции есть у класса set стандартной библиотеки шаблонов. Если ваши требования позволяют контейнеру хранить повторяющиеся упорядоченные значения, то класс multiset - это контейнер, который вы хотите использовать. В этой статье я расскажу, как использовать эти два класса и как изменить способ упорядочивания данных в этих контейнерах. Сначала я расскажу о set class, а затем расскажу о различиях, когда вместо этого вы используете класс multiset.
Создание наборов
Установленный класс импортируется в вашу программу с помощью этого файла заголовка:
#include <set>
Класс является классом-шаблоном, поэтому при объявлении набора необходимо указать тип данных. Набор может быть любого типа данных, сопоставимого по критерию сортировки. Это означает, что у вас может быть набор определяемого пользователем типа, если для этого типа определена функция сортировки.
Объявление набора должно включать тип данных для элементов набора:
set<string> names; set<int> grades;
Вы также можете объявить критерий сортировки в объявлении как второй параметр шаблона. Я продемонстрирую, как это работает, позже в статье.
Вы можете объявить набор с начальными данными, предоставив список инициализаторов. Список не нужно сортировать, так как его добавление в набор автоматически отсортирует его. Например:
int main()
{
set<int> numbers = {3,1,2};
for (const int n : numbers) {
cout << n << " "; // displays 1 2 3
}
return 0;
}
Добавление данных в набор
Основным способом добавления данных в набор является функция insert. Эта функция помещает элемент в нужное место в наборе:
set<int> numbers; numbers.insert(3); numbers.insert(1); numbers.insert(2);
Функция возвращает как позицию, в которую был вставлен элемент, так и, для набора, информацию о том, была ли вставка успешной. Это возвращаемое значение представляет собой структуру pair, где поле first - это позиция вставки, а поле second - логическое значение, показывающее успех или неудачу вставки.
Вот пример того, как обрабатывать возвращаемое значение функции insert:
int main()
{
set<int> numbers;
pair<set<int>::iterator, bool> success;
success = numbers.insert(3);
if (success.second) {
cout << "3 was inserted at position "
<< *success.first << "." << endl;
}
success = numbers.insert(1);
if (success.second) {
cout << "1 was inserted at position "
<< *success.first << "." << endl;
}
success = numbers.insert(2);
if (success.second) {
cout << "2 was inserted at position "
<< *success.first << "." << endl;
}
return 0;
}
Результат этой программы:
3 was inserted at position 3. 1 was inserted at position 1. 2 was inserted at position 2.
Существуют и другие версии функции insert . Вы можете указать предлагаемую точку вставки для функции, чтобы ускорить вставку. Вот пример:
int main()
{
set<int> numbers = {8, 1, 2, 4, 5, 7, 3};
int value = 6;
auto iter = numbers.begin();
while (*iter < value) {
++iter;
}
numbers.insert(iter, value);
for (const int n : numbers) {
cout << n << " "; // 1 2 3 4 5 6 7 8
}
return 0;
}
Программа просматривает набор до тех пор, пока не достигнет последнего значения, меньшего, чем значение, которое нужно вставить. В этот момент происходит вставка.
Вы также можете вставить список элементов в набор, как показано в программе ниже:
int main()
{
set<int> numbers = {2,4,6};
numbers.insert({1,3,5});
for (const int n : numbers){
cout << n << " "; // 1 2 3 4 5 6
}
return 0;
}
Удаление элементов из набора
Элементы удаляются из набора с помощью функции erase. Первая версия этой функции удаляет определенное значение и возвращает количество удаленных элементов:
int main()
{
set<int> numbers = {1,3,2,5,4};
int removed = 3;
int count = numbers.erase(removed);
cout << count << " element was removed." << endl << endl;
for (const int n : numbers) {
cout << n << " "; // displays 1 2 4 5
}
return 0;
}
Вторая версия erase удаляет элемент через итератор, указывающий на позицию в наборе. Его возвращаемое значение - это позиция после удаленного элемента. В приведенном ниже примере я игнорирую возвращаемое значение:
int main()
{
set<int> numbers = {1,3,2,5,4};
int removed = 3;
auto iter = numbers.begin();
while (*iter != removed) {
iter++;
}
numbers.erase(iter);
for (const int n : numbers) {
cout << n << " "; // 1 2 4 5
}
return 0;
}
Поиск набора
В the set class есть несколько функций-членов для поиска. Основная функция поиска - find. Эта функция принимает значение в качестве параметра и ищет значение в наборе. Если значение найдено, функция возвращает итератор, указывающий на значение. Если значение не найдено, функция возвращает end() или позицию сразу за последним элементом набора.
Вот программа, демонстрирующая, как работает функция поиска:
#include <iostream>
#include <set>
#include <cstdlib>
#include <ctime>
using namespace std;
void buildSet(set<int> &st) {
srand(time(0));
for (int i = 1; i <= 25; i++) {
st.insert(rand() % 100 + 1);
}
}
void printSet(const set<int> &st) {
for (const int n : st) {
cout << n << " ";
}
}
int main()
{
set<int> numbers;
buildSet(numbers);
printSet(numbers);
cout << endl << endl;
int value;
cout << "Enter a value to find: ";
cin >> value;
auto found = numbers.find(value);
if (found != numbers.end()) {
cout << "Found " << value << "." << endl;
}
else {
cout << value << " was not found in the set. " << endl;
}
return 0;
}
Вот результат двух запусков программы:
14 21 24 27 35 38 42 44 52 57 58 60 68 71 80 84 86 89 92 96 Enter a value to find: 57 Found 57. 7 10 11 15 22 23 34 36 40 53 56 60 62 63 65 72 76 79 84 93 94 96 97 Enter a value to find: 77 77 was not found in the set.
Изменение порядка сортировки
Как я упоминал ранее, основным критерием сортировки наборов является less<>. Вы можете изменить это, указав другой критерий при объявлении нового набора. Если вы не знакомы с различными критериями сортировки, доступными в C ++, здесь - это справочное руководство для вас.
Чтобы продемонстрировать, как работает изменение критерия сортировки, я создам новый набор, который будет отсортирован с использованием критерия greater<int>. Вот программа:
#include <iostream>
#include <set>
#include <cstdlib>
#include <ctime>
using namespace std;
void buildSet(set<int, greater<int>> &st) {
srand(time(0));
for (int i = 1; i <= 25; i++) {
st.insert(rand() % 100 + 1);
}
}
void printSet(const set<int, greater<int>> st) {
for (const int n : st) {
cout << n << " ";
}
}
int main()
{
set<int, greater<int>> numbers;
buildSet(numbers);
printSet(numbers);
return 0;
}
Результат этой программы:
90 87 85 77 65 62 50 40 39 38 31 29 26 25 24 21 20 19 15 14 8 6 1
Обратите внимание, что мне пришлось указать второй параметр во всех параметрах функции. Шаблонные функции исправят это, и я расскажу об этом в следующей статье.
Использование класса мультимножества
Если вам нужны функции упорядочивания набора, но вы хотите разрешить дублирование в контейнере, вы должны использовать класс multiset. Функции, которые мы использовали для наборов, также работают и для мультимножеств.
Вы по-прежнему ссылаетесь на set class в своих директивах препроцессора для использования мультимножества. Программа ниже создает новый мультимножество и отображает значения в контейнере:
#include <iostream>
#include <set>
#include <cstdlib>
#include <ctime>
using namespace std;
void buildSet(multiset<int> &st) {
srand(time(0));
for (int i = 1; i <= 25; i++) {
st.insert(rand() % 100 + 1);
}
}
void printSet(const multiset<int> st) {
for (const int n : st) {
cout << n << " ";
}
}
int main()
{
multiset<int> numbers;
buildSet(numbers);
printSet(numbers);
return 0;
}
Вот результат одного запуска этой программы:
9 11 15 18 18 28 45 46 54 63 64 67 68 68 71 77 79 79 84 84 87 88 91 93 95
Обратите внимание на дубликаты 18, 68 и 84.
Все функции, которые я продемонстрировал ранее с наборами, работают с мультимножествами. Одной из функций, которую вы можете продуктивно использовать только с мультимножествами, является функция count, которая подсчитывает количество указанного значения в наборе. Я не демонстрировал это на set экземплярах, потому что известно, что в наборе хранится только одно значение.
Вот программа, которая подсчитывает количество значений, найденных в мультимножестве:
int main()
{
multiset<int> numbers;
buildSet(numbers);
printSet(numbers);
int value;
cout << endl << endl;
cout << "Enter a value to count: ";
cin >> value;
auto found = numbers.find(value);
if (found != numbers.end()) {
int numVals = numbers.count(value);
cout << "Found " << numVals << " " << value
<< "s in the set." << endl;
}
return 0;
}
Вот один из запусков программы:
5 20 21 21 22 22 25 29 30 33 33 50 57 66 70 70 73 77 81 82 82 89 89 93 94 Enter a value to count: 70 Found 2 70s in the set.
Когда использовать наборы и мультимножества
Основная причина использования набора или мультимножества - это необходимость хранить данные в отсортированном порядке. Базовая структура данных для наборов и мультимножеств представляет собой сбалансированное двоичное дерево, что означает, что поддержание порядка в данных очень эффективно. Однако использование двоичных деревьев также создает проблему, потому что вы не можете изменить значение элемента на месте, потому что это сделало бы упорядочение недействительным. Итак, внесение изменений включает удаление элемента из контейнера, а затем вставку нового элемента. Это более неэффективно, чем делать это в другом контейнере, поэтому вы захотите выбрать другой контейнер, если вам нужно внести много изменений в данные в вашем приложении.
Спасибо, что прочитали эту статью, и пишите мне с комментариями и предложениями.
