std :: map с итераторами в std :: list из итераторов std :: map

Question

Как объявить std :: list (1) с помощью итераторов на std :: map, который сопоставляет std :: string с итераторами std :: список (1)? Является ли это возможным?

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

Причина, по которой я хочу это - очередь FIFO с возможностью быстрого удаления с помощью ключа.

Одно из возможных решений:

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

Здесь некрасиво, но полный пример

#include <cassert> 
#include <iostream> 
#include <list> 
#include <map> 
#include <string> 

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; 
}; 

int main(int argc, const char* argv[]) 
{ 
    decl_t::map_t map; 
    decl_t::list_t list; 

    auto list_it = list.emplace(list.end(), 42, decl_t::map_t::iterator()); 
    const auto pair = std::make_pair(std::string("key"), decl_t{list_it}); 
    auto result = map.insert(pair); 
    assert(result.second); 
    auto map_it = result.first; 
    list_it->second = map_it; 

    std::cout << list_it->second->first << std::endl; 
    std::cout << map_it->second.it->first << std::endl; 
} 

Answer 2

Для целей в FIFO с возможностью удаления с помощью ключа, я предлагаю вам использовать unordered_map, так как у вас нет необходимости порядка в карте.

После этого, возможно, вы можете изменить схему перекрестных ссылок. Используйте список строк, и отображение отображения строку в итераторы такого списка:

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


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

Для направления нахождения ключа в карте, как только вы итератор в списке, вы должны выполнить излишний хэш на имя относительно вашей полной схемы итератора-итератора, но все равно O (1) (ожидается). И наоборот, ваша оригинальная схема требует логарифмических операций для удаления с помощью ключа, поэтому вы, вероятно, еще впереди.

Чтобы вставить новый элемент, вы могли бы сделать что-то вроде этого:

map_t map; 
list_t list; 

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

---

Пример

#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; 
}