Devolviendo un vector vacío de cadenas si no se encuentra la clave

Question

Sé que es una muy mala idea, por lo que otras sugerencias sobre cómo hacerlo de manera eficiente serán bien recibidas.

Aquí está la cosa. Tengo map<string,vector<string> >, quiero buscar una clave y devolver su valor correspondiente (vector de cadenas en este caso). Motivo Insisto en regresar (en lugar de simplemente iterar) es necesario buscar los valores devueltos en algún otro vector.

Un ejemplo aclarará esto:

Input: 

key1 ---> {2,3,4} 
key2 ---> {1} 
key3 ---> {2,12,11,9} 

Para key1 como entrada, el vector con los valores 2,3,4 debe ser devuelto. Ahora estos valores 2,3,4 deben buscarse en otro vector de cadenas. ¿Cuál es la forma más eficiente de hacer esto?

que hemos probado algo como esto:

vector<string> returnEdges(string key) 
{ 
    for (map<string, vector<string> >::iterator it=outgoing.begin(); 
    it!=outgoing.end();++it) 
    { 
     if (key.compare((*it).first)==0) 
     { 
      return (*it).second; 
     } 
    } 


    //return string<;//what should I return here???? 


} 

1) ¿Cómo debería volver vector vacío en la caja dominante no se encuentra?

2) ¿Cuál es la mejor manera de implementar esto?

Espero que la pregunta sea clara.

EDIT: Cuando escribí la pregunta, pensé ¿por qué no devolver un iterador? ¿Las personas en SO dan su aprobación para esta idea?

Answer 1

1) Devolver un iterador es una buena idea. Cuando hace esto, la forma natural de indicar el caso "no encontrado" es devolver el iterador .end(). Esto tiene el inconveniente de que la abstracción es un poco permeable: la persona que llama tiene que ser capaz de obtener este valor .end() para compararlo con la comprobación de errores, y el iterador devuelto expone una interfaz más rica de lo que Me gusta (el código del cliente no debería jugar con aumentar y disminuir el iterador).

2) Devolver un vector vacío es tan simple como crear un vector vacío y devolverlo. Creando un vector vacío = construyendo un vector que está vacío. Esto es lo que obtienes de la lista de percusión: el constructor predeterminado de la clase de vector.

3) No necesita, y no debe, implementar el bucle de búsqueda usted mismo. La biblioteca estándar ya implementa esto para usted. (Hay una find función especializada para map s debido a la diferencia clave/valor. Para secuencias como list, vector y deque, prefieren la función libre std::find, que viene de <algorithm>.

4) Usted debe preferir a aceptar la función parámetros (cuando son instancias de clases, como std::string) y datos de retorno (especialmente cosas complejas como un vector de cadenas) por referencia. Pasar y regresar por valor implica una copia; a veces el compilador puede optimizar esto, pero no es tan confiable como nos gustaría.Además, la razón por la que estás usando C++ en primer lugar es tener ese nivel de control sobre las cosas, ¿verdad? Si no, entonces no te tortures con eso.

Sin embargo, no puede hacer eso si va a devolver un valor recién creado alguna vez. Otra forma de diseñar la interfaz es devolver un puntero al vector de cadenas (tenga en cuenta que la aritmética del puntero en estos no será válida) dentro del mapa, o un puntero NULL si no se encuentra el valor. Esto evita la copia y distingue un resultado "no encontrado" de un vector vacío real dentro de los datos, pero significa que el código del cliente tiene que lidiar con un puntero crudo icky.

5) Tener 'retorno' en el nombre de una función es inútil, ya que devolver es lo que hacen las funciones. OTOH, es una buena idea nombrar las cosas de una manera que haga evidente por qué los parámetros son lo que son.

6) Con los iteradores para tipos complejos, a menudo es una buena idea configurar los tipos.

Volviendo un iterador es tan simple como:

typedef map<string, vector<string> >::iterator graph_iterator; 
graph_iterator edges_named(const string& node_name) { 
    return outgoing.find(node_name); 
} 

La devolución de un vector de cadenas es tan simple como:

typedef map<string, vector<string> >::iterator graph_iterator; 
vector<string> edges_named(const string& node_name) { 
    graph_iterator it = outgoing.find(node_name); 
    return it == outgoing.end() ? vector<string>() : it->second; 
} 

devolviendo un puntero es tan simple como:

typedef map<string, vector<string> >::iterator graph_iterator; 
vector<string>* edges_named(const string& node_name) { 
    graph_iterator it = outgoing.find(node_name); 
    return it == outgoing.end() ? NULL : &(it->second); 
} 

Elige sabiamente.

Answer 2

¿Qué tal esto:

std::vector<std::string> find_by_key_maybe(const std::string & key) 
{ 
    std::map<std::string, std::vector<std::string>>::const_iterator it = themap.find(key); 
    return it == themap.end() ? std::vector<std::string>() : it->second; 
} 

O incluso, si themap es no constante, y también se quieren añadir un vector vacío en el mapa:

std::vector<std::string> find_by_key_and_insert_if_missing(const std::string & key) 
{ 
    return themap[key]; 
} 

Es perfectamente OK para volver un vector por valor, si eso es lo que requiere la situación.

Answer 3

La mayoría de las veces no necesita una copia del vector que se devolverá, una referencia constante funcionará igual de bien. Siempre puede hacer una copia más tarde si lo necesita.

Además, no necesita iterar a través de un mapa, están optimizados para buscar con el método find.

const vector<string> & returnEdges(string key) 
{ 
    map<string, vector<string> >::iterator it = outgoing.find(key); 
    if (it == outgoing.end()) 
    { 
     static vector<string> empty_vector; 
     return empty_vector; 
    } 
    return it->second; 
} 

Answer 4

Creo que el operador [] puede ayudarlo, devolverá un valor vacío (un vector vacío aquí). Así que todo lo que necesita hacer es

vector<string> returnEdges(string key) 
{ 
    return outgoing[key]; 
}