5.3.2 Basic Sets

C++ sets are great data structures either on their own or combined with other data structures. As mentioned earlier, sets have two key features that distinguish them from vectors: they have no duplicates, and searches for elements in the set are done in a binary search fashion (as opposed to a vector’s linear search).

Creating a Set

Sets are a part of the C++ standard library but do need an include statement when using them.

#incluce <set>

Creating a set is very similar to other data structures. Then can either be declared empty or with initial values.

set<int> numbers { 1, 2, 3, 4};

set<string> fruit;

Inserting Into a Set

Inserting into a set is relatively straightforward, but interpreting the insert return command is a little more complicated. To insert into a set, you use the insert(value) command, for example:

fruit.insert("apple");

Since a set cannot contain duplicates, it is possible that a value already existed in the set. If it does exist, the insert will not add the new value. To find out if a value already existed and whether the new value was added, you need to look at the return value for the insert command.

The insert command return value is a pair, with the first value of the pair pointing to either the location of the new element or the location of the existing element if it already was in the set. It uses an iterator to point to that location.

The second element of the pair is a boolean value representing whether the new value was added. If it was added, this value will be true.

The basic form of the insert statement with a return value being stored as a variable would look like this:

pair<iterator, bool> varName = setName.insert(value);

Using the example above, you would have something like this:

pair<set<string>::iterator, bool> rtrn = fruit.insert("apple");

You can then interpret the return value for use. For example, if you wanted to determine if the new value was not already in the set, you could use a conditional statement:

if (rtrn.second) {
    cout << "Value added! << endl;
}

Alternatively you can skip creating the return variable and just interpret the return value directly:

if (fruit.insert("apple").second) {
    cout << "Value added! << endl;
}

Searching a Set

As mentioned above, one of the great advantages of a set is that it can be searched quickly. Behind the scenes, sets are stored in a binary tree-like format, which allows for a search to traverse the tree and find an element quickly.

To find an element in a set, you will use the find command. The find command returns an iterator that points to the element. If the element is not found, the find command will point to the end position of the set.

Here is an example of a search:

if (number.find(3) != numbers.end()) {
    cout << "The number is found." << endl;
}

Other Useful Set Functions

As you saw with other data structures such as stacks and queues, sets have a limited number of functions. In addition to the find and insert functions, there are a few others that you may come across.

Here are the most commonly used set functions:

Function	Return Type	Description
insert(value)	pair	Inserts element into set. Returns position of element and bool to indicate whether the element was inserted.
find(value)	iterator	Searches for an element and returns the position of the element. Returns the end position if not found.
empty()	bool	Returns true if the set is empty, false otherwise.
size()	int	Returns the size of the set.
erase(iterator)	void	When passed an iterator position, erase will remove that element from a set.
clear()	void	Removes all elements from the set.
begin()	iterator	Returns the beginning position of the set.
end()	iterator	Returns the end position of a set.

Try This Example