const std::string *get_ref(const std::string &str);
unsigned int count_ref(const std::string &str);
unsigned int remove_ref(const std::string &str);
mngr.get_ref(str);
class string_compare
{
public:
string_compare(void);
bool operator()(const std::string *left, const std::string *right);
};
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// String Manager Stats
// Maintain various performance statistics
// – Justice
class StringManagerStats
{
protected:
unsigned int m_total_string;
unsigned int m_total_insert;
unsigned int m_total_delete;
unsigned int m_total_refs;
unsigned int m_total_chars;
unsigned int m_total_saved_chars;
StringManagerStats(void)
{
m_total_string = 0;
m_total_insert = 0;
m_total_delete = 0;
m_total_refs = 0;
m_total_chars = 0;
m_total_saved_chars = 0;
}
inline void update_new_ref(unsigned int len)
{
m_total_refs++;
m_total_string++;
m_total_insert++;
m_total_chars += len;
}
inline void update_add_ref(unsigned int len)
{
m_total_refs++;
m_total_saved_chars += len;
}
inline void update_delete_ref(unsigned int len)
{
m_total_refs–;
m_total_string–;
m_total_delete++;
m_total_chars -= len;
}
inline void update_remove_ref(unsigned int len)
{
m_total_refs–;
m_total_saved_chars -= len;
}
public:
inline unsigned int total_strings(void)
{
return m_total_string;
}
inline unsigned int total_inserted(void)
{
return m_total_insert;
}
inline unsigned int total_deleted(void)
{
return m_total_delete;
}
inline unsigned int total_refs(void)
{
return m_total_refs;
}
inline unsigned int total_chars(void)
{
return m_total_chars;
}
inline unsigned int total_saved_chars(void)
{
return m_total_saved_chars;
}
};
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// String Manager
// Shared string management using a refcount table.
// – Justice
class StringManager : public StringManagerStats
{
protected:
typedef std::map<const std::string*, unsigned int, string_compare>::iterator ITERATOR;
typedef std::pair<const std::string*, unsigned int> PAIR;
std::map<const std::string*, unsigned int, string_compare> content;
public:
StringManager(void);
~StringManager(void);
// Get a string reference.
// str = string to reference
// old = previous reference (remove if exists)
const std::string *get_ref(const std::string &str, const std::string *old);
const std::string *get_ref(const std::string *str, const std::string *old);
// Count a string's references.
// str = string to lookup
unsigned int count_ref(const std::string &str);
// Count a string's references.
// str = string to remove
const std::string *remove_ref(const std::string *str);
// Pass each string/refcount to a supplied object.
// Traits: T
// bool operator()(const std::string*,unsigned int)
// if TRUE then break
template <class T>
void for_each(T value)
{
ITERATOR it, end;
it = content.begin();
end = content.end();
for (; it != end; it++)
if (value(it->first, it->second))
break;
}
};
bool string_compare::operator()(const std::string *left, const std::string *right)
{
return (left->compare(*right) < 0);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// String Manager
StringManager::StringManager(void)
{
}
StringManager::~StringManager(void)
{
ITERATOR nxt,it,end;
const std::string *cur;
nxt = content.begin();
end = content.end();
while (nxt != end)
{
it = nxt++;
cur = it->first;
content.erase(it);
delete cur;
}
}
unsigned int StringManager::count_ref(const std::string &str)
{
ITERATOR fnd;
if ((fnd = content.find(&str)) == content.end())
return 0;
return fnd->second;
}
const std::string *StringManager::get_ref(const std::string &str, const std::string *old)
{
ITERATOR fnd;
PAIR tmp;
// Clear Reference
if (old)
remove_ref(old);
// Insert
if ((fnd = content.find(&str)) == content.end())
{
update_new_ref(str.length());
tmp.first = new std::string(str);
tmp.second = 1;
content.insert(tmp);
return tmp.first;
}
update_add_ref(str.length());
// Update
fnd->second++;
return fnd->first;
}
const std::string *StringManager::get_ref(const std::string *str, const std::string *old)
{
ITERATOR fnd;
PAIR tmp;
// Clear Reference
if (old)
remove_ref(old);
// Cannot insert null
if (!str)
return NULL;
// Insert
if ((fnd = content.find(str)) == content.end())
{
update_new_ref(str->length());
tmp.first = new std::string(*str);
tmp.second = 1;
content.insert(tmp);
return tmp.first;
}
update_add_ref(str->length());
// Update
fnd->second++;
return fnd->first;
}
const std::string *StringManager::remove_ref(const std::string *str)
{
ITERATOR fnd;
const std::string *tmp;
if (!str)
return NULL;
// Not Found
if ((fnd = content.find(str)) == content.end())
return NULL;
// Delete
if (–fnd->second == 0)
{
update_delete_ref(str->length());
tmp = fnd->first;
content.erase(fnd);
delete tmp;
return NULL;
}
// Remove
update_remove_ref(str->length());
return NULL;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Managed String Wrappers
// Simplify string management tasks.
// Reference Managed String
// Maintains a reference to it's string manager.
// If no table has been supplied, maintain it's own string.
// Support moving between string managers.
//
// Traits: MANAGER
// const std::string *get_ref(const std::string &str, const std::string *old);
// const std::string *get_ref(const std::string *str, const std::string *old);
// const std::string *remove_ref(const std::string *str);
// – Justice
template <class MANAGER>
class ManagedStringR
{
protected:
MANAGER *table;
const std::string *data;
public:
ManagedStringR(void)
{
table = NULL;
data = NULL;
}
~ManagedStringR(void)
{
if (table)
{
if (data)
data = table->remove_ref(data);
table = NULL;
}
if (data)
delete data;
}
// String Access
inline const std::string &operator()(void)
{
return *data;
}
inline const std::string *value(void)
{
return data;
}
const char *c_str(void)
{
return data->c_str();
}
std::string::size_type size(void)
{
if (!data)
return 0;
return data->size();
}
// Set the manager.
void operator<<(MANAGER *tbl)
{
std::string buf;
if (data)
{
// Remember value
buf = *data;
// Maintain previous value
if (table)
data = table->remove_ref(data);
else
delete data;
// Update table
table = tbl;
// Update pointer
if (table)
data = table->get_ref(buf, data);
else
data = new std::string(buf);
return;
}
// Update table
table = tbl;
}
// Change value
void operator=(ManagedStringR<MANAGER> &str)
{
// No Table? Manual string handling.
if (!table)
{
if (data)
delete data;
data = new std::string(str());
return;
}
// Table string handling.
data = table->get_ref(str.value(), data);
}
// Change value
void operator=(const std::string &str)
{
// No Table? Manual string handling.
if (!table)
{
if (data)
delete data;
data = new std::string(str);
return;
}
// Table string handling.
data = table->get_ref(str, data);
}
// Change value
void operator=(const std::string *str)
{
// No Table? Manual string handling.
if (!table)
{
if (data)
delete data;
if (str)
data = new std::string(*str);
else
data = NULL;
return;
}
// Table managed strings
if (str)
data = table->get_ref(str, data);
// Null means clear reference
else
data = table->remove_ref(data);
}
};
// Provider Managed String
// Uses a provider to reference it's string manager.
// Assume table is never null.
//
// Traits: MANAGER
// const std::string *get_ref(const std::string &str, const std::string *old);
// const std::string *get_ref(const std::string *str, const std::string *old);
// const std::string *remove_ref(const std::string *str);
//
// Traits: PROVIDER
// MANAGER *manager(void);
// – Justice
template <class MANAGER, class PROVIDER>
class ManagedStringP
{
protected:
const std::string *data;
public:
ManagedStringP(void)
{
data = NULL;
}
~ManagedStringP(void)
{
PROVIDER p;
MANAGER *table;
table = p.manager();
if (data)
data = table->remove_ref(data);
}
// String Access
inline const std::string &operator()(void)
{
return *data;
}
inline const std::string *value(void)
{
return data;
}
const char *c_str(void)
{
return data->c_str();
}
std::string::size_type size(void)
{
if (!data)
return 0;
return data->size();
}
// Change value
void operator=(ManagedStringP<MANAGER,PROVIDER> &str)
{
PROVIDER p;
MANAGER *table;
table = p.manager();
// Table string handling.
data = table->get_ref(str.value(), data);
}
// Change value
void operator=(const std::string &str)
{
PROVIDER p;
MANAGER *table;
table = p.manager();
// Table string handling.
data = table->get_ref(str, data);
}
// Change value
void operator=(const std::string *str)
{
PROVIDER p;
MANAGER *table;
table = p.manager();
// Table managed strings
if (str)
data = table->get_ref(str, data);
// Null means clear reference
else
data = table->remove_ref(data);
}
};
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Managed String Wrappers
// Simplify string management tasks.
// Reference Managed String
// Maintains a reference to it's string manager.
// If no table has been supplied, maintain it's own string.
// Support moving between string managers.
//
// Traits: MANAGER
// const std::string *get_ref(const std::string &str, const std::string *old);
// const std::string *get_ref(const std::string *str, const std::string *old);
// const std::string *remove_ref(const std::string *str);
// – Justice
template <class MANAGER>
class ManagedStringR
{
protected:
MANAGER *table;
const std::string *data;
public:
ManagedStringR(void)
{
table = NULL;
data = NULL;
}
~ManagedStringR(void)
{
if (table)
{
if (data)
data = table->remove_ref(data);
table = NULL;
}
if (data)
delete data;
}
// Conversions
operator const std::string*() {return data;}
operator const char*() {return c_str();}
// String Access
inline const std::string &operator()(void)
{
static std::string BLANK = "";
if (!data)
return BLANK;
return *data;
}
inline const std::string *value(void)
{
return data;
}
// is empty?
bool empty(void)
{
if (!data)
return TRUE;
return data->empty();
}
const char *c_str(void)
{
if (!data)
return NULL;
return data->c_str();
}
std::string::size_type size(void)
{
if (!data)
return 0;
return data->size();
}
// Set the manager.
void operator<<(MANAGER *tbl)
{
std::string buf;
if (data)
{
// Remember value
buf = *data;
// Maintain previous value
if (table)
data = table->remove_ref(data);
else
delete data;
// Update table
table = tbl;
// Update pointer
if (table)
data = table->get_ref(buf, data);
else
data = new std::string(buf);
return;
}
// Update table
table = tbl;
}
// Assign value
void operator=(const std::string &str)
{
// No Table? Manual string handling.
if (!table)
{
if (data)
delete data;
data = new std::string(str);
return;
}
// Table string handling.
data = table->get_ref(str, data);
}
// Assign value
void operator=(const std::string *str)
{
// No Table? Manual string handling.
if (!table)
{
if (data)
delete data;
if (str)
data = new std::string(*str);
else
data = NULL;
return;
}
// Table managed strings
if (str)
data = table->get_ref(str, data);
// Null means clear reference
else
data = table->remove_ref(data);
}
// Assign value: Cross implementation support
void operator=(ManagedStringR<MANAGER> &str)
{
// No Table? Manual string handling.
if (!table)
{
if (data)
delete data;
data = new std::string(str());
return;
}
// Table string handling.
data = table->get_ref(str.value(), data);
}
};
// Provider Managed String
// Uses a provider to reference it's string manager.
// Assume table is never null.
//
// Traits: MANAGER
// const std::string *get_ref(const std::string &str, const std::string *old);
// const std::string *get_ref(const std::string *str, const std::string *old);
// const std::string *remove_ref(const std::string *str);
//
// Traits: PROVIDER
// MANAGER *manager(void);
// – Justice
template <class MANAGER, class PROVIDER>
class ManagedStringP
{
protected:
const std::string *data;
public:
ManagedStringP(void)
{
data = NULL;
}
~ManagedStringP(void)
{
PROVIDER p;
MANAGER *table;
table = p.manager();
if (data)
data = table->remove_ref(data);
}
// Conversions
operator const std::string*() {return data;}
operator const char*() {return c_str();}
// String Access
inline const std::string &operator()(void)
{
static std::string BLANK = "";
if (!data)
return BLANK;
return *data;
}
// String Access
inline const std::string *value(void)
{
return data;
}
// is empty?
bool empty(void)
{
if (!data)
return TRUE;
return data->empty();
}
// char buffer
const char *c_str(void)
{
if (!data)
return NULL;
return data->c_str();
}
// size
std::string::size_type size(void)
{
if (!data)
return 0;
return data->size();
}
// assign value
void operator=(const std::string &str)
{
PROVIDER p;
MANAGER *table;
table = p.manager();
// Table string handling.
data = table->get_ref(str, data);
}
// assign value
void operator=(const std::string *str)
{
PROVIDER p;
MANAGER *table;
table = p.manager();
// Table managed strings
if (str)
data = table->get_ref(str, data);
// Null means clear reference
else
data = table->remove_ref(data);
}
void operator=(ManagedStringP<MANAGER,PROVIDER> &str)
{
PROVIDER p;
MANAGER *table;
table = p.manager();
// Table string handling.
data = table->get_ref(str.value(), data);
}
};
Indeed; tries were in fact designed, as I understand it, to take advantage of prefix compression. In fact, there are even neater versions that have prefix and suffix compression, but those are much, much harder to update at run-time than the prefix-only versions.
I'm not sure how you define 'full' for a hash table, rather I think it's more precise to speak of average bucket size. A hash table's average-case lookup is O(b) where b is the average bucket size. Worst-case is O© if you let c be the largest bucket. Both of those being a function of the number of buckets and the hash function, naturally.
Well, of course:
log_2 100k ~= 20
log_2 1m ~= 23.something
The difference in time of 3 extra hops isn't very big. Unless you compound it over very very very many lookups.
Personal satisfaction. :smile: I'm not saying it's inherently better than the other options. But I would argue that it's not worse, either.
Yours is shorter, but I don't really consider either to be clearer. Your solution imposes an implementation, and since it comes first in the file (well this would be true even had it come second) I think that, to some extent, takes away from the clarity of the interface. But I'm not claiming that what I say has objective value. (I would argue that it is objectively clearer to put public members first, though, because those are what users of the class most care about. But, the marginal gain is admittedly minimal and can be solved with good IDEs anyhow…)