Skip to content

Latest commit

 

History

History
386 lines (268 loc) · 9.5 KB

maps.md

File metadata and controls

386 lines (268 loc) · 9.5 KB

Map

Introduction:

A map is a datastructure to store a key value pair.

Import:

#include <map>

Properties:

  1. It is a datastructure which stores a key value pair.

  2. Elements are referenced using their keys not by position(unlike arrays).

  3. The elements are stored in orders(i.e. they are pre-sorted).

  4. Internal implementation is like a binary search tree.

  5. Size is increased and decreased automatically, according to storage needs.

  6. Keys are unique. Same key cannot be used to store more than 1 values.

Usage:

1. Initialize

Template has two data types first for key and second for value. User defined comparator can be added as third parameter.

2. Constructors

1. Default:

Makes an empty container.
```cpp map var_name; //Starts the var_name map with no key value pairs ```

2. Range:

Used to copy range of elements from one map to other. 
map<Type1, Type2> var_name1;
//fill 10 elements in var_name
//If want to copy elements from 0-10
map<Type1, Type2>  var_name2(var_name1.begin(),var_name1.end());

Note: The template types should be same.

3. Copy:

Copy entire container in new map object.
map<Type1, Type2> var_name(map_object);

Copies the map_object in var_name. The map_object should be of same type.

3. Insert

1. Insert using key and value directly, using array-like syntax.

map<char, int> map_object;
map_object['a'] = 10;
Note:
This method overwrites the previous value (if any).

2. Insert using insert()

map_object.insert(make_pair<char, int>('b', 20));
Note:
This method does not overwrite the previous value (if any) but returns an object pointing to the previous value and new value is not inserted.

3. Returned object of insert()

The return_object is a pair, first is an iterator to inserted element(or the same key element if insertion was prevented) and second is a boolean object which is true if insert happened and is false if it was stopped. 

#include<maps>
map<char,int> mymap;
mymap.insert ( pair<char,int>('a',100) );
mymap.insert ( pair<char,int>('z',200) );

pair<std::map<char,int>::iterator,bool> ret;
ret = mymap.insert (pair<char,int>('z',500) );
if (ret.second==false) {
	cout << "element 'z' already existed";
	cout << " with a value of " << ret.first->second << '\n';
}

4. Access

1. Access using key directly

cout << mymap['b'];

2. Access using at()

cout << mymap.at('b');

3. Access using find()

cout << mymap.find('b')->second;
cout << (*mymap.find('b')).second;
Note:
This method returns an iterator to the elements.

5. Delete

1. erase()

mymap.erase('b');
it = mymap.find('a');
mymap.erase(it, mymap.end());

6. Iteration

1. Begin()

Returns an iterator to first element in the map.

2. End()

Returns an iterator to the end of map (Not the last element). 
map<char,int> mymap;

mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;
for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); it++)
	std::cout << it->first << " => " << it->second << '\n';
return 0;

Complexities

Insert: O(log(n))

Access: O(log(n))

Delete: O(1) + Access = O(log(n))

Unordered Map

Introduction:

An unordered map is a datastructure to store a key value pair and access it fast enough.

Import:

#include <unordered_map>

Properties:

  1. It is a datastructure which stores a key value pair.

  2. Elements are referenced using their keys not by position(unlike arrays).

  3. The elements are not sorted.

  4. Internal implementation is using hashing.

  5. Size is increased and decreased automatically, according to storage needs.

  6. Keys are unique. Same key cannot be used to store more than 1 values.

  7. Introduced in C++11.

Usage

1. Initialize

Template has two data types first for key and second for value.

2. Constructors

1. Default:

Makes an empty container. 
unordered_map<Type1, Type2> var_name; //Starts the var_name map with no key value pairs

2. Range:

Used to copy range of elements from one map to other. 
unordered_map<Type1, Type2> var_name1;
//fill 10 elements in var_name
//If want to copy elements from 0-10
unordered_map<Type1, Type2>  var_name2(var_name1.begin(),var_name1.end());

Note: The template types should be same.

3. Copy:

Copy entire container in new map object.
unordered_map<Type1, Type2> var_name(map_object);

Copies the map_object in var_name. The map_object should be of same type.

4. List:

Initialize a list as a key value pair.

3. Insert

1. Insert using key and value directly, using array-like syntax.

unordered_map<char, int> map_object;
map_object['a'] = 10;
Note:
This method overwrites the previous value (if any).

2. Insert using insert()

map_object.insert(make_pair<char, int>('b', 20));
Note:
This method does not overwrite the previous value (if any) but returns an object pointing to the previous value and new value is not inserted.

3. Returned object of insert()

The return_object is a pair, first is an iterator to inserted element(or the same key element if insertion was prevented) and second is a boolean object which is true if insert happened and is false if it was stopped.

unordered_map<char,int> mymap;
mymap.insert ( pair<char,int>('a',100) );
mymap.insert ( pair<char,int>('z',200) );

pair<std::map<char,int>::iterator,bool> ret;
ret = mymap.insert (pair<char,int>('z',500) );
if (ret.second==false) {
	cout << "element 'z' already existed";
	cout << " with a value of " << ret.first->second << '\n';
}

4. Access

1. Access using key directly

cout << mymap['b'];

2. Access using at()

cout << mymap.at('b');

3. Access using find()

cout << mymap.find('b')->second;
cout << (*mymap.find('b')).second;
Note:
This method returns an iterator to the elements.

5. Delete

1. erase()

mymap.erase('b');
it = mymap.find('a');
mymap.erase(it, mymap.end());

6. Iteration

1. Begin()

Returns an iterator to first element in the map.

2. End()

Returns an iterator to the end of map (Not the last element). 
unordered_map<char,int> mymap;

mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;
for (unordered_map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); it++)
	cout << it->first << " => " << it->second << '\n';
return 0;

Complexities

Insert (Average Case): O(1)

Insert (Worst Case): O(n)

Access: O(1)

Delete (Average Case): O(1)

Delete (Worst Case): O(n)

Multimap

Introduction:

A Multimap is a datastructure to store a key value pair having multiple keys.

Import: 

#include <map>

Properites:

Same as maps but only it can have multiple values for a key.

Usage:

1. Initialize

Template has two data types first for key and second for value. User defined comparator can be added as third parameter.

2. Constructors

1. Default:

Makes an empty container. 
multimap<Type1, Type2> var_name; //Starts the var_name map with no key value pairs

2. Range:

Used to copy range of elements from one map to other. 
multimap<Type1, Type2> var_name1;
//fill 10 elements in var_name
//If want to copy elements from 0-10
multimap<Type1, Type2>  var_name2(var_name1.begin(),var_name1.end());

Note: The template types should be same.

3. Copy:

Copy entire container in new map object.
multimap<Type1, Type2> var_name(map_object);

Copies the map_object in var_name. The map_object should be of same type.

3. Insert

1. Insert using insert()

This method inserts an element with the key and value provided. Use this link because it is very similar to maps and unordered_maps.

4. Access

1. Access using find()

Returns an iterator to an arbitrary element of possibly multiple elements having the given key.
Example

2. Access using equal_range()

Returns a pair of iterators. First is an iterator to the first element having the given key. Second is the iterator to the next to last element having the key.
Example

5. Delete

1. erase()

Deletes an element using its iterator. Same as maps and unordered_maps.
Example

6: Iteration

Same as maps and unordered_maps.
Example

Complexities

Insert: O(log(n))

Access: O(log(n))

Delete: O(1) + Access = O(log(n))