Expression: cannot dereference value-initialized map/set iterator (Debug Assertion Failed!)-CodePudding

The simple code:

#include <iostream>
#include <random>
#include <string>
#include <map>

std::map<int, uint64_t> mp;

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distr(1, 9);

//std::mutex _mutex;
//std::shared_timed_mutex _mutex;
std::shared_mutex _mutex;

void t1()
{
    int key = 0;
    uint64_t i;
    while (1)
    {
          key;
        if (key < 1000)
        {
            std::map<int, uint64_t>::iterator it_mp = mp.find(key);
            if (it_mp != mp.end())
            {
                i = distr(gen);
                std::cout << "UPDATE\t1\t" << it_mp->first << "\t" << it_mp->second << "\t->\t" << i << "\n";
                it_mp->second = i;
            }
            else
            {
                std::unique_lock guard(_mutex);

                i = distr(gen);
                std::cout << "INSERT\t1\t" << key << "\t->\t" << i << "\n";
                mp.insert({ key, i });
            }
        }
        else
        {
            i = distr(gen);
            std::map<int, uint64_t>::iterator it_mp = mp.begin();
            while (it_mp != mp.end())
            {
                if (it_mp->second == i)
                {
                    std::unique_lock guard(_mutex);

                    std::cout << "ERASE\t1\t" << it_mp->first << "\t<-\t" << i << "\n";
                    it_mp = mp.erase(it_mp);
                }
                else
                {
                      it_mp;
                }
            }

            key = 0;
        }
    }
}

void t2()
{
    int key = 0;
    uint64_t i;
    while (1)
    {
          key;
        if (key < 1000)
        {
            std::map<int, uint64_t>::iterator it_mp = mp.find(key);
            if (it_mp != mp.end())
            {
                i = distr(gen);
                std::cout << "UPDATE\t2\t" << it_mp->first << "\t" << it_mp->second << "\t->\t" << i << "\n";
                it_mp->second = i;
            }
            else
            {
                std::unique_lock guard(_mutex);

                i = distr(gen);
                std::cout << "INSERT\t2\t" << key << "\t->\t" << i << "\n";
                mp.insert({ key, i });
            }
        }
        else
        {
            i = distr(gen);
            std::map<int, uint64_t>::iterator it_mp = mp.begin();
            while (it_mp != mp.end())
            {
                if (it_mp->second == i)
                {
                    std::unique_lock guard(_mutex);

                    std::cout << "ERASE\t2\t" << it_mp->first << "\t<-\t" << i << "\n";
                    it_mp = mp.erase(it_mp);
                }
                else
                {
                      it_mp;
                }
            }

            key = 0;
        }
    }
}

int main()
{
    std::thread _t1(t1);
    _t1.detach();

    std::thread _t2(t2);
    _t2.join();
    
    return 0;
}

An exception occurs at an arbitrary point in time (Error in caption). Is there a way to make this code work with minimal effort?

I am looking for a method to concurrently communicate with std::map in a multithreaded environment. But, Debug Assertion Failed: Expression: cannot dereference value-initialized map/set iterator.

CodePudding user response：

 std::map<int, uint64_t>::iterator it_mp = mp.find(key);

This accesses the contents of the multimap, without the protection of a mutex. The other execution thread is modifying this map, concurrently. This is undefined behavior.

Neither std::map, nor any other container in the C library, is thread-safe. This means that all access to the container, and not just modifications to the container, must be synchronized (i.e., protected by a mutex). The shown code locks a mutex to synchronize only certain modifications to the map. This is insufficient. All access to the map must be synchronized.

Additionally, ignoring the subject of synchronization for a brief moment: the overall algorithm also has another flaw. Even if find() does not find an existing value in the map, the other execution thread may end up reaching the same conclusion and insert() its value into the map before the first execution thread gets around to calling insert(), itself. The clear intent of the shown code is for the find/insert to be an atomic operation. This is another reason why that entire section of code must be protected by a mutex (and not only the insert() call).

CodePudding user response：

Yes, You are right. Mutexes need before iterators.

shared_lock before "update" and "insertion", unique_lock before "erase".

Refurbished code:

#include <iostream>
#include <random>
#include <string>
#include <map>
#include <shared_mutex>

std::map<int, uint64_t> mp;

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distr(1, 9);

//std::mutex _mutex;
//std::shared_timed_mutex _mutex;
//std::recursive_mutex _mutex;

std::shared_mutex _mutex;

void t1()
{
    int key = 0;
    uint64_t i;
    while (1)
    {
          key;
        if (key < 1000)
        {
            std::shared_lock guard(_mutex);
            std::map<int, uint64_t>::iterator it_mp = mp.find(key);
            if (it_mp != mp.end())
            {
                i = distr(gen);
                std::cout << "UPDATE\t1\t" << it_mp->first << "\t" << it_mp->second << "\t->\t" << i << "\n";
                it_mp->second = i;
            }
            else
            {
                i = distr(gen);
                std::cout << "INSERT\t1\t" << key << "\t->\t" << i << "\n";
                mp.insert ({key, i});
            }
        }
        else
        {
            i = distr(gen);
            std::unique_lock guard(_mutex);
            std::map<int, uint64_t>::iterator it_mp = mp.begin();
            while (it_mp != mp.end())
            {
                if (it_mp->second == i)
                {
                    std::cout << "ERASE\t1\t" << it_mp->first << "\t<-\t" << i << "\n";
                    it_mp = mp.erase(it_mp);
                }
                else
                {
                      it_mp;
                }
            }

            key = 0;
        }
    }
}

void t2()
{
    int key = 0;
    uint64_t i;
    while (1)
    {
          key;
        if (key < 1000)
        {
            std::shared_lock guard(_mutex);
            std::map<int, uint64_t>::iterator it_mp = mp.find(key);
            if (it_mp != mp.end())
            {
                i = distr(gen);
                std::cout << "UPDATE\t2\t" << it_mp->first << "\t" << it_mp->second << "\t->\t" << i << "\n";
                it_mp->second = i;
            }
            else
            {
                i = distr(gen);
                std::cout << "INSERT\t2\t" << key << "\t->\t" << i << "\n";
                mp.insert({ key, i });
            }
        }
        else
        {
            i = distr(gen);
            std::unique_lock guard(_mutex);
            std::map<int, uint64_t>::iterator it_mp = mp.begin();
            while (it_mp != mp.end())
            {
                if (it_mp->second == i)
                {
                    std::cout << "ERASE\t2\t" << it_mp->first << "\t<-\t" << i << "\n";
                    it_mp = mp.erase(it_mp);
                }
                else
                {
                      it_mp;
                }
            }

            key = 0;
        }
    }
}

int main()
{
    std::thread _t1(t1);
    _t1.detach();

    std::thread _t2(t2);
    _t2.join();

    return 0;
}

... works like charm. ... Maybe this will help someone.