Tengo un struct nodo¿Qué función de la biblioteca std hay para buscar binariamente un vector y encontrar un elemento?
struct Node{CString text, int id;};
en un vector ordenado.
Me pregunto si hay una función en el algoritmo que hará una búsqueda binaria del vector y encontrará un elemento.
std::binary_search() le dirá si existe un valor en el contenedor.
std::lower_bound()/std::upper_bound() volverá un iterador a la primera/última ocurrencia de un valor.
Sus objetos deben implementar operator< para que estos algoritmos funcionen.
o necesita usar la otra sobrecarga para 'binary_search' y proporcionar un comparador en el 4º parámetro. Debe ser el mismo comparador con el que solía ordenar. – KitsuneYMG
"A diferencia de lower_bound, para upper_bound el valor apuntado por el iterador devuelto por esta función no puede ser ** equivalente ** a val, solo mayor."¿Cómo puede upper_bound devolver la última ocurrencia de val? –
Sí, hay una función llamada "binary_search" std :: binary_search
Se le da nombre, apellido y un valor o un predicado.
Ver here para una muestra
combinar eso con Martin York's operador == y usted debe estar bien (de forma alternativa se puede escribir un funtor predicado
En realidad para la búsqueda binaria, necesita un operador <, no operador == –
boost :: bind (& Node :: text, _1)
También tenga en cuenta que no encuentra el elemento. Simplemente prueba la existencia. –
En lugar de un vector ordenado <Nodo>
¿Por qué no utilizar un mapa? Este es un contenedor clasificado. Por lo tanto, cualquier búsqueda realizada en esta vía, std :: find() tiene automáticamente las mismas propiedades que una búsqueda binaria.
Si sus datos son estables (sin adiciones/eliminaciones en curso), es más eficiente con la memoria para usar el vector. Si necesita interactuar con otras partes del sistema que esperan un o necesita acceder a los datos por índice. O bien, se accede a los datos en un bucle cerrado, donde la ubicación de la memoria es importante. – KeithB
"Un vector ordenado le permite recorrer los contenidos en orden": también lo hace un mapa. for (std :: map
un mapa tampoco funciona tan bien con varias instancias del clave. – baash05
Usa std::equal_range para encontrar una gama de elementos en un vector ordenado. std::equal_range devuelve std::pair de iteradores, lo que le proporciona un rango en el vector de elementos igual al argumento que proporciona. Si el rango está vacío, entonces tu artículo no está en el vector, y la longitud del rango te dice cuántas veces aparece tu elemento en el vector.
Aquí hay un ejemplo usando enteros en lugar de struct Node:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
int main(int argc, const char * argv[])
{
std::vector<int> sorted = { 1, 2, 2, 5, 10 };
auto range = std::equal_range(sorted.begin(), sorted.end(), 20);
// Outputs "5 5"
std::cout << std::distance(sorted.begin(), range.first) << ' '
<< std::distance(sorted.begin(), range.second) << '\n';
range = std::equal_range(sorted.begin(), sorted.end(), 5);
// Outputs "3 4"
std::cout << std::distance(sorted.begin(), range.first) << ' '
<< std::distance(sorted.begin(), range.second) << '\n';
range = std::equal_range(sorted.begin(), sorted.end(), -1);
// Outputs "0 0"
std::cout << std::distance(sorted.begin(), range.first) << ' '
<< std::distance(sorted.begin(), range.second) << '\n';
return 0;
}
Para hacer este trabajo con struct Node ya sea que usted tiene que proporcionar una operator < para struct Node o pasar en un comparador de std::equal_range. Puede hacerlo proporcionando un lambda como argumento al std::equal_range para comparar sus estructuras.
std::vector<Node> nodes = { Node{"hello", 5}, Node{"goodbye", 6} };
Node searchForMe { "goodbye", 6 };
auto range = std::equal_range(nodes.begin(), nodes.end(), searchForMe,
[](Node lhs, Node rhs) { return lhs.id < rhs.id; });
¿Estás seguro de la coma entre CString? ¿No debería ser eso un punto y coma? – razeh