содержание
вводить
Контейнер набора наборов реализует структуру данных сбалансированного бинарного дерева поиска красно-черного дерева, автоматически корректирует расположение бинарного дерева и расставляет элементы в нужное положение. Значение элементов, содержащихся в контейнере набора, уникально, и элементы в наборе расположены в определенном порядке. На самом деле, большинство операций над набором аналогичны операциям над вектором, но набор не поддерживает произвольный доступ и должен использовать итераторы для доступа. Поскольку набор, помещающий элемент, регулирует положение элемента и помещает его в правильное положение, в наборе есть только одна операция вставки.
Общие функции
set Список функций-членов выглядит следующим образом:
1. begin() -- возвращает итератор, указывающий на первый элемент
2. clear() -- очистить все элементы
3. count() -- возвращает количество элементов значения.
4. empty() -- Если коллекция пуста, вернуть true
5. end() -- возвращает итератор, указывающий на последний элемент
6. equal_range() -- возвращает два итератора верхней и нижней границ, равных заданному значению в коллекции
7. erase() -- удаляет элемент в коллекции
8. find() -- возвращает итератор, указывающий на найденный элемент
9. get_allocator() -- возвращает распределитель коллекции
10. insert() — вставка элемента в коллекцию.
11. lower_bound() — возвращает итератор, указывающий на первый элемент, больший (или равный) значению
12. key_comp() -- возвращает функцию сравнения значений между элементами
13. max_size() -- возвращает максимальное количество элементов, которые может содержать коллекция.
14. rbegin() — возвращает обратный итератор, указывающий на последний элемент в коллекции.
15. rend() -- возвращает обратный итератор, указывающий на первый элемент в коллекции.
16. size() -- количество элементов в коллекции
17. swap() -- поменять местами две заданные переменные
18. upper_bound() — возвращает итератор элементов больше определенного значения
19. value_comp() -- возвращает функцию для сравнения значений между элементами.
Экземпляр функции
инициализация и обход
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main() {
int arr[5] = { 0,1,2,3,4 };
set<int> mySet(arr, arr + 5);
for (auto it = mySet.begin(); it != mySet.end(); it++)
{
cout << " " << *it;
}
cout << "\n";
set<int> mySet1 = { 0,1,2,3,4,5 };
for (auto it = mySet1.begin(); it != mySet1.end(); it++)
{
cout << " " << *it;
}
cout << "\n";
set<int> mySet2;
mySet2.insert(11);
mySet2.insert(12);
mySet2.insert(13);
mySet2.insert(14);
mySet2.insert(15);
mySet2.insert(16);
mySet2.insert(17);
mySet2.insert(18);
for (auto it = mySet2.begin(); it != mySet2.end(); it++)
{
cout << " " << *it;
}
cout << "\n";
return 0;
}
найти и удалить
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main() {
set<int> st;
for (int i = 0; i < 10; i++)
st.insert(i);
// удаляем элемент, значение которого равно elem в контейнере
st.erase(4);
// удалить элемент в любом месте
set<int>::iterator it = st.begin();
st.erase(it);
// удаляем элементы между [first, last]
st.erase(st.begin(), ++st.begin());
// обход дисплея
for (it = st.begin(); it != st.end(); it++)
cout << *it << " ";
cout << endl;
// очистить все элементы
st.clear();
// Определяем, пусто ли множество
if (st.empty())
cout
return 0;
}// list::sort
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main() {
set<int> mySet2;
mySet2.insert(11);
mySet2.insert(12);
mySet2.insert(13);
mySet2.insert(18);
mySet2.insert(14);
mySet2.insert(15);
mySet2.insert(16);
mySet2.insert(17);
for (auto it = mySet2.begin(); it != mySet2.end();)
{
if (*it == 15)
{
it = mySet2.erase(it);
}
else
{
it++;
}
}
cout << "\n";
for (auto it = mySet2.begin(); it != mySet2.end();it++)
{
cout << " " << *it;
}
cout << "\n";
return 0;
}
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main() {
set<int> mySet2;
mySet2.insert(11);
mySet2.insert(12);
mySet2.insert(13);
mySet2.insert(18);
mySet2.insert(14);
mySet2.insert(15);
mySet2.insert(16);
mySet2.insert(17);
mySet2.insert(15);
mySet2.insert(16);
mySet2.insert(17);
set<int>::iterator iter;
iter = mySet2.find(17);
if (iter == mySet2.end())
{
cout
}
else
{
cout
mySet2.erase(*iter);
}
return 0;
}
Найдите количество элементов
// list::sort
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main() {
set<int> mySet2;
mySet2.insert(11);
mySet2.insert(12);
mySet2.insert(13);
mySet2.insert(18);
mySet2.insert(14);
mySet2.insert(15);
mySet2.insert(16);
mySet2.insert(17);
mySet2.insert(15);
mySet2.insert(16);
mySet2.insert(17);
int cc = mySet2.count(13);
cout
return 0;
}
вставить элемент
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main() {
set<int> mySet;
// вставляем элемент в контейнер
mySet.insert(4);
// вставляем элемент в любую позицию
set<int>::iterator it = mySet.begin();
mySet.insert(it, 2);
// обход дисплея
for (it = mySet.begin(); it != mySet.end(); it++)
cout
cout << endl;
return 0;
}
изменить элемент
Итератор it набора имеет модификатор const, поэтому модификация его элементов неизбежно завершится ошибкой. Но иногда я сталкиваюсь с проблемой модификации элемента stl set.Общее решение этой проблемы - сначала стереть элемент, а потом вставить его, что очень неэффективно, поэтому приходится искать более эффективный метод. Компиляция всегда не проходит с начала. Если он отображается на объект, на который указывает ссылка, с помощью const_cast(*it), его можно изменить. Более общий подход заключается в следующем:
#include <set>
#include <string>
#include <iostream>
using namespace std;
class CEmployee {
public:
CEmployee();
~CEmployee();
const string getName() const;
void setName(const string name);
const string getTitle() const;
void setTitle(string title);
int getID() const;
void setID(int id);
private:
int m_id;
string m_username;
string m_title;
};
CEmployee::CEmployee()
{
}
CEmployee::~CEmployee()
{
}
const string CEmployee::getName() const
{
return m_username;
}
void CEmployee::setName(const string username)
{
m_username = username;
}
const string CEmployee::getTitle() const
{
return m_title;
}
void CEmployee::setTitle(string title)
{
m_title = title;
}
int CEmployee::getID() const
{
return m_id;
}
void CEmployee::setID(int id)
{
m_id = id;
}
class sortByID
{
public:
bool operator() (CEmployee const &_A, CEmployee const &_B) const
{
if (_A.getID() < _B.getID()) return true;
if (_A.getID() == _B.getID()) return _A.getName().compare(_B.getName()) < 0;
return false;
}
};
int main()
{
set
set<CEmployee, sortByID> ::iterator iter;
CEmployee employeeInfo;
employeeInfo.setName("employee_one");
employeeInfo.setTitle("employee");
employeeInfo.setID(1);
empIDSet.insert(employeeInfo);
CEmployee employeeInfo2;
employeeInfo2.setName("employee_two");
employeeInfo2.setTitle("CFO");
employeeInfo2.setID(5);
empIDSet.insert(employeeInfo2);
CEmployee employeeInfo3;
employeeInfo3.setName("employee_three");
employeeInfo3.setTitle("manager");
employeeInfo3.setID(3);
empIDSet.insert(employeeInfo3);
// Шаг 1: Найдите элемент для изменения
iter = empIDSet.find(employeeInfo2);
if (iter != empIDSet.end())
{
// Шаг 2: Скопируйте этот элемент
CEmployee e(*iter);
// Шаг 3: удалить этот элемент;
empIDSet.erase(iter++);
// Увеличиваем итератор, чтобы он оставался действительным (см. правило 9)
// Шаг 4: Измените эту копию
e.setTitle("Corporate Deity");
// Шаг 5: Вставьте новое значение, запросите его местоположение
empIDSet.insert(iter, e);
// то же, что и исходный элемент
// не работает
//static_cast<CEmployee>(*iter).setTitle("Corporate Deity");
}
else
{
cout << " Failed/n" << endl;
}
for (iter = empIDSet.begin(); iter != empIDSet.end(); iter++)
{
cout << iter->getID() << " " << iter->getName() << " " << iter->getTitle() << endl;
}
return 0;
}
// Набор наборов типа int, сначала удаляя, а затем вставляя.
#include <set>
#include <iostream>
using namespace std;
int main()
{
set<int> mySet = { 1,2,3,4,5,6,7,8,85,94,24 };
for (auto it = mySet.begin(); it != mySet.end(); it++)
{
cout << " " << *it;
}
cout << "\n";
set<int>::iterator itr;
itr = mySet.find(8);
itr = mySet.erase(itr);
mySet.insert(itr, 10);
for (auto it = mySet.begin(); it != mySet.end(); it++)
{
cout << " " << *it;
}
return 0;
}
Несколько вопросов по набору
(1) Почему эффективность вставки и удаления map и set выше, чем у других контейнеров последовательности?
Большинство людей говорят, что это легко, потому что с ассоциативными контейнерами нет необходимости делать копии памяти и перемещать память. Это верно, это так. Все элементы в контейнере набора хранятся в виде узлов, а структура узла аналогична структуре связанного списка, указывая на родительские узлы и дочерние узлы. Структурная схема может быть следующей:
А
/ \
ДО НАШЕЙ ЭРЫ
/ \ / \
D E F G
Поэтому при вставке требуется лишь небольшое преобразование, и указатель узла указывает на новый узел. Удаление аналогично: после небольшого преобразования можно указать указатель на удаляемый узел на другие узлы. Все операции здесь — перестановка указателей, и к перемещению памяти это не имеет никакого отношения.
(2) Почему ранее сохраненный итератор не дает сбой после каждой вставки?
Итератор здесь равнозначен указателю на узел, память не изменилась, как может быть недействительным указатель на память (разумеется, сам удаленный элемент был недействителен). По сравнению с вектором каждый раз, когда вы удаляете и вставляете, указатель может стать недействительным, и то же самое верно для вызова push_back для вставки в конце. Потому что для обеспечения непрерывного хранения внутренних данных память, на которую указывает итератор, могла быть перезаписана другой памятью или память была освобождена в процессе удаления и вставки. Даже в момент push_back внутреннего пространства контейнера может не хватить, и нужна новая память большего размера.Только освободив предыдущую память, подав заявку на новую большую память, скопировав существующие элементы данных в новую память, и, наконец, размещение требуемой памяти. Вставленный элемент помещается в конец, тогда предыдущий указатель памяти, естественно, недоступен. Особенно при использовании с такими алгоритмами, как find, помните об этом принципе: не используйте итераторы с истекшим сроком действия.
(3) Как меняется скорость вставки и поиска множества при увеличении количества элементов данных?
Если вы знаете взаимосвязь log2, вы должны полностью понять этот ответ. Поиск в множестве использует бинарный поиск, то есть если элементов 16, то для нахождения результата требуется максимум 4 сравнения, а элементов 32 и требуется максимум 5 сравнений. Так что насчет 10000? Максимальное количество сравнений log10000, максимальное 14, а если 20000 элементов? Не более 15 раз. Как видите, когда количество данных удваивается, количество поисков увеличивается только на 1, а время поиска увеличивается только на 1/14. После того, как вы поймете эту истину, вы сможете со спокойной душой вкладывать в нее элементы.