需要一个 C++ 映射和列表，其中包含彼此的迭代器

Question

我有一个使用地图和列表保持同步的自定义模板化容器。映射需要包含 MyList::const_iterator，列表需要包含 MyMap::const_iterator。我能够找到的唯一解决方案是双关语其中一个迭代器，如下例所示。

是否有适当的方式转发声明这样我就不需要丑陋的双关语了？

可运行代码位于 http://coliru.stacked-crooked.com/a/a5eae03ad5090b27。

（当然还有其他方法可以用于该示例，但这超出了范围。这是一个更大程序的片段。我只是想使这个“循环”没有 UB 的定义。)

#include <iostream>
#include <list>
#include <unordered_map>

template<class ObjectT> class MyClass
{
private:
// SUMMARY: The map must contain an iterator to the list, and the list must contain an iterator to the map.
// I have not been able to figure out how to define that (circular), so I've punned an iterator to a different list for the map entry.
    typedef std::list<ObjectT> PunnedList;

    struct MapEntry
    {
        ObjectT m_object;
        mutable typename PunnedList::const_iterator m_listIt; // Really a List::const_iterator, but that can't be defined.
    };

    typedef std::unordered_multimap<std::string, MapEntry> Map;

public:
    struct ListEntry
    {
        typename Map::iterator m_mapIt;

        const ObjectT& object() const
        {
            return m_mapIt->second.m_object;
        }

        const std::string& name() const
        {
            return m_mapIt->first;
        }

    };
private:
    typedef std::list<ListEntry> List;

    Map mMap;
    List mList;

private:
    typename List::const_iterator listiter_from_mapiter( typename Map::const_iterator& miter ) const
    {
        static_assert(sizeof(typename PunnedList::const_iterator) == sizeof(typename List::const_iterator));
        return *(reinterpret_cast<typename List::const_iterator*>(&miter->second.m_listIt));
    }

public:
    
    typename List::const_iterator append( const std::string &name, const ObjectT& item )
    {
        static_assert(sizeof(typename PunnedList::const_iterator) == sizeof(typename List::const_iterator));

        MapEntry entry{ item, typename PunnedList::const_iterator{} };

        auto mapIter = mMap.insert({ name, entry });
        mList.push_back({ mapIter });
        auto iter = mList.cend();
        --iter;
        *(reinterpret_cast<typename List::const_iterator*>(&mapIter->second.m_listIt)) = iter;
        return iter;
    }
    
    typename List::const_iterator begin() const
    {
        return mList.end();
    }

    typename List::const_iterator end() const
    {
        return mList.end();
    }

    void erase( typename List::const_iterator iter )
    {
        mMap.erase(iter->m_mapIt);
        mList.erase( iter );
    }

    typename List::const_iterator find( const std::string &name ) const
    {
        auto range = mMap.equal_range(name);

        for (auto mapIter = range.first; mapIter != range.second; ++mapIter)
        {
            // In the real program, there are additional criteria on the map entry, not needed for the example.
            // if (mapIter is a match)
                return listiter_from_mapiter(mapIter);
        }

         return mList.cend();
    }
};

int main()
{
    MyClass<int> container;
    container.append("A",1);
    container.append("B",2);
    container.append("C",1);
    
    std::cout << container.find("B")->object();
}

Answer 1

Forward-declaring 你的内心至少有一个类打破了循环：

template<class ObjectT> class MyClass
{
public:
    struct ListEntry;
private:
    typedef std::list<ListEntry> List;

    // Rest of the class, using List as you like

请注意，以下 List::const_iterator 之所以有效，是因为 std::list<T> 不需要 T 完成实例化。

Answer 2

无法声明依赖于类型 Y 的类型 T，而类型 Y 也依赖于 T。但你可以使用包装器来做到这一点：

(看来你想创建一个哈希table，其中元素是按插入顺序排列的？通常的做法是将链表的元素和迭代器包装起来。)

#include <string>
#include <list>
#include <unordered_map>


template<typename T>
class A{
    struct Wrapper;
    typedef std::unordered_multimap<std::string, Wrapper> Map;
    typedef typename Map::const_iterator map_iter;
    typedef std::list<map_iter> List;
    typedef typename List::const_iterator list_iter;
    struct Wrapper{
        T value;
        list_iter iter;
    };
    Map map;
    List list;
public:
    // do what you want
};

之所以有效，是因为声明 std::unordered_multimap<std::string, Wrapper>::iterator 不需要定义 Wrapper（不需要在此处实例化）。

需要一个 C++ 映射和列表，其中包含彼此的迭代器

Need a C++ map and list which contain iterators to each other

c++

std

forward-declaration