Редактирование std::set на примере переписывания и отсечения значений

Опубликовано 10.09.2022 | Автор: admin

Иногда могут возникать новичковатые вопросы вроде "как перемешать set или map", как поменять ключи местами, как отсортировать множество или карту и подобные им. Появление этих вопросов обусловлено непониманием внутреннего устройства ассоциативных контейнеров и что упорядоченный массив — это массив, которому предначертано быть упорядоченным непосредственно при создании, что определяется упорядочивание только один раз.

//Листинг #1		clang		Ошибка в представлении себе ассоциативных контейнеров

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    for (int i=0; i<10; i++){
       s.insert(i);    
    }
    
    for (const auto &i: s){
       cout << i << ' ';    
    }
    
    s.find(5) = 10; 	//Нельзя проделать  нечто подобное
}

//Листинг #1 clang Ошибка в представлении себе ассоциативных контейнеров

#include <iostream>

#include <set>

using namespace std;

int main()

{

set<int> s;

for (int i=0; i<10; i++){

s.insert(i);

}

for (const auto &i: s){

cout << i << ' ';

}

s.find(5) = 10; //Нельзя проделать нечто подобное

}

В листинге #1 приводится пример попытки переназначения. Проблема только в том, что переназначение будет означать, что одно только это действие потребует сортировки всего массива (множества) s. Т. е. каждое переназначение будет означать сортировку набора значений. А проведение сортировки будет означать, что заданная для создания сортировка не будет иметь смысла, ну, и ещё каждое присваивание требовало бы неоправдано много времени (это же не просто присваивание, а перестроение всего набора).

Ассоциативным массивам предначертано быть упорядочеными только в том порядке, в каком их просят быть упорядоченными в момент создания.

Любое вмешательство в ассоциативный массив, требующее престроения массива, — это создание нового массива.

Если вы используете ассоциативный массив, а у вас часто возникает потребность влиять на него изменением значения, переупорядочиванием или каким-то подобным редактированием, вам следует подумать, правильный ли вид контейнера был выбран.

Чтобы переписать значение, нужно удалить старое и вставить новое (ну или вставить новое и удалить старое). Нельзя просто взять и переписать прямым присваиванием.

//Листинг #2		clang		Переписываем значение в set

//clang 6.0.0

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    for (int i=0; i<10; i++){
       s.insert(i);    
    }
    
    cout << "before:\n";
    for (const auto &i: s){
       cout << i << ' ';    
    }
    
    set<int>::iterator it =  s.find(5);		//Находим точку переназначения
    s.erase(it);							//Удаляем это значение из массива
    s.insert(10);							//Вставляем в массив нужное значение
    
    
    cout << "\nafter:\n";
    for (const auto &i: s){
       cout << i << ' ';    
    }
    
}

//Листинг #2 clang Переписываем значение в set

//clang 6.0.0

#include <iostream>

#include <set>

using namespace std;

int main()

{

set<int> s;

for (int i=0; i<10; i++){

s.insert(i);

}

cout << "before:\n";

for (const auto &i: s){

cout << i << ' ';

}

set<int>::iterator it = s.find(5); //Находим точку переназначения

s.erase(it); //Удаляем это значение из массива

s.insert(10); //Вставляем в массив нужное значение

cout << "\nafter:\n";

for (const auto &i: s){

cout << i << ' ';

}

Удалить и вставить значение как новое намного эфективнее, чем приходилось бы делать неоправданную сортировку на каждое присваивание. Эффективность связана и с тем, что и вставка, и удаление в set — это быстрые операции.

Бывает и так, что нужно задать свой порядок для упорядоченного массива, от чего как раз иногда и возникают вопросы, а как отсортировать.

Задавать свой порядок упорядоченным массивам можно, а нужно это делать в момент объявления массива. Для задействования своего порядка следует использовать функтор.

//Листинг #3		clang 6.0.0		Использование собственного порядка в set

#include <iostream>
#include <set>

using namespace std;

/*ФУНКТОР-компаратор*/
struct My_Comparator{
    bool operator ()(const int x, const int y) const{
        return x < y;	//определяем условие сравнения
    }
};

int main()
{
    set<int, My_Comparator> s; //Указываем ФУНКТОР-компаратор в момент объявления 
    
}

//Листинг #3 clang 6.0.0 Использование собственного порядка в set

#include <iostream>

#include <set>

using namespace std;

/*ФУНКТОР-компаратор*/

struct My_Comparator{

bool operator ()(const int x, const int y) const{

return x < y; //определяем условие сравнения

}

};

int main()

{

set<int, My_Comparator> s; //Указываем ФУНКТОР-компаратор в момент объявления

}

Иногда может быть нужно усечь set, сделать ему resize. Одно дело, если нужно сделать массив пустым, для этого достаточно использовать clear(), а другое, когда массив с десятком тысяч значений хочется усечь до, например, первых пятиста, и подавать значения порциями по пятьсот. Читающие эту тему уже могли и должны понимать или хотя бы догадываться, что для ассоциативных упорядоченных массивов прямое усечение невозможно, т. е. нельзя как вектору vector сделать resize для set, можно только создавать новый set на основании исходного. В создании нового set и внесении в него значений из старого нет ничего такого, с чем новичок бы не справился, но есть несколько способов: чисто новичковые и в духе STL.

//Листинг #4.1		clang 6.0.0		Новичок усекает set использованием вспомогательного set (очень плохой подход)

#include <iostream>
#include <set>

using namespace std;

void print(const set<int> s, const char* info){
    if (s.empty()){
        cout << "empty\n";
        return;
    }
    cout << "\nstart " << info << '\n';
    for (const auto &i: s){
       cout << i << ' ';
    }
    cout << "\nend " << info << "\n\n";
}

int main()
{
    set<int> s;
    for (int i=0; i<100; i++){
       s.insert(i);
    }

    print(s, "before");

    set<int> temp_set(s);
    set<int>::iterator cursor = s.end();                  //текущий элемент
    set<int>::iterator start_erase = s.begin();           //точка начала среза
    set<int>::iterator temp;                              //вспогательный итератор

    int N = 9;   //Будем отсекать всё после девятого элемента

    /*устанавливаем итераторы на позиции*/
    cursor--;							//ставим курсор на последний элемент
    advance(start_erase, N);			//устанавливаем место среза	

    /*отсекаем элементы*/
    if (N < s.size()){
		while ( (temp != start_erase)  ){  
			  temp = cursor;
			  cursor--;
			  s.erase(temp);
		}
    } else {
       cout << "нельзя отсечь что-то за пределами массива\n";    
    }

    print(s, "after");
}

//Листинг #4.1 clang 6.0.0 Новичок усекает set использованием вспомогательного set (очень плохой подход)

#include <iostream>

#include <set>

using namespace std;

void print(const set<int> s, const char* info){

if (s.empty()){

cout << "empty\n";

return;

}

cout << "\nstart " << info << '\n';

for (const auto &i: s){

cout << i << ' ';

}

cout << "\nend " << info << "\n\n";

}

int main()

{

set<int> s;

for (int i=0; i<100; i++){

s.insert(i);

}

print(s, "before");

set<int> temp_set(s);

set<int>::iterator cursor = s.end(); //текущий элемент

set<int>::iterator start_erase = s.begin(); //точка начала среза

set<int>::iterator temp; //вспогательный итератор

int N = 9; //Будем отсекать всё после девятого элемента

/*устанавливаем итераторы на позиции*/

cursor--; //ставим курсор на последний элемент

advance(start_erase, N); //устанавливаем место среза

/*отсекаем элементы*/

if (N < s.size()){

while ( (temp != start_erase) ){

temp = cursor;

cursor--;

s.erase(temp);

}

} else {

cout << "нельзя отсечь что-то за пределами массива\n";

}

print(s, "after");

}

Такое написать может быть сложно на уровне новичка. Но это не только сложно написать новичку, но и сам код относительно многословный: много текста, много переменных, циклы… А в попытках это написать можно столкнуться с обращением к невалидному итератору, с попыткой вытащить значение или из s.end(), или из s.begin(), с выходом за пределы массива, с удалением элементов через один и мало ли чем ещё. В общем, любопытным имеет смысл разобраться, как это работает, а вообще прямое отсечение удалением — это, наверное, самый худший способ решить такую задачу усечения, а #4.2 — яркий пример, как делать ни в коем случае нельзя.

Более продвинутый новичок имеет иной уровень мышления и использует удаление копированием: создаёт новый массив, копирует в него нужные значения, а потом либо использует полученный, либо меняет массивы местами и удаляет ненужный.

У set нет доступа по индексу, поэтому, чтобы попасть на элемент по порядковому номеру, можно использовать advance.

//Листинг #4.2		clang 6.0.0		Новичок усекает set удалением копированием и использованием вспомогательного set

#include <iostream>
#include <set>

using namespace std;

void print(const set<int> s, const char* info){
    if (s.empty()){
        cout << "empty\n";
        return;
    }
    cout << "\nstart " << info << '\n';
    for (const auto &i: s){
       cout << i << ' ';
    }
    cout << "\nend " << info << "\n\n";
}

int main()
{
    set<int> s;
    for (int i=0; i<100; i++){
       s.insert(i);    
    }
    
    print(s, "after");
    
    int N = 50;		//отсекаем всё после указанной позиции
    set<int> temp;	//вспомогательный массив
    set<int>::iterator it = s.begin();  //итератор для пощиционирования по массиву
   
   /*ЗАПОЛНЯЕМ МАССИВ ЗНАЧЕНИЯМИ В НУЖНОМ КОЛИЧЕСТВЕ*/
    for (int i=0; i<N; i++){        
       temp.insert(*it);  
       it++;
    }
    swap(s, temp);  //меняем местами
    temp.clear();   //удаляем
   
    print(s, "after");
    
}

//Листинг #4.2 clang 6.0.0 Новичок усекает set удалением копированием и использованием вспомогательного set

#include <iostream>

#include <set>

using namespace std;

void print(const set<int> s, const char* info){

if (s.empty()){

cout << "empty\n";

return;

}

cout << "\nstart " << info << '\n';

for (const auto &i: s){

cout << i << ' ';

}

cout << "\nend " << info << "\n\n";

}

int main()

{

set<int> s;

for (int i=0; i<100; i++){

s.insert(i);

}

print(s, "after");

int N = 50; //отсекаем всё после указанной позиции

set<int> temp; //вспомогательный массив

set<int>::iterator it = s.begin(); //итератор для пощиционирования по массиву

/*ЗАПОЛНЯЕМ МАССИВ ЗНАЧЕНИЯМИ В НУЖНОМ КОЛИЧЕСТВЕ*/

for (int i=0; i<N; i++){

temp.insert(*it);

it++;

}

swap(s, temp); //меняем местами

temp.clear(); //удаляем

print(s, "after");

}

В #4.2 разумный подход, тут и кода меньше, и придумывать это проще, чем #4.1. И вообще так делать можно, но это всё же новичковое решение.

Наиболее лёгким и безболезным способом отсечения будет использование алгоритмов. В STL есть copy_n: алгоритм количественного копирования (примечание: он не имеет названия "количественного копирования", просто мне удобно сейчас использовать такую формулировку).

//Листинг #4.3		clang 6.0.0		Усекчение set удалением копированием с использованием вспомогательного set

#include <iostream>
#include <set>

using namespace std;

void print(const set<int> s, const char* info){
    if (s.empty()){
        cout << "empty\n";
        return;
    }
    cout << "\nstart " << info << '\n';
    for (const auto &i: s){
       cout << i << ' ';
    }
    cout << "\nend " << info << "\n\n";
}

int main()
{
    set<int> s;
    for (int i=1; i<100; i++){
       s.insert(i);
    }

    print(s, "before");

    int N = 20;
    set<int> temp;
    copy_n(s.begin(), N, inserter(temp, temp.end()));  //Откуда, сколько, и как бы вставляем итераторы в создаваемый массив

    print(temp, "after");

}

//Листинг #4.3 clang 6.0.0 Усекчение set удалением копированием с использованием вспомогательного set

#include <iostream>

#include <set>

using namespace std;

void print(const set<int> s, const char* info){

if (s.empty()){

cout << "empty\n";

return;

}

cout << "\nstart " << info << '\n';

for (const auto &i: s){

cout << i << ' ';

}

cout << "\nend " << info << "\n\n";

}

int main()

{

set<int> s;

for (int i=1; i<100; i++){

s.insert(i);

}

print(s, "before");

int N = 20;

set<int> temp;

copy_n(s.begin(), N, inserter(temp, temp.end())); //Откуда, сколько, и как бы вставляем итераторы в создаваемый массив

print(temp, "after");

}

#4.3 — это практически то же самое, что и #4.2 (используется тот же подход), только занимает написание такого кода намного меньше времени. Если кто не знает, то существуют адаптеры итераторов, в которые входят итераторы вставки: вставки в начало, вставки в конец и вставки в указанную позицию. set так устроен, что у него не может быть операции вставки в начало или в конец, но может быть операция просто вставки, поэтому из адаптеров итераторов вставки — для set походит только итератор вставки inserter. Первый аргумент, нужный адаптеру — это контейнер, в который вставлятся элемент, а второй аргумент — это позиция. В случае с set можно указывать любую позицию из диапазона самого set — она служит подсказкой, а не позицией вставки и может игнорироваться компилятором. Само же понятие адаптеров в данном случае подразумевает, что используются такие виды итераторов в алгоритмах. Алгоритм копирования, использующий операторы вставки, будет не перезаписывать значения, а добавлять.

Итераторы вставки используются для того, чтобы дать алгоритмам возможность работать в режиме вставки, а не замены. В частности, итераторы вставки решают проблему, возникающую, когда в диапазоне назначения нет достаточного места: они позволяют увеличивать размер диапазона вставки.

//Листинг #aa
#include <iostream>
#include <iterator>
#include <set>
#include <algorithm>

using namespace std;

int main(){
    set<int> s{1, 2, 3};
    set<int> s2{4, 5, 6};
        
    
    copy(s.begin(), s.end(), inserter(s2, s2.begin()));  //Вставляем диапазон [s.begig()...s.end()] в s2
    
    for (const auto &i: s2){
       cout << i << ' ';   
    }
}

//Листинг #aa

#include <iostream>

#include <iterator>

#include <set>

#include <algorithm>

using namespace std;

int main(){

set<int> s{1, 2, 3};

set<int> s2{4, 5, 6};

copy(s.begin(), s.end(), inserter(s2, s2.begin())); //Вставляем диапазон [s.begig()...s.end()] в s2

for (const auto &i: s2){

cout << i << ' ';

}

//Листинг #ab
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    vector<int> s{1, 2, 3};
    vector<int> s2{4, 5, 6};
    
    
    //вставим весь s2 во вторую позицию s
    //1 4 5 6 2 3
    auto it = s.begin();
    advance(it, 1);  //определяем позицию вставки на уровне итераторов
    
    copy(s2.begin(), s2.end(), inserter(s, it)); //вставляем s2 в s с позиции it 
    for (const auto &i: s){
       cout << i << ' ';   
    }
}

//Листинг #ab

#include <iostream>

#include <iterator>

#include <vector>

#include <algorithm>

using namespace std;

int main(){

vector<int> s{1, 2, 3};

vector<int> s2{4, 5, 6};

//вставим весь s2 во вторую позицию s

//1 4 5 6 2 3

auto it = s.begin();

advance(it, 1); //определяем позицию вставки на уровне итераторов

copy(s2.begin(), s2.end(), inserter(s, it)); //вставляем s2 в s с позиции it

for (const auto &i: s){

cout << i << ' ';

}

Если эта статья кому-то помогла в чём-то разобраться, это замечательно.

Рубрика: STL, Массивы

Редактирование std::set на примере переписывания и отсечения значений

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета