vector, set, map

Data Structures

Often, while solving problems, we need various data structures to do so efficiently, easily, and with minimal coding. Below are some of the most commonly used data structures.

The presented data structures are implemented as classes. In all cases, the type of elements stored/handled must be specified in advance. For example, if we want to use int or Course, we must define it ahead of time.

These implementations use what's called a template, which is not part of this practice material, but it's useful to know about. The template is similar to Java's generics. If we make a mistake, the compiler may generate long error messages, which may be harder to understand than usual.

Set (std::set)

In a set, each element may only appear once. The contained elements cannot be modified (they are stored as const), but they can be removed. Every element is stored in sorted order in a tree, so we need to ensure the type is sortable using operator<. If a type doesn’t support comparison, attempting to store it in a set will result in a compilation error.

To use a set, you must include the set header.

Example of creation and usage:

#include <iostream>
#include <set>

class Course {
private:
    int id;
public:
    Course(int id) : id(id) {}
    int getId() const { return id; }
    bool operator<(const Course& course) const { return this->id < course.id; }
};

bool courseExists(const std::set<Course>& courses, Course course) {
    return courses.find(course) != courses.end();
}

/// contains is only available in C++20
bool courseExists2(const std::set<Course>& courses, Course course) {
    return courses.contains(course);
}

int main() {
  std::set<Course> courseSet;
  Course c1(1);
  Course c2(2);
  Course c3(3);
  Course c12(1);

  courseSet.insert(c1);
  std::cout << courseSet.size() << std::endl;
  courseSet.insert(c2);
  std::cout << courseSet.size() << std::endl;
  courseSet.insert(c3);
  std::cout << courseSet.size() << std::endl;
  courseSet.insert(c12);
  std::cout << courseSet.size() << std::endl;

  int course_id = 1;
  Course search(course_id);
  if (courseExists(courseSet, search)) {
    std::cout << "Course exists, id: " << course_id << std::endl;
  } else {
    std::cout << "Course does not exist, id: " << course_id << std::endl;
  }

  course_id = 2;
  Course search2(course_id);
  if (courseExists2(courseSet, search2)) {
    std::cout << "Course exists, id: " << course_id << std::endl;
  } else {
    std::cout << "Course does not exist, id: " << course_id << std::endl;
  }

  std::cout << "Currently available courses:" << std::endl;
  for (Course c : courseSet) {
    std::cout << "  - " << c.getId() << std::endl;
  }

  Course toDelete(3);
  courseSet.erase(toDelete);

  std::cout << "Courses after deletion:" << std::endl;
  for (auto& c : courseSet) {
    std::cout << "  - " << c.getId() << std::endl;
  }
}

Output

1
2
3
3
Course exists, id: 1
Course exists, id: 2
Currently available courses:
    - 1
    - 2
    - 3
Courses after deletion:
    - 1
    - 2

Explanation of the example

std::set<Course> courseSet; We must instantiate the set class. The type to be stored is specified within <>.

courseSet.insert(c1); Insert an element. Only the specified type can be inserted.

courseSet.size() Returns the number of elements in the set.

courseSet.insert( c12 ); Although we're calling insert, size doesn't increase since the element already exists.

courses.contains( course ); Starting from C++20, we can use contains() to check if an element exists. Returns bool, which is true if the element is contained, false otherwise.

courses.find( course ) != courses.end(); Before C++20, the find method was used. It does not return a boolean value, but instead returns an element indicating the position of the searched item within the set (an iterator). If the element is found, we get a valid iterator; if not, we get an iterator that points to the end of the set. This end element can be accessed using the end method. So, by using the find method, we get the position of the element, and if it is not the end element, then the item is present in the set.

for( Course k : courseSet ) You can iterate over the elements of a set using iterators with the begin() and end() methods to access the first and last positions.
However, for containers that support iterators, there's a simpler syntax for traversal — a range-based for loop, as shown below.
This allows you to iterate through all elements of the set with less boilerplate code.

for (Kurzus k : kurzusHalmaz) {
    // use k
}

In this case, each iteration provides a copy of the stored element. If you want to avoid copying and work with the original object instead, you can use a reference:

for (Kurzus& k : kurzusHalmaz) {
    // reference to the stored element
}

for (auto& k : kurzusHalmaz)

This implementation is very similar to the previous one, but here we don't need to explicitly specify the type. By using auto, the compiler automatically infers the correct type of the elements in the set. This makes the code shorter and cleaner, especially when working with complex or templated types.

kurzusHalmaz.erase( torlendo );

You can perform the deletion using the erase method.

Vector (std::vector)

A vector is suitable for storing multiple elements in a given order. An element may appear more than once.

To use it, you need to include the vector header.

class Course {
public: 
  int id;
};

int main() {
  std::vector<Course> courses;
  Course c1 { 1 };
  Course c2 { 2 };

  courses.push_back( c1 );
  courses.push_back( c2 );
  courses.push_back( c1 );
  std::cout << courses.size() << std::endl;

  std::cout << "The ID of the course at index one: " << courses[ 1 ].id << std::endl;

  std::cout << "Courses:" << std::endl;
  for ( auto course : courses ) {
    std::cout << "  - " << course.id << std::endl;
  }

  for ( auto& course : courses ) {
    course.id = 42;
  }

  std::cout << courses.at( 0 ).id << std::endl;
}

Output

3
The ID of the course at index one: 2
Courses:
  - 1
  - 2
  - 1
42

Explanation of the Example

std::vector<Course> courses; A vector is a class, so it needs to be instantiated, and here you also have to specify what type of elements you want to store.

courses.push_back( c1 ); Adds the given element to the end of the vector. There are multiple insertion options, but inserting at the end of the vector can be done in constant time.

courses[ 1 ].id Just like with regular arrays, you can access elements by their index.

courses.at( 0 ).id This call also accesses elements by index, but the given index is validated. If the index is invalid, a std::out_of_range exception is thrown.

for ( auto& course : courses ) Similar to sets, you can access elements in a for-loop. You can use either copies or references, but here note that you don’t have to use const—the original elements can be modified!

Map (std::map)

A map is suitable for storing key-value pairs. Every key must be unique!

Example:

#include <iostream>
#include <map>
#include <string>

struct Course {
  std::string name;
  Course(const std::string& name) : name(name) {}
  Course() = default;
  bool operator<(const Course c) const { return name.length() < c.name.length(); }
};

int main() {
  std::map<std::string, Course> instructors_courses;
  Course native_programming{ "native_programming" };
  Course prog1{ "prog1" };
  std::string native_programming_instructor = "C++ instructor";
  std::string prog1_instructor = "Java instructor";

  instructors_courses[native_programming_instructor] = native_programming;
  instructors_courses[prog1_instructor] = prog1;

  std::cout << native_programming_instructor << "'s course: " 
            << instructors_courses.at(native_programming_instructor).name << std::endl;
  std::cout << prog1_instructor << "'s course: " 
            << instructors_courses[prog1_instructor].name << std::endl;

  Course prog3{ "prog3" };
  std::string prog3_instructor = "Carbon instructor";

  if (instructors_courses.find(prog1_instructor) != instructors_courses.end()) {
    std::cout << prog1_instructor << " has a course, namely: " 
              << instructors_courses.at(prog1_instructor).name 
              << std::endl;
  }

  for (auto& element : instructors_courses) {
    std::cout << "Instructor: " << element.first
              << " Course: " << element.second.name 
              << std::endl;
  }

  // Since C++17 this can be used
  for (auto& [instructor, course] : instructors_courses) {
    std::cout << "Instructor: " << instructor
              << " Course: " << course.name 
              << std::endl;
  }
}

Output

C++ instructor's course: native_programming
Java instructor's course: prog1
Java instructor has a course, namely: prog1
Instructor: C++ instructor Course: native_programming
Instructor: Java instructor Course: prog1
Instructor: C++ instructor Course: native_programming
Instructor: Java instructor Course: prog1

Explanation of the Example

std::map<std::string, Course> instructors_courses; A map is a class, so it also needs to be instantiated, but this time we need to specify two extra types: the first is the type of the keys, and the second is the type of the stored values.
The key type elements must have a sorting relation. For primitive types, this is naturally given; for custom types, we need to provide this ourselves.

instructors_courses[native_programming_instructor] = native_programming; The indexing operator allows us to assign a value to a given key.
Important: if the key did not exist before, a new element is inserted.
It is also suitable for updating the stored value for a key.
When inserting a new value, the default constructor is required!

instructors_courses[prog1_instructor].name The indexing operator is not only for insertion/update, but can also be used for querying.
Be careful with this, because if you query a key that does not exist, a value constructed by the default constructor will be inserted for the new key!

instructors_courses.at(native_programming_instructor).name A safer way to query. This does not insert a new value, but may throw an exception.
Before calling this, it is advisable to check if the element exists or be prepared to handle an exception in case it does not!

instructors_courses.find(prog1_instructor) != instructors_courses.end() Similarly to sets, the find method returns an iterator, and an element is found if the iterator is NOT the end iterator of the map.

for (auto& element : instructors_courses) Elements in a map are also iterable, but in this case, we get two values because we are dealing with key-value pairs.
The received element is a pair, which has first and second members. An example of this is found in the following explanation.

element.first and element.second.name The object obtained during iteration is a pair where the first member contains the KEY stored in the map.
The second attribute contains the VALUE.

for (auto& [instructor, course] : instructors_courses) Since C++17, we can simplify the previous iteration. We do not need to use the pair's first and second members explicitly; instead, we can bind the key and value to separate variables automatically.
In this case, the current KEY is assigned to the instructor object and the VALUE is assigned to the course object.

Iterators

In the examples above, we saw several cases where we used a for loop to traverse containers. These traversals ensure that every element is visited. Behind the scenes, iterators are used.

Iterator: An object that allows us to walk through the elements of a container. Depending on the type of iterator, it may support moving forward, backward, and jumping to arbitrary elements. The iterator itself does not represent the individual elements, only points to a given element.
To access the actual value, the iterator must be dereferenced, which for us means putting a * before the iterator’s name to get the value it refers to!

When using iterators, some special elements are distinguished. These include the first and last elements during traversal. In a typical iteration, the iterator representing the first element is obtained by the begin method, and the iterator representing the end of the container is obtained by the end method.

#include <iostream>
#include <vector>
int main() {
  std::vector<int> v_int = { 1, 4, -8, 33 };
  std::cout << *v_int.begin() << std::endl; // After dereferencing, we print the value.
  *v_int.begin() = 77; // Using iterators, we can also modify values in some containers. See cppreference for details.
  for (int value : v_int) {
    std::cout << value << std::endl;
  }
}

Output

1
77
4
-8
33

When iterating with iterators, a variable must be created to access the elements.
The type of this variable depends on the container used and the type of elements stored in it.
Different containers’ iterators may allow different operations, but in most cases, the ++ operator can be used.
With its help, we get an iterator referring to the next element.

#include <iostream>
#include <vector>
int main() {
  std::vector<int> v_int = { 1, 4, -8, 33 };
  std::vector<int>::iterator it; // this is the type of the iterator
  for (it = v_int.begin(); it != v_int.end(); ++it) { 
    // we iterate until the iterator equals the container’s end iterator
    std::cout << *it << std::endl; // the iterator must be dereferenced
  }

  auto it2 = v_int.begin(); // when declaring iterator type, auto can be used to shorten the code
}

Output

1
4
-8
33

---

Last update: 2025-09-04
Created: 2025-09-04