Master the basics
The blog is about learning the commonly used data structures: Vector, Set, and Map. In my last blog, we discussed STL.
The structure of the blog: definition, syntax, some functions, when to use it, and examples.
Let’s begin with Vector:
{ } Vector
Definition: Vectors in C++ are sequence containers representing dynamic arrays. Vectors provide more flexibility to the program as they can adjust their size automatically when an element is inserted or deleted from it.
Syntax: vector <type> variable (elements)
For example: vector <int> rooms (9);
Let’s break it down:
- type defines a data type of elements stored in a vector (e.g., <int>, <double> or <string>)
- variable is a name that you choose for the data
- elements specify the number of elements for the data and is optional
It is mandatory to determine the type and variable name.
Functions:
1. assign() — It assigns a new value to the existing elements of the vector.
2. push_back() — It pushes the element from back in the vector.
3. pop_back() — It removes elements from the back of the vector.
4. insert() — It inserts an element before a specified element in the vector.
5. erase() — It is used to remove elements from a specified element or a range in the vector.
6. swap() — It is used to swap the contents of two vectors of the same datatype. The sizes of vectors may differ.
7. clear() — It is used to remove all the elements from the vector.
When to use it?
The scenario that involves:
- Constantly changing container: The vectors are preferred when dynamic data is involved where we often add or remove data
- No prior knowledge of the maximum size of container: When we don’t know the size of data beforehand or when the data is not established in advance. The size keeps on changing
Example:
{ } Set
Sets are associative containers that store unique elements following a specific order.
Properties:
- Uniqueness — All elements inside a C++ Set are unique
- Sorted — The elements inside a Set are always in a sorted manner
- Immutable — Any element inside the Set cannot be changed. It can only be inserted or deleted
- Unindexed — The STL Set does not support indexing
- Internal Implementation — The Sets in STL are internally implemented by BSTs (Binary Search Trees)
Syntax: set <type> variable {elements}
For example: set <int> words {6, 10, 5, 1};
Let’s break it down:
- type defines a data type of elements stored in a vector (e.g., <int>, <double> or <string>)
- variable is a name that you choose for the data
- elements specify the elements(literal values) for the data and is optional
It is mandatory to determine the type and variable name.
Functions:
The commonly used functions are:
1. begin( ): used to return an iterator pointing to the first element of the set container.
2. end( ): it returns an iterator pointing to past the last element of the set container
3. size( ): used to return the size of the set container or the number of elements in the set container
4. empty( ): used to check if the set container is empty or not
5. insert(x): inserts a new element in the set container
6. erase( ): used to remove elements from a container from the specified position or range
7. find( x ): it returns an iterator based on the position of the element if it is found, else return iterator at the end
When to use it?
Sets are frequently used containers in competitive programming; whenever there is a need of storing the elements in a sorted manner, we can think of using the sets, but remember that the set does not allow us to store the duplicate values. The value can’t be modified once it is stored.
Example:
{ } Map
Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have same key values.
Syntax: map<key_type , value_type> map_name;
- The key_type denotes the datatype of the map keys
- The value_type denotes the datatype of the values corresponding to the map keys
- The map_name is the name of the map.
For example: map<string, int> my_map;
We declared a map named my_map. The map will have a string as key datatypes and integer as values datatype.
Properties:
- map only stores unique keys, and the keys themselves are in sorted order
- There is only one value for every key
Functions:
Some basic functions associated with Map:
1. begin(): it returns an iterator to the first element in the map
2. end(): it returns an iterator to the theoretical element that follows last element in the map
3. size(): it returns the number of elements in the map
4. max_size(): it returns the maximum number of elements that the map can hold
5. empty(): it returns whether the map is empty
6. pair insert(keyvalue, mapvalue): adds a new element to the map
7. erase(iterator position): Removes the element at the position pointed by the iterator
8. erase(const g): Removes the key-value ‘g’ from the map
9. clear(): Removes all the elements from the map
When to use it?
Whenever we come across the data that is in the form of key-value pair and we require to perform more search operations on it then it is best to consider the maps. Consider maps when there are constant lookups by key, you search if key/value exists and remove duplicates.
Example:
{ } General Rules of Thumb
There are some general rules of thumb that will guide you through most situations given by Phillip Johnston
- Use sequential containers when you need to access elements by position
- Use std:vector as your default sequential container, especially as an alternative to built-in arrays
- If the size is known in advance, use std::array instead of a built-in array
- If you add or remove elements frequently at both the front and back of a container, use std::deque
- Use a std::list (not std::deque) if you need to insert/remove elements in the middle of the sequence
- Do not use std::list if you need random access to objects
- Prefer std::vector over std::list if your system uses a cache
- std::string is almost always better than a C-string
- Use associative containers when you need to access elements by key
- For key/value pair, default to std::unordered_map, or if element order matters, std::map
- If you need multiple entries for the same key, use std::unordered_multimap, or if element order matters, std::multimap
Memory allocation may also be a factor in your decision. Here are the general rules of thumb for how the different sequential containers are storing memory:
- std:vector, std::array, and std::string store memory contiguously and are compatible with C-style APIs
- std::deque allocates memory in chunks
- std::list allocates memory by node
{ } Conclusion
And there you have it — you now know the basics of vectors, sets and maps in C++. To go on with STL, I would like you to try programs on various websites on coding. This will help you understand the concepts more clearly and improve your coding skills. The more programs you practice the more you get when and why to use C++ STL.
Thanks! Signing off!
Megha B. Halasangimath
