Как в set найти элемент

If you were going to add a contains function, it might look like this:

#include <algorithm>
#include <iterator>

template<class TInputIterator, class T> inline
bool contains(TInputIterator first, TInputIterator last, const T& value)
{
    return std::find(first, last, value) != last;
}

template<class TContainer, class T> inline
bool contains(const TContainer& container, const T& value)
{
    // This works with more containers but requires std::begin and std::end
    // from C++0x, which you can get either:
    //  1. By using a C++0x compiler or
    //  2. Including the utility functions below.
    return contains(std::begin(container), std::end(container), value);

    // This works pre-C++0x (and without the utility functions below, but doesn't
    // work for fixed-length arrays.
    //return contains(container.begin(), container.end(), value);
}

template<class T> inline
bool contains(const std::set<T>& container, const T& value)
{
    return container.find(value) != container.end();
}

This works with std::set, other STL containers, and even fixed-length arrays:

void test()
{
    std::set<int> set;
    set.insert(1);
    set.insert(4);
    assert(!contains(set, 3));

    int set2[] = { 1, 2, 3 };
    assert(contains(set2, 3));
}

Edit:

As pointed out in the comments, I unintentionally used a function new to C++0x (std::begin and std::end). Here is the near-trivial implementation from VS2010:

namespace std {

template<class _Container> inline
    typename _Container::iterator begin(_Container& _Cont)
    { // get beginning of sequence
    return (_Cont.begin());
    }

template<class _Container> inline
    typename _Container::const_iterator begin(const _Container& _Cont)
    { // get beginning of sequence
    return (_Cont.begin());
    }

template<class _Container> inline
    typename _Container::iterator end(_Container& _Cont)
    { // get end of sequence
    return (_Cont.end());
    }

template<class _Container> inline
    typename _Container::const_iterator end(const _Container& _Cont)
    { // get end of sequence
    return (_Cont.end());
    }

template<class _Ty,
    size_t _Size> inline
    _Ty *begin(_Ty (&_Array)[_Size])
    { // get beginning of array
    return (&_Array[0]);
    }

template<class _Ty,
    size_t _Size> inline
    _Ty *end(_Ty (&_Array)[_Size])
    { // get end of array
    return (&_Array[0] + _Size);
    }

}

In this article we will discuss how to check if a given element exists in set or not.

Suppose we have a set of strings i.e.

Advertisements

// Set of strings
std::set<std::string> setOfStrs = { "the", "is", "of" , "from" , "at" , "hello" , "the" };

Now we wnat to check if any given string exists in the set or not. Let’s do this using two different techniques i.e.

Search for an element in Set using set::find()

std::set provides a member function to find the existance of a given element in set i.e.

Frequently Asked:

• How to Access Element by index in a Set | C++
• Set vs Map : How to choose a right associative container ?
• Different ways to Erase / Delete an element from a Set in C++
• C++: Convert Set to Vector

iterator find (const value_type& val);

It accepts the element as argument and search for that in the set. If the element is found in set then it returns the iterator pointing to that element else it returns the iterator pointing to the end of set.

Let’s use set::find() function to check if “at” exists in above set or not i.e.

// search for the iterator of given string in set
std::set<std::string>::iterator it = setOfStrs.find("at");

// Check if iterator it is valid
if (it != setOfStrs.end())
{
	std::cout << "'at' found in set" << std::endl;
}

We can not modify the element pointed by this iterator because this element is used for indexing inside the set, changing it will make the indexing wrong. Therefore we can access the element through iterator but cannot modify it.

Search for an element in Set using set::count()

std::set provides a member function to find the occurrence count of a given element in set i.e.

size_type count (const value_type& val) const;

It accepts the element as argument and search for its occurrence count in the set. As std::set can contain only unique elements, so occurrence count of the given element can be only 0 or 1 i.e,

If found then 1 else 0.

Let’s use set::count() function to check if “hello” exists in above set or not i.e.

// Fetch the occurrence count of given string in set
if (setOfStrs.count("hello") != 0)
{
	std::cout << "'hello' found in set" << std::endl;
}

Checkout the complete example as follows,

#include <iostream>
#include <set>
#include <string>
#include <algorithm>
#include <iterator>

int main()
{
	// Set of strings
	std::set<std::string> setOfStrs = { "the", "is", "of" , "from" , "at" , "hello" , "the" };

	// search for the iterator of given string in set
	std::set<std::string>::iterator it = setOfStrs.find("at");

	// Check if iterator it is valid
	if (it != setOfStrs.end())
	{
		std::cout << "'at' found in set" << std::endl;
	}

	// Modification is not allowed
	//*it = "AND";

	// search for the iterator of given string in set
	it = setOfStrs.find("text");
	// Check if iterator it is valid
	if (it != setOfStrs.end())
		std::cout << "'text' found in set" << std::endl;
	else
		std::cout << "'text' not found in set" << std::endl;

	// Fetch the occurrence count of given string in set
	if (setOfStrs.count("hello") != 0)
	{
		std::cout << "'hello' found in set" << std::endl;
	}

	return 0;

}

Output:

'at' found in set
'text' not found in set
'hello' found in set

Both set::find() and set:: count() helps to check the existence of an element in set. But why 2 different method for same thing ?

Complexity wise both find() and count() are same. Main difference is that set::find() returns the iterator of the given element. Iterator is useful if we have user define objects in set, instead of primitive data types.

As set::find() returns the iterator, We can perform operations on the object pointed by iterator, also we can modify the mutable content of that object

Suppose we have a struct Student i.e.

// Student with ID and name
// Name is mutable, so can be modified by const object
struct Student
{
	int mId;
	mutable std::string mName;
	Student(int id, std::string name) :
			mId(id), mName(name)
	{
	}
};

A Functor / Comparator, to compare Student objects using ID i.e.

// Student comparator / Functor
// Compare objects with ID only
struct StudentComp
{
	bool operator()(const Student& lhs, const Student& rhs) const
	{
		return lhs.mId < rhs.mId;
	}
};

Let’s Create a set of Student objects i.e.

// Set of Student class objects
std::set<Student, StudentComp> setOfStudents =
		{ Student(1, "Shaun"), Student(2, "Riti"), Student(3, "Aadi"),
		  Student(4,"Vicky"), Student(5, "Renu") };

Find a Student object with id 3 using set::find() and modify its name, because mName is mutable and can be modifies eve with const objects i.e.

// Find a student with id 3
std::set<Student, StudentComp>::iterator it = setOfStudents.find( Student(3, ""));

// Check if Iterator is valid
if (it != setOfStudents.end())
{
	// Modify the mutuable content which is not
	// used in comparision or indexing
	it->mName = "Aarav";
	std::cout << it->mId << " :: " << it->mName << std::endl;
}

Now search for an element with count() i.e.

// Check if a student with ID 3 exists in set
// Not possible to fetch the iterator with count(),
// It returns the count only
if (setOfStudents.count(Student(3, "")) != 0)
{
	std::cout << it->mId << " Exist in Set" << std::endl;
}

We will not get any iterator with set::count(), so its not possible to perform any operation or modify content with count().

Complete example is as follows,

#include <iostream>
#include <set>
#include <string>
#include <algorithm>
#include <iterator>

// Student with ID and name
// Name is mutable, so can be modified by const object
struct Student
{
	int mId;
	mutable std::string mName;
	Student(int id, std::string name) :
			mId(id), mName(name)
	{
	}
};

// Student comparator / Functor
// Compare objects with ID only
struct StudentComp
{
	bool operator()(const Student& lhs, const Student& rhs) const
	{
		return lhs.mId < rhs.mId;
	}
};

int main()
{
	// Set of Student class objects
	std::set<Student, StudentComp> setOfStudents =
			{ Student(1, "Shaun"), Student(2, "Riti"), Student(3, "Aadi"),
			  Student(4,"Vicky"), Student(5, "Renu") };

	// Find a student with id 3
	std::set<Student, StudentComp>::iterator it = setOfStudents.find( Student(3, ""));

	// Check if Iterator is valid
	if (it != setOfStudents.end())
	{
		// Modify the mutuable content which is not
		// used in comparision or indexing
		it->mName = "Aarav";
		std::cout << it->mId << " :: " << it->mName << std::endl;
	}

	// Check if a student with ID 3 exists in set
	// Not possible to fetch the iterator with count(),
	// It returns the count only
	if (setOfStudents.count(Student(3, "")) != 0)
	{
		std::cout << it->mId << " Exist in Set" << std::endl;
	}

	return 0;

}

#include <iostream>
#include <set>
#include <string>
#include <algorithm>
#include <iterator>

// Student with ID and name
// Name is mutable, so can be modified by const object
struct Student
{
	int mId;
	mutable std::string mName;
	Student(int id, std::string name) :
			mId(id), mName(name)
	{
	}
};

// Student comparator / Functor
// Compare objects with ID only
struct StudentComp
{
	bool operator()(const Student& lhs, const Student& rhs) const
	{
		return lhs.mId < rhs.mId;
	}
};

int main()
{
	// Set of Student class objects
	std::set<Student, StudentComp> setOfStudents =
			{ Student(1, "Shaun"), Student(2, "Riti"), Student(3, "Aadi"),
			  Student(4,"Vicky"), Student(5, "Renu") };

	// Find a student with id 3
	std::set<Student, StudentComp>::iterator it = setOfStudents.find( Student(3, ""));

	// Check if Iterator is valid
	if (it != setOfStudents.end())
	{
		// Modify the mutuable content which is not
		// used in comparision or indexing
		it->mName = "Aarav";
		std::cout << it->mId << " :: " << it->mName << std::endl;
	}

	// Check if a student with ID 3 exists in set
	// Not possible to fetch the iterator with count(),
	// It returns the count only
	if (setOfStudents.count(Student(3, "")) != 0)
	{
		std::cout << it->mId << " Exist in Set" << std::endl;
	}

	return 0;

}

Output:

3 :: Aarav
3 Exist in Set

S.erase(x);

S.erase(S.find(x));

set <int> S;

set <int>::iterator it;

for (it = S.begin(); it != S.end(); ++it)

    cout << *it << ” “

for (auto elem: S)

    cout << elem << ” “;

for (auto it = S.rbegin(); it != S.rend(); ++it)

    cout << *it << ” “;

auto it = S.begin();

–it;

S.erase(it);

auto it = S.upper_bound(x);

if (it != S.end())

    S.erase(it);

Множества в Python – это структура данных, которые содержат неупорядоченные элементы. Элементы также не является индексированным. Как и список, множество позволяет внесение и удаление элементов. Однако, есть ряд особенных характеристик, которые определяют и отделяют множество от других структур данных:

• Множество не содержит дубликаты элементов;
• Элементы множества являются неизменными (их нельзя менять), однако само по себе множество является изменяемым, и его можно менять;
• Так как элементы не индексируются, множества не поддерживают никаких операций среза и индексирования.

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

Содержание:

• Создание множеств
• Доступ к элементам множеств
• Добавление элементов во множество
• Удаление элементов из множеств
• Объединение множеств
• Пересечение множеств
• Разница множеств
• Сравнение множеств
• Методы множеств
• Frozenset в Python
• Вывод

Создание множеств

Существует два пути, следуя которым, мы можем создавать множества в Python.

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

Рассмотрим пример создания множества в Python:

Результат:

Только что мы создали множество чисел. Мы также можем создать множество из строк. Например:

Результат:

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

Мы также можем создать множество с элементами разных типов. Например:

Результат:

Все элементы в упомянутом выше множестве принадлежат разным типам.

Мы также можем создать множество из списков. Это можно сделать, вызвав встроенную функцию Python под названием set(). Например:

Результат:

Как упоминалось ранее, множества не содержат дубликаты элементов. Предположим, наш список содержит дубликаты элементов, как показано ниже:

Результат:

Множество удалило дубликаты и выдало только по одному экземпляру элементов. Это также происходит при создании множества с нуля. Например:

Результат:

И снова, множество удалило дубликаты и вернуло только один из дублируемых объектов.

Создание пустого множества подразумевает определенную хитрость. Если вы используете пустые фигурные скобки {} в Python, вы скорее создадите пустой словарь, а не множество. Например:

Результат:

Как показано в выдаче, тип переменной х является словарем.

Чтобы создать пустое множество в Python, мы должны использовать функцию set() без передачи какого-либо значения в параметрах, как показано ниже:

Результат:

Выдача показывает, что мы создали множество.

Доступ к элементам множеств

Python не предоставляет прямой способ получения значения к отдельным элементам множества. Однако, мы можем использовать цикл для итерации через все элементы множества. Например:

Результат:

Мы также можем проверить наличие элемента во множестве при помощи in, как показано ниже:

Результат:

Код возвращает «True«, а это означает, что элемент был найден во множестве. Аналогичным образом, при поиске элемента, который отсутствует во множестве, мы получим «False«, как показано ниже:

Как и ожидалось, код вернул «False«.

Добавление элементов во множество

Python позволяет нам вносить новые элементы во множество при помощи функции add(). Например:

Результат:

Элемент «Feb» успешно внесен во множество. Если это было множество чисел, мы не можем передать новый элемент внутри скобочек, как мы делаем это для строк. Например:

Результат:

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

Удаление элемента из множеств

Python позволяет нам удалять элемент из множества, но не используя индекс, так как множество элементов не индексированы. Элементы могут быть удалены при помощи обоих методов discard() и remove().

Помните, что метод discard() не будет выдавать ошибку, если элемент не был найден во множестве. Однако, если метод remove() используется и элемент не был найден, возникнет ошибка.

Давайте продемонстрируем как удалять элемент при помощи метода discard():

Результат:

Элемент 3 был удален из множества.

Аналогично, метод remove() может использоваться следующим образом:

Результат:

Теперь попробуем удалить элемент, которого нет во множестве. Сначала используем метод discard():

Результат:

Выдача выше показывает, что никакого воздействия на множество не было оказано. Теперь посмотрим, что выйдет из использования метода remove() по аналогичному сценарию:

Результат:

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

С методом pop(), мы можем удалить и вернуть элемент. Так как элементы находятся в произвольном порядке, мы не можем утверждать или предсказать, какой элемент будет удален.

Например:

Результат:

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

Результат:

Эти элементы остаются во множестве.

Метод Python под названием clear() поможет удалить все элементы во множестве. Например:

Результатом является пустой set() без каких-либо элементов внутри.

Объединение множеств

Предположим, у нас есть два множества, А и В. Объединение этих двух множеств — это множество со всеми элементами обеих множеств. Такая операция выполняется при помощи функции Python под названием union().

Рассмотрим пример:

Результат:

Объединение может состоять из более чем двух множеств, и все их элементы сложатся в одно большое множество. Например:

Результат:

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

Результат:

Оператор | может также использоваться при поиске объединения двух или более множеств. Например:

Результат:

Если вы хотите создать объединение из более двух множеств, разделите названия множеств при помощи оператора | . Взглянем на пример:

Результат:

Пересечение множеств

Предположим, у вас есть два множества: А и В. Их пересечение представляет собой множество элементов, которые являются общими для А и для В.

Операция пересечения во множествах может быть достигнута как при помощи оператора &, так и метода intersection(). Рассмотрим пример:

В обеих множествах 3 является общим элементом. То же самое может быть достигнуто при использовании метода intersection():

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

Разница между множествами

Предположим, у вас есть два множества: А и В. Разница между А и В (А — В) — это множество со всеми элементами, которые содержатся в А, но не в В. Соответственно, (В — А) — это множество со всеми элементами в В, но не в А.

КОД

Для определения разницы между множествами в Python, мы можем использовать как функцию difference(), так и оператор — . Рассмотрим пример:

Результат:

В показанном выше скрипте, только первые три элемента множества set_a отсутствуют во множестве set_b, формируя нашу выдачу. Оператор минус - можно также применить для нахождения разницы между двумя множествами, как показано ниже:

Результат:

Симметричная разница между множествами А и В — это множество с элементами, которые находятся в А и В, за исключением тех элементов, которые являются общими для обеих множеств. Это определяется использованием метода Python под названием symmetric_difference(), или оператора ^. Посмотрим на пример:

Результат:

Симметричную разницу можно также найти следующим образом:

Результат:

Сравнение множеств

Мы можем сравнить множества в зависимости от того, какие элементы в них содержатся. Таким образом, мы можем сказать, является ли множество родительским, или дочерним от другого множества. Результат такого сравнения будет либо True, либо False.

Чтобы проверить, является ли множество А дочерним от В, мы можем выполнить следующую операцию:

Чтобы узнать является ли множество В дочерним от А, мы можем выполнить следующую операцию, соответственно:

Например:

Результат:

Дочернее и родительское множество может также быть проверено при помощи методов issubset() и issuperset(), как показано ниже:

Результат:

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

Методы множеств

Python содержит огромное количество встроенных методов, включая следующие:

Метод copy()

Этот метод возвращает копию множества. Например:

Результат:

Выдача показывает, что х является копией множества string_set.

Метод isdisjoint()

Этот метод проверяет, является ли множество пересечением или нет. Если множества не содержат общих элементов, метод возвращает True, в противном случае — False. Например:

Результат:

Оба множества не имеют общих элементов, что делает выдачу True.

Метод len()

Этот метод возвращает длину множества, которая является общим количеством элементов во множестве. Пример:

Выдача показывает, что длина множества является 4.

Frozenset в Python

Frozenset (замороженное множество) – это класс с характеристиками множества, однако, как только элементы становятся назначенными, их нельзя менять. Кортежи могут рассматриваться как неизменяемые списки, в то время как frozenset-ы — как неизменные множества.

Множества являются изменяемыми и нехешируемыми, это значит, что мы не можем использовать их как словарные ключи. Замороженные множества (frozenset) являются хешированными и могут использоваться в качестве ключей словаря.

Для создания замороженного множества, мы используем метод frozenset(). Давайте создадим два замороженных множества, Х и Y:

Результат:

Замороженные множества поддерживают использование множественных методов Python, таких как copy(), difference(), symmetric_difference(), isdisjoint(), issubset(), intersection(), issuperset() и union().

Вывод

Данная статья предоставляет подробное введение во множества языка программирования Python. Математическое определение множеств аналогично определению множеств в Python.

Множество — это набор элементов в произвольном порядке. Само по себе, множество является изменяемым, однако его элементы являются неизменяемыми.

Однако, мы можем добавлять и убирать элементы из множества без каких-либо проблем. В большей структур данных элементы являются индексированными. Однако, элементы множеств не являются индексированными. Это делает невозможным для нас выполнять операции, которые направлены на определенные элементы множества.