std::map with iterators to std::list from iterators of std::map

Question

How should I declare std::list(1) with iterators to std::map, which maps std::string to iterators of std::list (1) ? Is it possible?

std::list<std::map<std::string, (1) ???>::iterator>;
std::map<std::string, (1) ???::iterator>;

The reason I want this - FIFO queue with ability to fast remove by key.

One possible solution:

struct decl_t {
    typedef std::map< std::string, decl_t > map_t;
    typedef std::list< std::pair< int, typename map_t::iterator > > list_t;

    list_t::iterator it;
};

Answer 1

For the purpose of a FIFO with the ability to remove by key, I suggest you use unordered_map, as you have no need for order in the map.

Following that, perhaps you could change your cross-referencing scheme. Use a list of strings, and a map mapping strings to iterators of such a list:

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


using map_t = unordered_map<string, list<string>::iterator>;
using list_t = list<string>;

For the direction of finding a key in the map once you have an iterator in the list, you need to perform a redundant hash on the name relative to your full iterator-to-iterator scheme, but it is still O(1) (expected). Conversely, your original scheme required logarithmic operations for removal by key, so you're probably still ahead.

To insert a new element, you could do something like this:

map_t map;
list_t list;

list.push_back("koko");
auto it = --list.end();
map["koko"] = it;

---

Example

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


using namespace std;


int main()
{
    using map_t = unordered_map<string, list<string>::iterator>;
    using list_t = list<string>;

    map_t map;
    list_t list;

    list.push_back("koko");
    auto it = --list.end();
    map["koko"] = it;
}