Pregunta Implementando un "grupo de cadenas" que está garantizado que no se moverá


Necesito un objeto "string pool" en el que pueda insertar repetidamente una "secuencia de caracteres" (uso esta frase para significar "cadena" sin confundirla con std :: string o una cadena C), obtengo un puntero a la secuencia , y se garantiza que el puntero no se invalidará si / cuando el grupo necesita crecer. Usando un simple std::string ya que la agrupación no funcionará, debido a la posibilidad de que la cadena se reasigne cuando supere su capacidad inicial, invalidando así todos los punteros anteriores.

El conjunto no crecerá sin límite: hay puntos bien definidos en los que llamaré clear() método, pero tampoco quiero reservar capacidad máxima en él. Debería poder crecer, sin moverse.

Una posibilidad que estoy considerando es insertar cada nueva secuencia de caracteres en un forward_list<string> y obteniendo begin()->c_str(). Otra es insertar en una unordered_set<string>, pero me está costando averiguar qué sucede cuando un conjunto no ordenado tiene que crecer. La tercera posibilidad que estoy considerando (menos entusiastamente) es desplegar mi propia cadena de almacenamientos intermedios 1K en la que concatené la secuencia de caracteres. Eso tiene la ventaja (supongo) de tener el rendimiento más alto, que es un requisito para este proyecto.

Me interesaría escuchar cómo otros recomendarían acercarse a esto.

ACTUALIZACIÓN 1: editado para aclarar mi uso de la frase "secuencia de caracteres" para que sea equivalente a la noción general de "cadena" sin implicar std :: cadena o matriz de caracteres terminada en nulo.


9
2018-01-05 20:00


origen


Respuestas:


He usado este enfoque en el pasado:

using Atom = const char*;

Atom make_atom(string const& value)
{
    static set<string> interned;
    return interned.insert(value).first->c_str();
}

Obviamente, si quiere / necesita borrar el conjunto, lo haría disponible en un ámbito más amplio.

Para una mayor eficiencia, mueva / coloque las cuerdas en el conjunto.

Actualizar He agregado este enfoque para completarlo. Míralo Vivir en Coliru

#include <string>
#include <set>
using namespace std;

using Atom = const char*;

template <typename... Args>
typename enable_if<
    is_constructible<string, Args...>::value, Atom
>::type emplace_atom(Args&&... args)
{
    static set<string> interned;
    return interned.emplace(forward<Args>(args)...).first->c_str();
}

#include <iostream>

int main() {
    cout << emplace_atom("Hello World\n");
    cout << emplace_atom(80, '=');
}

8
2018-01-06 23:24



Sí, vas a tener que escribir una lista de almacenamientos intermedios. No, no hagas todo el trabajo duro por ti mismo.

La estructura de datos subyacente debe ser una std::vector<std::string>. Usar una lista (hacia adelante) no te compra mucho. Cuando el vector se redimensiona, las cadenas se mueven de manera eficiente.   std::forward_list<std::string>. Incluso si la lista se redimensiona, las cadenas en sí permanecen en su lugar. La iteración de la lista solo es necesaria para una .clear por lo que el rendimiento de la lista no es crítico.

La clase contenedora debe abstraer la adición de nuevas cadenas. Se debe agregar una nueva cadena cuando la capacidad de la última cadena no es suficiente para agregar la nueva cadena. Cuando agrega una nueva cadena, reserve toda la memoria que necesitará un trozo; esto asegura que la capacidad será lo suficientemente grande como para evitar reasignaciones más adelante.

Esta configuración puede perder algo de espacio cuando una nueva asignación grande fuerza el uso de un nuevo fragmento, dejando parte de un fragmento más viejo sin usar. Por supuesto, podría recordar el tamaño restante en los últimos N bloques, para un pequeño valor de N tal que esos fragmentos aún podrían estar en caché. Pero es muy posible que en tu aplicación N = 5 ya sea demasiado grande.


1
2018-01-06 23:15



Recapping, sus requisitos son:

  • Poder empujar elementos
  • Ser capaz de obtener un iterador al comienzo de la secuencia
  • Los iteradores no deben ser invalidados si la secuencia crece
  • Ser capaz de clear la secuencia
  • No reserve la capacidad máxima

Parece que std::list<char> encaja perfectamente en esta lista de requisitos. Por supuesto, es posible que necesite una envoltura alrededor de la clase para que se comporte exactamente como std::string, pero eso realmente depende de cómo manipules los datos.

Y así es cómo se ajusta a los requisitos:

  • Para empujar elementos, puede usar push_back y emplace_back funciones miembro

  • std::begin(container) o la función miembro begin recuperará el iterador al primer elemento de la secuencia.

  • Agregar, eliminar y mover los elementos dentro de la lista o en varias listas no invalida los iteradores. Un iterador se invalida solo cuando se elimina el elemento correspondiente.

  • Para borrar la secuencia, puede usar la función miembro clear.

  • La mayoría de las veces se implementa como una lista doblemente enlazada, por lo tanto, no se reserva ninguna capacidad.

Ya que std::list  parece memoria ineficiente (aunque el estándar no especifica el tamaño ni su implementación), es correcto agregar que también puede usar std::deque<char> con casi la misma interfaz que arriba. La única diferencia es que std::deque podría reservar memoria no utilizada.


0
2018-01-05 20:53