Basic Concepts
1. map and set are associative containers, unlike sequence containers such as vector, queue, and stack. The structure of associative containers makes data retrieval more efficient.
2. map and set follow a <key, value> structure.
Key-Value Pairs
SGI_STL implementation of key-value pairs
Through class template parameters, different types of data can be mapped one-to-one:
namespace cpp_utils {
template<class class="" k="" v="">
struct pair {
typedef K key_type;
typedef V value_type;
K key;
V value;
pair()
: key(K())
, value(V())
{}
pair(const K& a, const V& b)
: key(a)
, value(b)
{}
};
}</class>
Underlying Structure of set and map (Balanced Search Trees or Red-Black Trees)
1. In special cases, our binary search tree can become a single-branch structure.
2. The search time complexity decreases significantly, changing from height-based to count-based complexity.
3. Balenced search trees or red-black trees perform data balancing when there's a possibility of single-branch formation, ensuring tree balance.
set
set (Sorted + Unique)
Template Parameters
set as an Ordered Container
1. Use insert for data insertion.
2. Traverse data using iterators.
3. set's default comparison method is ascending order.
4. Data in set cennot be modified arbitrarily to maintain order.
Uniqueness in set
1. Duplicate data cannot be stored in set.
2. Each data element in set is unique.
Special Structure of set
1. set doesn't have a << key value>> structure — actually it's << value value>>
2. When inserting data, set actually inserts both values of the underlying pair, but at the upper level, we only need to insert one data element without considering the pair.
Using find and erase
Case 1
1. Pass the data value, returns an iterator to the same data. If the data doesn't exist, returns the iterator after the last element.
2.配合使用 erase's first overload:
3. Disadvantage: The data to be deleted must exist, otherwise an error will occur.
Case 2
1. Can directly pass the value of the data to be deleted to erase.
2. Case 1: Delete if exists.
3. Case 2: Do not delete if doesn't exist, no out-of-bounds issues.
Case 3: Range deletion
1. set's erase for range deletion requires a left-closed, right-open range.
2. find's usage doesn't fully satisfy this condition?
3. find's search criterion is whether the parameter value exists in set!
4. Obviously, find's search range is unreliable, so set provides two methods.
5. lower_bound and upper_bound
count Returns Element Count
1. Because set has the special structure (sorted + unique), count can only return 0 or 1.
multiset (Sorted + Allows Duplicates)
Differences between set and multiset
1. Allows key value redundancy.
2. Data insertion is relatively free but considers balance.
3. find returns the iterator of the first identical data in in-order when multiple exist.
4. Data in multiset cannot be modified arbitrarily to maintain order.
Usefulness of count
1. Count duplicate data elements:
map
map (Sorted + Unique)
Basic Concepts
1. map is an associative container that stores a pair class internally.
2. For pair, the two object types of < key value> may be different.
Data Insertion and Multiple Initialization Methods
1. Construct object then pass parameters
2. Use make_pair
3. Implicit type conversion provided by multi-parameter constructor.
Search and Deletion
1. An iterator to the element, if an element with specified key is found, or map::end otherwise. — Pass the data value, returns an iterator to the same data. If the data doesn't exist, returns the iterator after the last element.
1. These contents are the same as in set, but note that we always consider through the key value, the value doesn't participate.
count
1. Since duplicate key data is not allowed, count in map is also 0 or 1.
Preventing Duplicate Key Insertion
Testing:
Data Statistics
Method 1: find + insert:
void analyze_fruit_counts()
{
map<string int=""> fruitMap;
const char* fruits[] = { "grape","watermelon","apple","banana","strawberry","grape",
"watermelon","watermelon","apple","banana","strawberry" "grape","watermelon","apple","banana",
"strawberry","strawberry","watermelon","watermelon","grape","grape","banana","banana","apple" };
//1. Simple data statistics:
for (int i = 0; i < sizeof(fruits) / sizeof(fruits[0]); i++)
{
auto searchResult = fruitMap.find(fruits[i]);
//1. First insertion:
if (searchResult == fruitMap.end())
{
fruitMap.insert(make_pair(fruits[i], 1));
}
//2. Not first insertion:
else
{
(searchResult->second)++;
}
}
map<string int="">::iterator it = fruitMap.begin();
while (it != fruitMap.end())
{
cout << it->first << ":" << it->second << endl;
it++;
}
cout << endl;
}</string></string>
Method 2: insert returns pair type:
void analyze_fruit_counts_v2()
{
map<string int=""> fruitMap;
const char* fruits[] = { "grape","watermelon","apple","banana","strawberry","grape",
"watermelon","watermelon","apple","banana","strawberry" "grape","watermelon","apple","banana",
"strawberry","strawberry","watermelon","watermelon","grape","grape","banana","banana","apple" };
//1. Simple data statistics:
for (int i = 0; i < sizeof(fruits) / sizeof(fruits[0]); i++)
{
//1. bool is true means current insertion value doesn't exist:
pair<map int="">::iterator,bool> insertionResult = fruitMap.insert(make_pair(fruits[i], 1));
//2. bool is false means current insertion value already exists:
if (!insertionResult.second)
{
(insertionResult.first->second)++;
}
}
map<string int="">::iterator it = fruitMap.begin();
while (it != fruitMap.end())
{
cout << it->first << ":" << it->second << endl;
it++;
}
cout << endl;
}</string></map></string>
operator[] Overload (Optimized Data Statistics)
void analyze_fruit_counts_v3()
{
map<string int=""> fruitMap;
const char* fruits[] = { "grape","watermelon","apple","banana","strawberry","grape",
"watermelon","watermelon","apple","banana","strawberry" "grape","watermelon","apple","banana",
"strawberry","strawberry","watermelon","watermelon","grape","grape","banana","banana","apple" };
//1. Simple data statistics:
for (int i = 0; i < sizeof(fruits) / sizeof(fruits[0]); i++)
{
fruitMap[fruits[i]]++;
}
map<string int="">::iterator it = fruitMap.begin();
while (it != fruitMap.end())
{
cout << it->first << ":" << it->second << endl;
it++;
}
cout << endl;
}</string></string>
multimap (Sorted + Allows Duplicate Keys)
Differences between map and multimap
1. multimap is not suitable for data statistics but can store keys of the same type.