c++iteratorcrashinvalidation

What causes the stored std::list::iterator to become invalid?


edit: The below code can be run on https://wandbox.org/permlink/1Qry83quzoDveYDi
I implemented various suggestions from the comments, but unfortunately, it is still not clear to my why erasing the item at this particular std::list::iterator (line 86) crashes at runtime. All the explanations given below seem to affirm that the iterator should still be valid at this point.


I was under the impression that iterators to items in a std::list do not get invalidated when an item is inserted into a list (refer to this excellent post).

However, in the below code, the line
items.at(noOfitems-2)->erase(iter++); (line 86)
crashes the program with
malloc: *** error for object 0x100778b28: pointer being freed was not allocated.

Could you please help me understand why (where) this iterator std::list<std::string>::iterator becomes invalid, and how I can make it work without iteratively finding it again?

Am I perhaps misunderstanding the error?

#include <iostream>
#include <iostream>
#include <vector>
#include <random>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <list>
#include <utility>
#include <chrono>
#include <sstream>
#include <tr1/memory>

class Increment;
struct Item;

struct Pairhash {
public:
  template <typename T>
  std::size_t operator()(const T &x) const
  {
      return std::hash<T>()(x) ^ std::hash<T>()(x);
  }
};

struct Item {
    Item() = default;
    std::string name;
    int counter;
    Item(std::string name) : counter(0)
    {
        this->name = name;
    }
    
    bool operator==(const Item& p) const
    {
        return (this->name == p.name);
    }
    
    bool operator<(const Item& p) const
    {
        return (this->counter < p.counter);
    }
};

class Increment {
private:
    std::unordered_map<std::string, std::pair<std::list<std::string>::iterator , std::shared_ptr<Item> >, Pairhash >  itemMap;
    std::vector<std::shared_ptr<std::list<std::string>>> items;
public:
    Increment() = default;
    std::list<std::string>::iterator insertItem(std::string & name , int noOfitems)
    {
        if (noOfitems > items.size())
        {
            items.emplace_back(std::make_shared<std::list<std::string>>(std::initializer_list<std::string>{ name }));
            return items.back()->begin();
        }
        else
        {
            items.at(noOfitems-1)->emplace_back(name);
            return items.at(noOfitems-1)->rbegin().base(); //Last position in list
        }
    }
    
    std::list<std::string>::iterator adjustItemPosition(std::string & name, int noOfitems, std::list<std::string>::iterator & iter)
    {
        if (noOfitems > items.size())
        {
            std::list<std::string> temp{name};
            items.push_back(std::make_shared<std::list<std::string>>(temp));
        }
        else
        {
            items.at(noOfitems-1)->emplace_back(name);
        }
        /* // Works as expected
        auto itr = std::find(items.at(noOfitems-2)->begin(), items.at(noOfitems-2)->end(), name);
        if (itr != items.at(noOfitems-2)->end())
        {
            items.at(noOfitems-2)->erase(itr);
        }
        */
        items.at(noOfitems-2)->erase(iter++); //TODO Crashes
        return items.at(noOfitems-1)->rbegin().base(); //Last position in list
    }
    
    void incrementByOne(std::string name)
    {
        auto it = itemMap.find(name);
        if (it != itemMap.end()) //Item already in map
        {
            it->second.second->counter++;
            it->second.first = adjustItemPosition(name, it->second.second->counter,
                                                    it->second.first);
        }
        else  //New item to be inserted
        {
            std::shared_ptr<Item> temp = std::make_shared<Item>(Item(name));
            temp->counter = 1;
            std::list<std::string>::iterator listIter = insertItem(name, 1);
            itemMap.emplace(name, std::make_pair( listIter, temp));
        }
    }
    
    std::string printTop10() const
    {
        std::stringstream ss;
        auto count(0);
        for (auto it = items.rbegin(); it != items.rend(); ++it)
        {
            for (auto item : **it)
            {
                if (count == 10)
                {
                    break;
                }
                ss << "We have " << itemMap.at(item).second->counter << " " << item << std::endl;
                ++count;
            }
        }
        return ss.str();
    }
};

int main(int argc, const char * argv[]) {
    Increment incrementer;
    std::vector<std::string> names{ "Bananas", "Apples", "Peaches", "Durians", "Hazelnuts", "Avocados", "Pineapples", "Cherries", "Almonds", "Olives", "Eggs", "Yoghurts", "Peas", "Blueberries" };

    for (int i = 0; i < 100; ++i) {
        incrementer.incrementByOne(names.at(i%10));
    }
    std::cout << incrementer.printTop10() << std::endl;
    return 0;
}

Solution

  • Replacing
    return items.at(noOfitems-1)->rbegin().base();
    with
    return std::next(items.at(noOfitems-1)->end(), -1);

    in lines 63 and 86 fixes the crash.
    Working solution: https://wandbox.org/permlink/I68Szb0XMRKsPZqp

    #include <iostream>
    #include <iostream>
    #include <vector>
    #include <random>
    #include <unordered_set>
    #include <set>
    #include <unordered_map>
    #include <map>
    #include <list>
    #include <utility>
    #include <chrono>
    #include <sstream>
    #include <memory>
    
    class Increment;
    struct Item;
    
    struct Pairhash {
    public:
      template <typename T>
      std::size_t operator()(const T &x) const
      {
          return std::hash<T>()(x) ^ std::hash<T>()(x);
      }
    };
    
    struct Item {
        Item() = default;
        std::string name;
        int counter;
        Item(std::string name) : counter(0)
        {
            this->name = name;
        }
    
        bool operator==(const Item& p) const
        {
            return (this->name == p.name);
        }
    
        bool operator<(const Item& p) const
        {
            return (this->counter < p.counter);
        }
    };
    
    class Increment {
    private:
        std::unordered_map<std::string, std::pair<std::list<std::string>::iterator , std::shared_ptr<Item> >, Pairhash >  itemMap;
        std::vector<std::shared_ptr<std::list<std::string>>> items;
    public:
        Increment() = default;
        std::list<std::string>::iterator insertItem(std::string & name , int noOfitems)
        {
            if (noOfitems > items.size())
            {
                items.emplace_back(std::make_shared<std::list<std::string>>(std::initializer_list<std::string>{ name }));
                return items.back()->begin();
            }
            else
            {
                items.at(noOfitems-1)->emplace_back(name);
                return std::next(items.at(noOfitems-1)->end(), -1);  // versus return items.at(noOfitems-1)->rbegin().base(); //Crashes
            }
        }
    
        std::list<std::string>::iterator adjustItemPosition(std::string & name, int noOfitems, std::list<std::string>::iterator & iter)
        {
            if (noOfitems > items.size())
            {
                std::list<std::string> temp{name};
                items.push_back(std::make_shared<std::list<std::string>>(temp));
            }
            else
            {
                items.at(noOfitems-1)->emplace_back(name);
            }
            /* // Works as expected
            auto itr = std::find(items.at(noOfitems-2)->begin(), items.at(noOfitems-2)->end(), name);
            if (itr != items.at(noOfitems-2)->end())
            {
                items.at(noOfitems-2)->erase(itr);
            }
            */
            items.at(noOfitems-2)->erase(iter++); //TODO Crashes
            return std::next(items.at(noOfitems-1)->end(), -1); //versus return items.at(noOfitems-1)->rbegin().base(); //Crashes
        }
    
        void incrementByOne(std::string name)
        {
            auto it = itemMap.find(name);
            if (it != itemMap.end()) //Item already in map
            {
                it->second.second->counter++;
                it->second.first = adjustItemPosition(name, it->second.second->counter,
                                                        it->second.first);
            }
            else  //New item to be inserted
            {
                std::shared_ptr<Item> temp = std::make_shared<Item>(Item(name));
                temp->counter = 1;
                std::list<std::string>::iterator listIter = insertItem(name, 1);
                itemMap.emplace(name, std::make_pair( listIter, temp));
            }
        }
    
        std::string printTop10() const
        {
            std::stringstream ss;
            auto count(0);
            for (auto it = items.rbegin(); it != items.rend(); ++it)
            {
                for (auto item : **it)
                {
                    if (count == 10)
                    {
                        break;
                    }
                    ss << "We have " << itemMap.at(item).second->counter << " " << item << std::endl;
                    ++count;
                }
            }
            return ss.str();
        }
    };
    
    int main(int argc, const char * argv[]) {
        Increment incrementer;
        std::vector<std::string> names{ "Bananas", "Apples", "Peaches", "Durians", "Hazelnuts", "Avocados", "Pineapples", "Cherries", "Almonds", "Olives", "Eggs", "Yoghurts", "Peas", "Blueberries" };
    
        for (int i = 0; i < 100; ++i) {
            incrementer.incrementByOne(names.at(i%10));
        }
        std::cout << incrementer.printTop10() << std::endl;
        return 0;
    }
    

    I believe the answer as to why this is so was given in https://stackoverflow.com/a/33851951, namely that the pointer to the reverse iterator is in fact a copy of the original reference to it, which is deleted when it goes out of scope. http://cplusplus.github.io/LWG/lwg-defects.html#2360