[C++] C++ 11/14/17/... New STL (ENG)

 

Unordered Map

std::unordered_map
std::unordered_multimap

 

// std::map
#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<std::string, int> scores;

    scores["Nana"] = 60;
    scores["Mocha"] = 70;
    scores["Coco"] = 100;

    for (auto it = scores.begin(); it != scores.end(); ++it)
    {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}

// Coco: 100
// Mocha: 70
// Nana: 60

 

std::map is a map that orders elements automatically. So frequent insertion and deletion of elements degrades performance. It is based on binary search tree. Use std::unordered_map.

 

// std::unordered_map
#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string, int> scores;

    scores["Nana"] = 60;
    scores["Mocha"] = 70;
    scores["Coco"] = 100;

    for (auto it = scores.begin(); it != scores.end(); ++it)
    {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}

// Coco: 100
// Nana: 60
// Mocha: 70

 

std::unordered_map (a.k.a hashmap) stores pairs of keys and values. It is not based on BST, but on hash table. Keys cannot be duplicated. It doesn't sort the elements. The elements consist of index-based backets that the hash function creates. Its time complexity is O(1). It need more memory because of the buckets.

auto found = scores.find("Coco");

 

You can use arrays, vectors, or linked lists to prevent hash collisions (that is, two or more values in a bucket with different keys having the same value). Arrays have a fixed capacity, and vectors or lists don't make values collide.

 

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string, int> scores;

    scores["Nana"] = 60;
    scores["Mocha"] = 70;
    scores["Coco"] = 100;
    scores["Ari"] = 40;
    scores["Chris"] = 90;

    for (size_t i = 0; i < scores.bucket_count(); ++i)
    {
        std::cout << "Bucket #" << i << ": ";
        for (auto it = scores.begin(i); it != socres.end(i); ++it)
        {
            std::cout << " " << it->first << ":" << it->second;
        }
        std::cout << std::endl;
    }

    return 0;
}

// Bucket #0:
// Bucket #1: Ari:40 Coco:100 Nana:60
// Bucket #2:
// Bucket #3:
// Bucket #4: Chris:90
// Bucket #5: Mocha:70
// Bucket #6:
// Bucket #7:

 

It is good to set bucket size enough, and as many as prime numbers.

 

 

 

Unordered Set

The same concepts of unordered_map.

 

 

 

Speed Testing

auto start = chrono::high_resolution_clock::now();
orderedSet.insert (NUMBER_TO_INSERT_LATER);
auto end = chrono::high_resolution_clock::now();
auto elapsedNanoSeconds = end - start;
cout << "Inserting into orderedSet: " << elapsedNanoSeconds.count() << " ns" <<endl;

 

 

 

Array

This array is not an array that we know. It is a kind of container. It is similar to FixedVector (template class). It doesn't remember the number of elements, size. It works like a C-style array.

std::array <int, 3> numbers;
numbers[0] = 1;  // it means that it already got the value
// numbers.size() == 3
// numbers.max_size() == 3

 

Array are not be used so much. I'm wondering why it is needed. (Maybe for std::algorithm?)

 

 

 

Range-Based for

// previously 1
int scores[3] = { 10, 20, 30};

for (int i = 0; i < 3; ++i)
{
    std::cout << scores[i] << " " << std::endl;
}

 

// range-based for 1
int scores[3] = { 10, 20, 30};

for (int score : scores)
{
    std::cout << score << " " << std::endl;
}

 

// previously 2
std::map<std::string, int> scoreMap;

scoreMap["Lulu"] = 10;
scoreMap["Coco"] = 50;
scoreMap["Mocha"] = 100;

for (auto it = scoreMap.begin(); it != scoreMap.end(); ++it)
{
    std::cout << it->first << ": " << it->second << std::endl;
}

 

// range-based for 2
std::map<std::string, int> scoreMap;

scoreMap["Lulu"] = 10;
scoreMap["Coco"] = 50;
scoreMap["Mocha"] = 100;

for (auto& score: scoreMap)
{
    std::cout << score.first << ": " << score.second << std::endl;
}

 

As you can see above, it is quite similar with the one of python. Range-based for 1, the members of scores are copied as values to score. Range-based for 2, the members of scoreMap are copied as references to score.

 

Range-based for is simple, and has good readability. It can be used for STL containers and also for C-style arrays. You can use auto with it. You can't reverse though. It is supported as an algorithm, not as the syntax.

 

What about for_each( ) of STL algorithms?

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string, int> scores;

    scores["Lulu"] = 70;
    scores["Chris"] = 50;
    scores["Monica"] = 100;

    // lambda function - study later
    auto printElement = [](std::unordered_map<std::string, int>::value_type& item)
    {
        std::cout << item.first << ": " << item.second << std::endl;
    };

    for_each(scores.begin(), scores.end(), printElement);

    return 0;
}

 

for_each( ) is available after C++03. It runs the function to each element. Use range-based for instead of this.

 

// {["Lulu", 10], ["Chris", 50], ["Monica", 100]}
std::map<std::string, int> scoreMap;

for (auto score : scoreMap)
{
    score.second -= 10;
    std::cout << score.first << ": " << score.second << std::endl;
}

for (auto& score : scoreMap)
{
    std::cout << score.first << ": " << score.second << std::endl;
}

for (const auto& score : scoreMap)
{
    std::cout << score.first << ": " << score.second << std::endl;
}

// By value
// Chris: 40
// Lulu: 0
// Monica: 90

// By reference
// Chris: 50
// Lulu: 10
// Monica: 100

// By const reference
// Chris: 50
// Lulu: 10
// Monica: 100

 

Use const, and reference.