back_inserter & basic_string

[Mark A. Gibbs]

I have a string conversion function that looks something like this
(apologies, but I cannot post the actual code):

whar_t char_to_wchar(c har);

wstring to_wstring(cons t string& s)
{
wstring result(s.length (), '\0');

transform(s.beg in(), s.end(), result.begin(), ptr_fun(char_to _wchar));

return result;
}

Now, I wonder if I might gain some improvement if instead of filling the
string with null characters then overwriting them I use:

wstring result;
result.reserve( s.length());
transform(s.beg in(), s.end(), back_inserter(r esult),
ptr_fun(char_to _wchar));

The only problem is that back_insert_ite rator apparently uses
push_back(), which is fine for most containers, but not for strings. So
I was wondering whether specializing
back_insert_ite rator<basic_str ing<Char> > to use operator+= instead of
push_back was a good idea.

If not, I can always just write a custom string_back_ins ert_iterator,
but would it be a good idea then to write a specialization of
back_inserter<b asic_string<Cha r> > that returns the custom iterator?

On a completely unrelated topic, something else occurred to me as I was
reviewing the code (which led to my investigation of back_inserter). Is
the use of length() instead of size() potentially dangerous? Would the
original code be safer if I either replaced s.length() with s.size() or
replaced the call to s.end() with advance(s.begin (), s.length())?

Mark

[Jonathan Turkanis]

"Mark A. Gibbs" <gi*******@xrog ersx.com> wrote in message
news:hp******** *******@twister 01.bloor.is.net .cable.rogers.c om...

I have a string conversion function that looks something like this
(apologies, but I cannot post the actual code):

whar_t char_to_wchar(c har);

wstring to_wstring(cons t string& s)
{
wstring result(s.length (), '\0');

transform(s.beg in(), s.end(), result.begin(), ptr_fun(char_to _wchar));
return result;
}
You're calling char_to_wchar once for each character. This can be
expensive. If you call this function a lot, its better to make a table
which maps narrow characters to wide characters. Then you can do all
the conversion in one loop, without any function calls.

You can initialize the table the first time through:

#include <climits>
#include <locale>
#include <string>

void init_conversion _table(wchar_t* table)
{
using namespace std;
const ctype<wchar_t>& ct =
use_facet< std::ctype<wcha r_t> >(locale::class ic());
for (int i = CHAR_MIN; i <= CHAR_MAX; ++i)
table[i - CHAR_MIN] = ct.widen(static _cast<char>(i)) ;
}

std::wstring to_wstring(cons t std::string& s)
{
using namespace std;
wchar_t table[CHAR_MAX - CHAR_MIN + 1];
static bool first = true;
if (first) {
first = false;
init_conversion _table(table);
}
size_t len = s.size();
wstring result(len, '\0');
for (size_t i = 0; i < len; ++i)
result[i] = table[static_cast<int >(s[i]) - CHAR_MIN];
return result;
}

(Loosely adapted from "How to do case-insensitive string comparison"
by Matt Austern.)

The multithreaded case is more complex (and platform dependent).

Now, I wonder if I might gain some improvement if instead of filling the string with null characters then overwriting them I use:

wstring result;
result.reserve( s.length());
transform(s.beg in(), s.end(), back_inserter(r esult),
ptr_fun(char_to _wchar));

The only problem is that back_insert_ite rator apparently uses
push_back(), which is fine for most containers, but not for strings.
basic_string has push_back. What's wrong with it?
So
I was wondering whether specializing
back_insert_ite rator<basic_str ing<Char> > to use operator+= instead of push_back was a good idea.

If not, I can always just write a custom string_back_ins ert_iterator, but would it be a good idea then to write a specialization of
back_inserter<b asic_string<Cha r> > that returns the custom iterator?
Neither is necessary.

On a completely unrelated topic, something else occurred to me as I was reviewing the code (which led to my investigation of back_inserter). Is the use of length() instead of size() potentially dangerous? Would the original code be safer if I either replaced s.length() with s.size() or replaced the call to s.end() with advance(s.begin (), s.length())?

size and length are synonymous.

Jonathan

[Jonathan Turkanis]

"Jonathan Turkanis" <te******@kanga roologic.com> wrote in message
news:c1******** *****@ID-216073.news.uni-berlin.de...

using namespace std;
wchar_t table[CHAR_MAX - CHAR_MIN + 1];
static bool first = true;

table should be static too.

Jonathan

[Mark A. Gibbs]

Jonathan Turkanis wrote:

You're calling char_to_wchar once for each character. This can be
expensive. If you call this function a lot, its better to make a table
which maps narrow characters to wide characters. Then you can do all

Actually, that's a damned good idea, and I guess the same table could be
used with a little reworking for the reverse (wchar_to_char) . I'll work
with that soultion instead.

The only problem is that back_insert_ite rator apparently uses
push_back() , which is fine for most containers, but not for strings.

basic_string has push_back. What's wrong with it?

Really? Maybe it's just missing from the rogue wave implementation - or
even just the documentation in Borland C++ Builder 5.

replaced the call to s.end() with advance(s.begin (), s.length())?

size and length are synonymous.

Actually, I recall reading that they are not (though I can't find the
reference now, I think it was in Kalev's ISO C++ programmer's handbook).
From what I recall, size and length are related in a similar way to
c_str and data, in that c_str must return a pointer to a null-terminated
character sequence while all data has to do is return a pointer to the
internal data (which may or may not be null-terminated). size returns
the amount of character data in the string while length returns
strlen(c_str()) , so it's possible for size to be bigger than length, but
not the opposite.

At any rate, if they are syonymous, why bother to have them both?
Wouldn't it be wiser to advocate using size all the time instead of
length so that other containers could just as easily be swapped in?

But I've heard so much contradictory information on the STL - especially
in regards to international support and allocators - that I honestly
don't know what is really true anymore.

Mark

[Jonathan Turkanis]

"Mark A. Gibbs" <gi*******@xrog ersx.com> wrote in message
news:Fq******** *****@news01.bl oor.is.net.cabl e.rogers.com...

Jonathan Turkanis wrote:

You're calling char_to_wchar once for each character. This can be
expensive. If you call this function a lot, its better to make a table

which maps narrow characters to wide characters. Then you can do all

Actually, that's a damned good idea,
Thanks.
and I guess the same table could be
used with a little reworking for the reverse (wchar_to_char) . I'll work with that soultion instead.
You'll need to modifiy it a bit. If you try applying the same
technique literally, you'll get a really huge table, most entries of
which contain a narrow character represnting an invalid conversion.
The only problem is that back_insert_ite rator apparently uses
push_back() , which is fine for most containers, but not for

strings.

basic_string has push_back. What's wrong with it?
Really? Maybe it's just missing from the rogue wave implementation -

or even just the documentation in Borland C++ Builder 5.
replaced the call to s.end() with advance(s.begin (), s.length())?
size and length are synonymous.

Actually, I recall reading that they are not (though I can't find

the reference now, I think it was in Kalev's ISO C++ programmer's handbook). From what I recall, size and length are related in a similar way to
c_str and data, in that c_str must return a pointer to a null-terminated character sequence while all data has to do is return a pointer to the internal data (which may or may not be null-terminated). size returns the amount of character data in the string while length returns
strlen(c_str()) , so it's possible for size to be bigger than length, but not the opposite.
length is specified in the standard this way:

Returns: size().

size() was added for consistency with the other containers. length()
seems more natural, to many, when dealing with strings. I always use
size().

Jonathan

Mark

[Mark A. Gibbs]

Jonathan Turkanis wrote:

"Mark A. Gibbs" <gi*******@xrog ersx.com> wrote in message
news:Fq******** *****@news01.bl oor.is.net.cabl e.rogers.com...

Actually, that's a damned good idea,
Thanks.

Welcome.
You'll need to modifiy it a bit. If you try applying the same
technique literally, you'll get a really huge table, most entries of
which contain a narrow character represnting an invalid conversion.
Yes, I was thinking of something like:

namespace {

const int TABLE_SIZE = CHAR_MAX - CHAR_MIN + 1;

const wchar_t* get_table() {
static bool first = true;
static wchar_t table[TABLE_SIZE];

if (first) {
// Init the table as you described
first = false;
}

return table;
}

}

wstring to_wstring(cons t string& s) {
const wchar_t* table = get_table();
size_t size = s.size();
wstring result;

result.reserve( size);

for(size_t i = 0; i < size; ++i) {
result += table[static_cast<int >(s[i]) - CHAR_MIN];
}

return result;
}

string to_string(const wstring& s) {
const wchar_t* table = get_table();
const wchar_t* end = table + TABLE_SIZE;
const char def_char = '?';
size_t size = s.size();
string result;

result.reserve( size);

for(size_t i = 0; i < size; ++i) {
const wchar_t* p = find(table, end, s[i]);
result += (p == end) ? def_char :
static_cast<cha r>(distance(tab le, p) + CHAR_MIN);
}

return result;
}

You mentioned that there might be multithreading issues, but I think
that if I were to write get_table as:

const wchar_t* get_table()
{
static bool first = true;
static wchar_t table[TABLE_SIZE];

if (first)
{
platform_specif ic_mutex_or_cri tical_section_o bject x;

if (first)
{
// Init the table as you described
first = false;
}

// x releases on destruction
}

return table;
}

Then those problems go away.
length is specified in the standard this way:

Returns: size().

size() was added for consistency with the other containers. length()
seems more natural, to many, when dealing with strings. I always use
size().

Ah, thanks for clearing that up. I would probably have been using size
myself all along if I knew that.

I'm curious to know if there is some kind of definitive resource out
there on the ISO standard besides the standard itself. I've looked at a
copy of the standard and it's (understandably ) wordy and a little obtuse
in parts (to me at least). And of course, I don't have a copy at home.
There's a lot of stuff out there that's either outdated or just plain
wrong (a fresh example is Borland's online help).

I mean, I looked through the comp.lang.c++ FAQ's suggested references
(Item 36.4) and:

1.) Claims basic_string has no push_back
2.) Dead link
3.) Doesn't even mention basic_string and appears to have been last
modified in 1996.
4.) Has a disclaimer in 3cm high, bold, red letters that the reference
is way out of date.
5.) Agrees with your assertion of the existence of
basic_string::p ush_back, but in the same breath talks about rope<T,
Allocator>. (To be fair, it explicitly states that rope is an extension,
although how can I be *sure* that basic_string::p ush_back is not?)

Is there anything out there online that is accurate and yet does not
have a bunch of non-standard extension stuff thrown in?

Mark

[Jonathan Turkanis]

"Mark A. Gibbs" <gi*******@xrog ersx.com> wrote in message
news:UW******** **********@twis ter01.bloor.is. net.cable.roger s.com...

Jonathan Turkanis wrote:

"Mark A. Gibbs" <gi*******@xrog ersx.com> wrote in message
news:Fq******** *****@news01.bl oor.is.net.cabl e.rogers.com...

Actually, that's a damned good idea,
Thanks.

Welcome.

You'll need to modifiy it a bit. If you try applying the same
technique literally, you'll get a really huge table, most entries of which contain a narrow character represnting an invalid conversion.
Yes, I was thinking of something like:

namespace {

const int TABLE_SIZE = CHAR_MAX - CHAR_MIN + 1;

const wchar_t* get_table() {
static bool first = true;
static wchar_t table[TABLE_SIZE];

if (first) {
// Init the table as you described
first = false;
}

return table;
}

}

<snip>
string to_string(const wstring& s) {
const wchar_t* table = get_table();
const wchar_t* end = table + TABLE_SIZE;
const char def_char = '?';
size_t size = s.size();
string result;

result.reserve( size);

for(size_t i = 0; i < size; ++i) {
const wchar_t* p = find(table, end, s[i]);
result += (p == end) ? def_char :
static_cast<cha r>(distance(tab le, p) + CHAR_MIN);
}

return result;
}
I'd use a map instead. The linear search through the table could be
rather slow. But the map might be even slower than just calling the
conversion function for each character. You'd have to compare them.

You mentioned that there might be multithreading issues, but I think
that if I were to write get_table as:

const wchar_t* get_table()
{
static bool first = true;
static wchar_t table[TABLE_SIZE];

if (first)
{
platform_specif ic_mutex_or_cri tical_section_o bject x;

if (first)
{
// Init the table as you described
first = false;
}

// x releases on destruction
}

return table;
}
That's the way to do it.

Then those problems go away.

length is specified in the standard this way:

Returns: size().

size() was added for consistency with the other containers.

length() seems more natural, to many, when dealing with strings. I always use size().

Ah, thanks for clearing that up. I would probably have been using

size myself all along if I knew that.

I'm curious to know if there is some kind of definitive resource out
there on the ISO standard besides the standard itself. I've looked at a copy of the standard and it's (understandably ) wordy and a little obtuse in parts (to me at least). And of course, I don't have a copy at home. There's a lot of stuff out there that's either outdated or just plain wrong (a fresh example is Borland's online help).

I think Nicolai Josuttis's The C++ Standard Library is the best work
library reference. It doesn't cover the other aspects of the standard.

I'd also get a copy of the standard( 2nd edition). It's only $18. Most
of it, particularly the library specification, is surprisingly easy to
read. Parts are really obscure, though.

Jonathan

[Mark A. Gibbs]

Jonathan Turkanis wrote:

I'd also get a copy of the standard( 2nd edition). It's only $18. Most
of it, particularly the library specification, is surprisingly easy to
read. Parts are really obscure, though.

Wow, I had heard that it was CDN$300. I just read the relevant section
in the FAQ and I see where my confusion came from (ISO vs. ANSI). $18
(~CDN$25-30) is definitely worth the price for admission. Thanks for the
tip.

Mark

[Jonathan Turkanis]

"Mark A. Gibbs" <gi*******@xrog ersx.com> wrote in message
news:9d******** **********@twis ter01.bloor.is. net.cable.roger s.com...

Jonathan Turkanis wrote:

I'd also get a copy of the standard( 2nd edition). It's only $18. Most of it, particularly the library specification, is surprisingly easy to read. Parts are really obscure, though.
Wow, I had heard that it was CDN$300. I just read the relevant

section in the FAQ and I see where my confusion came from (ISO vs. ANSI). $18 (~CDN$25-30) is definitely worth the price for admission. Thanks for the tip.

Glad to help. Last I heard, the version available at the ansi store
had formatting problems, but this version was clean:

http://www.techstreet.com/cgi-bin/de...uct_id=1143945

Jonathan