Associative Containers

Question 1

Write a program to count words

Answer 1

map word_count; // empty map from string to size_t
string word;
while (cin&raquo_space; word)
++word_count[word];
for (const auto &w : word_count)
cout &laquo_space;w.first &laquo_space;” occurs “ &laquo_space;w.second &laquo_space;((w.second > 1) ? “ times” : “ time”) &laquo_space;endl;

Question 2

How to use a custom compatrator

Answer 2

bool compareIsbn(const Sales_data &lhs, const Sales_data&rhs)
{	return lhs.isbn() < rhs.isbn();	}

multiset bookstore(compareIsbn);

When we use decltype to form a function pointer, we must add a * to indicate that we’re using a pointer to the given function type. We can write compareIsbn instead of &compareIsbn as the constructor argument because when we use the name of a function, it is automatically converted into a pointer if needed. We could have written &compareIsbn with the same effect

Question 3

Various _type in set/ map

Answer 3

key_type Type of the key for this container type
mapped_type Type associated with each key; map types only
value_type For sets, same as the key_type
For maps, pa i to cons t key_type, mapped_type>

examples :-

set: :value_type v1; // v1 is a string
set: :key_type v2; // v2 is a string
map: :value_type v3; // v3 is a pair
map: :key_type v4; // v4 is a string
map: :mapped_type v5; // v5 is an int

Question 4

Is there s difference in const-ness of iterator and const_iterator in a set

Answer 4

No, both are const

Question 5

What are associative set insert operations

Answer 5

c. insert (v) v value_type object args are used to construct an element.

c emplace large) For map and set, the element is inserted (or constructed) only if an element with the given key is not already in c. Returns a pair con-taining an iterator referring to the element with the given key and a bool indicating whether the element was inserted. For multimap and multiset, inserts (or constructs) the given ele-ment and returns an iterator to the new element.

c . insert (b , e) b and e are iterators that denote a range of c :value_type values;
c . insert(il) il is a braced list of such values. Returns void. For map and set, inserts the elements with keys that are not already in c. For multimap and multiset inserts, each element in the range.

c . insert (p, v) Like insert (v) (or emplace (args)), but uses iterator p as a hint

c emplace (p, args) for where to begin the search for where the new element should be stored. Returns an iterator to the element with the given key.

Question 6

What are associate set erase functions

Answer 6

c . erase ( k ) Removes every element with key k from c. Returns i ze_type indicating the number of elementn removed.

c . erase (p) Removes the element denoted by the iterator p from c. p most refer to an actual element in c; it must not be equal to c . end ( ) . Returns an iterator to the element after p or c . end ( ) if p denotes the last element in c.

c . erase (b , e) Removes the elements in the range denoted by the iterator pair b, e. Retums e.

Question 7

3 ways to iterate through all the elements with same key in a multimap

Answer 7

// 1
// definitions of authors and search_item as above
// beg and end denote the range of elements for this author
for (auto beg = authors.lower_bound(search_item),
		end = authors.upper_bound(search_item);
		beg != end; ++beg)
	cout << beg->second << endl; // print each title

// 2
string search_item("Alain de Botton"); // author we'll look for
auto entries = authors.count(search_item); // number of elements
auto iter = authors.find(search_item); // first entry for this author
// loop through the number of entries there are for this author
while(entries) {
	cout << iter->second << endl; // print each title
	\++iter; // advance to the next title
	--entries; // keep track of how many we've printed
}

// 3
// definitions of authors and search_item as above
// pos holds iterators that denote the range of elements for this key
for (auto pos = authors.equal_range(search_item);
		pos.first != pos.second; ++pos.first)
	cout << pos.first->second << endl; // print each title

Question 8

How do unordered associative container(s) manage buckets

Answer 8

To access an element, the container first computes the element’s hash code, which tells which bucket to search. The container puts all of its elements with a given hash value into the same bucket. If the container allows multiple elements with a given key, all the elements with the same key will be in the same bucket. As a result, the performance of an unordered container depends on the quality of its hash function and on the number and size of its buckets.

Ideally, the hash function also maps each particular value to a unique bucket. However, a hash unction is allowed to map elements with differing keys to the same bucket.