C++
std :: set и std :: multiset

Вступление

замечания

Вставка значений в набор

Три разных метода вставки могут использоваться с наборами.

• Во-первых, простая вставка значения. Этот метод возвращает пару, позволяющую вызывающему абоненту проверить, действительно ли вставка произошла.
• Во-вторых, вставка, давая подсказку о том, где значение будет вставлено. Цель состоит в том, чтобы оптимизировать время вставки в таком случае, но знание того, где должно быть вставлено значение, не является обычным случаем. Будьте осторожны в этом случае; способ дать подсказку отличается от версий компилятора .
• Наконец, вы можете вставить диапазон значений, указав начальный и конечный указатель. Исходный из них будет включен во вставку, конечный - исключен.

#include <iostream>
#include <set>

int main ()
{
  std::set<int> sut;
  std::set<int>::iterator it;
  std::pair<std::set<int>::iterator,bool> ret;

  // Basic insert
  sut.insert(7);
  sut.insert(5);
  sut.insert(12);
  
  ret = sut.insert(23);
  if (ret.second==true)
    std::cout << "# 23 has been inserted!" << std::endl;
    
  ret = sut.insert(23); // since it's a set and 23 is already present in it, this insert should fail
  if (ret.second==false)
    std::cout << "# 23 already present in set!" << std::endl;
 
  // Insert with hint for optimization
  it = sut.end();
  // This case is optimized for C++11 and above
  // For earlier version, point to the element preceding your insertion
  sut.insert(it, 30); 

  // inserting a range of values
  std::set<int> sut2;
  sut2.insert(20);
  sut2.insert(30);
  sut2.insert(45);
  std::set<int>::iterator itStart = sut2.begin();
  std::set<int>::iterator itEnd = sut2.end();
  
  sut.insert (itStart, itEnd); // second iterator is excluded from insertion

  std::cout << std::endl << "Set under test contains:" << std::endl;
  for (it = sut.begin(); it != sut.end(); ++it)
  {
    std::cout << *it << std::endl;
  }

  return 0;
}

Выход будет:

# 23 has been inserted!                                                                                                                                                                                                                                                                                                   
# 23 already present in set!                                                                                                                                                                                                                                                                                              
                                                                                                                                                                                                                                                                                                                          
Set under test contains:                                                                                                                                                                                                                                                                                                  
5                                                                                                                                                                                                                                                                                                                         
7                                                                                                                                                                                                                                                                                                                         
12                                                                                                                                                                                                                                                                                                                        
20                                                                                                                                                                                                                                                                                                                        
23                                                                                                                                                                                                                                                                                                                        
30                                                                                                                                                                                                                                                                                                                        
45   

Вставка значений в мультимножество

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

auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);

Изменение типа сортировки по умолчанию

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

Представим себе, что мы сохраняем строковые значения в наборе, но мы знаем, что эти строки содержат только числовые значения. По умолчанию сортировка будет представлять собой сравнение лексикографической строки, поэтому порядок не будет соответствовать численному типу. Если вы хотите применить сортировку, эквивалентную тому, что у вас было бы с значениями int , вам нужен функтор для перегрузки метода сравнения:

#include <iostream>
#include <set>
#include <stdlib.h> 

struct custom_compare final
{
    bool operator() (const std::string& left, const std::string& right) const
    {
        int nLeft = atoi(left.c_str());
        int nRight = atoi(right.c_str());
        return nLeft < nRight;
    }
};

int main ()
{
    std::set<std::string> sut({"1", "2", "5", "23", "6", "290"});
  
    std::cout << "### Default sort on std::set<std::string> :" << std::endl;
    for (auto &&data: sut)
        std::cout << data << std::endl;
  
    std::set<std::string, custom_compare> sut_custom({"1", "2", "5", "23", "6", "290"},
                                                     custom_compare{}); //< Compare object optional as its default constructible.
  
    std::cout << std::endl << "### Custom sort on set :" << std::endl;
    for (auto &&data : sut_custom)
        std::cout << data << std::endl;
  
    auto compare_via_lambda = [](auto &&lhs, auto &&rhs){ return lhs > rhs; };
    using set_via_lambda = std::set<std::string, decltype(compare_via_lambda)>;
    set_via_lambda sut_reverse_via_lambda({"1", "2", "5", "23", "6", "290"},
                                          compare_via_lambda);
  
    std::cout << std::endl << "### Lambda sort on set :" << std::endl;
    for (auto &&data : sut_reverse_via_lambda)
        std::cout << data << std::endl;

    return 0;
}

Выход будет:

### Default sort on std::set<std::string> :
1
2
23
290
5
6
### Custom sort on set :
1
2
5
6
23
290  

### Lambda sort on set :
6
5
290
23
2
1

В приведенном выше примере можно найти 3 разных способа добавления операций сравнения в std::set , каждый из которых полезен в своем собственном контексте.

Сорт по умолчанию

Это будет использовать оператор сравнения ключа (первый аргумент шаблона). Часто ключ уже обеспечивает хорошее значение по умолчанию для функции std::less<T> . Если эта функция не является специализированной, она использует operator< объекта. Это особенно полезно, когда другой код также пытается использовать некоторый порядок, поскольку это позволяет обеспечить согласованность всей базы кода.

Написание кода таким образом уменьшит усилия по обновлению вашего кода, когда ключевыми изменениями будут API, например: класс, содержащий 2 члена, который изменяется на класс, содержащий 3 члена. Обновляя operator< в классе, все вхождения будут обновляться.

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

Пользовательский вид

Добавление пользовательской сортировки через объект с оператором сравнения часто используется, когда сравнение по умолчанию не выполняется. В приведенном выше примере это связано с тем, что строки ссылаются на целые числа. В других случаях это часто используется, когда вы хотите сравнивать (умные) указатели на основе объекта, на который они ссылаются, или потому, что вам нужны разные ограничения для сравнения (например: сравнение std::pair по значению first ).

При создании оператора сравнения это должна быть стабильная сортировка. Если результат оператора сравнения изменяется после вставки, вы будете иметь неопределенное поведение. Как хорошая практика, ваш оператор сравнения должен использовать только постоянные данные (константные члены, функции const ...).

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

Лямбда-сортировка

Lambdas - это более короткий способ писать объекты функции. Это позволяет записывать оператор сравнения на меньшее количество строк, делая общий код более удобочитаемым.

Недостатком использования lambdas является то, что каждый lambda получает определенный тип во время компиляции, поэтому decltype(lambda) будет отличаться для каждой компиляции одной и той же единицы компиляции (файл cpp) как множество множественных единиц компиляции (если они включены в заголовочный файл ). По этой причине рекомендуется использовать функциональные объекты в качестве оператора сравнения при использовании в файлах заголовков.

Эта конструкция часто встречается, когда std::set используется в локальной области действия функции, тогда как функциональный объект является предпочтительным при использовании в качестве аргументов функции или членов класса.

Другие варианты сортировки

Поскольку оператор сравнения std::set является аргументом шаблона, все вызываемые объекты могут использоваться как оператор сравнения, а приведенные выше примеры - это только конкретные случаи. Единственными ограничениями, которые имеют эти вызываемые объекты, являются:

• Они должны быть готовы к копированию
• Они должны быть вызваны двумя аргументами типа ключа. (подразумеваемые преобразования разрешены, но не рекомендуется, так как это может повредить производительность)

Поиск значений в наборе и мультимножестве

Существует несколько способов поиска заданного значения в std::set или в std::multiset :

Чтобы получить итератор первого вхождения ключа, можно использовать функцию find() . Он возвращает end() если ключ не существует.

  std::set<int> sut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(3); // contains 3, 10, 15, 22    

  auto itS = sut.find(10); // the value is found, so *itS == 10
  itS = sut.find(555); // the value is not found, so itS == sut.end()   

  std::multiset<int> msut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(15);
  sut.insert(3); // contains 3, 10, 15, 15, 22  

  auto itMS = msut.find(10);

Другой способ - использовать функцию count() , которая подсчитывает, сколько соответствующих значений найдено в set / multiset (в случае set , возвращаемое значение может быть только 0 или 1). Используя те же значения, что и выше, мы будем иметь:

int result = sut.count(10); // result == 1
result = sut.count(555); // result == 0

result = msut.count(10); // result == 1
result = msut.count(15); // result == 2

В случае std::multiset может быть несколько элементов, имеющих одинаковое значение. Чтобы получить этот диапазон, можно использовать функцию equal_range() . Он возвращает std::pair имеющую нижнюю границу итератора (включительно) и верхнюю границу (исключая) соответственно. Если ключ не существует, оба итератора будут указывать на ближайшее превосходное значение (на основе метода сравнения, используемого для сортировки заданного multiset ).

auto eqr = msut.equal_range(15);
auto st = eqr.first; // point to first element '15'
auto en = eqr.second; // point to element '22'

eqr = msut.equal_range(9); // both eqr.first and eqr.second point to element '10'

Удаление значений из набора

Самый очевидный метод, если вы просто хотите сбросить свой набор / мультимножество на пустой, - это использовать clear :

  std::set<int> sut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(3); 
  sut.clear(); //size of sut is 0

Затем можно использовать метод erase . Он предлагает несколько возможностей, несколько похожих на вставку:

std::set<int> sut;
std::set<int>::iterator it;
          
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3); 
sut.insert(30);
sut.insert(33);
sut.insert(45);
    
// Basic deletion
sut.erase(3);
    
// Using iterator
it = sut.find(22);
sut.erase(it);
          
// Deleting a range of values
it = sut.find(33);
sut.erase(it, sut.end());
    
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
  std::cout << *it << std::endl;
}

Выход будет:

Set under test contains:                                                                                                                                                                                                                                                                                                  
10                                                                                                                                                                                                                                                                                                                        
15                                                                                                                                                                                                                                                                                                                        
30 

Все эти методы также применяются к multiset . Обратите внимание, что если вы попросите удалить элемент из multiset , и он присутствует несколько раз, все эквивалентные значения будут удалены .