What's the STL'ish way of doing this?

[Jeff Dege]

I've been programming in C++ for a good long while, but there are aspects
of the language I've never needed, and hence never bothered to really
learn.

It's the curse of working on a developed product - many fundamental issues
were set long ago, and there's no reason to go back and revisit them just
because the language has come out with a new set of tools.

Case in point - the Standard Template Library. We fixed on a set of
collection classes long before the STL was available for the compilers we
were using. I've read about it, played around a bit with it, but haven't
used it on the day-to-day basis to completely internalize its capabilities
and the normal idioms with which it is used.

So I've decided to spend some time on learning the STL.

As a testbed, I'm writing some crypto programs - encrypt, decrypt,
calculate statistics to help in breaking, etc.

I'm keeping the text, both plain- and cipher-, in vector<char>'s. I've
figured out how to use algorithm copy() with stream iterator adapters to
read and write the text vectors from stdio and/or files.

I've figured out how to use algorithm transform() and ::toupper() to
change everything to uppercase, and how to use algorithm remove_if() and
::isalpha() to remove everything that isn't a letter.

What I'm trying to do next is to output the text in cipher groups, five
characters to a group, 12 groups to a line.

This works:

vactor<char> cipherText;
vector<char> outputText;

// ...

vector<char>::iterator iter;
int i;
for (iter = cipherText.begin(), i=0;
iter != cipherText.end();
iter++, i++)
{
outputText.push_back(*iter);

if (i%60 == 59)
out2Text.push_back('\n');
else if (i%5 == 4)
out2Text.push_back(' ');
}

if (i%60 != 0)
out2Text.push_back('\n');

But this seems a very non-STL'ish way of doing things.

How would folks usually approach this sort of problem, in an STL idiom?

--
The citizen sees nothing wrong, in the sense of robbing a neighbor
is wrong to him, in turning the tables upon...[government] whenever
the opportunity offers. When he steals anything from it he is only
recovering his own, with fair interest and a decent profit. Two gangs
stand thus confronted: on the one hand the gang of drones and exploiters
constituting the government, and on the other hand the body of prehensile
and enterprising citizens...The difference between the two gangs - of
professionals and amateurs - is that the former has the law on its side,
and so enjoys an unfair advantage.
- H. L. Mencken

 

[Kai-Uwe Bux]

Jeff Dege wrote:

[sni]

So I've decided to spend some time on learning the STL.

As a testbed, I'm writing some crypto programs - encrypt, decrypt,
calculate statistics to help in breaking, etc.

I'm keeping the text, both plain- and cipher-, in vector<char>'s. I've
figured out how to use algorithm copy() with stream iterator adapters to
read and write the text vectors from stdio and/or files.

I've figured out how to use algorithm transform() and ::toupper() to
change everything to uppercase, and how to use algorithm remove_if() and
::isalpha() to remove everything that isn't a letter.

What I'm trying to do next is to output the text in cipher groups, five
characters to a group, 12 groups to a line.

This works:

vactor<char> cipherText;
vector<char> outputText;

// ...

vector<char>::iterator iter;
int i;
for (iter = cipherText.begin(), i=0;
iter != cipherText.end();
iter++, i++)
{
outputText.push_back(*iter);

if (i%60 == 59)
out2Text.push_back('\n');
else if (i%5 == 4)
out2Text.push_back(' ');
}

if (i%60 != 0)
out2Text.push_back('\n');

But this seems a very non-STL'ish way of doing things.

How would folks usually approach this sort of problem, in an STL idiom?

I would introduce a custom algorithm. This way, you can abstract the
formatting from the underlying representation of the sequence:

template < typename InIter, typename OutIter >
OutIter format ( InIter from, InIter to, OutIter where ) {
unsigned long i = 0;
while ( from != to ) {
++i;
if ( i % 60 == 0 ) {
i = 0;
*where++ = '\n';
continue;
}
if ( i % 5 == 0 ) {
*where++ = ' ';
continue;
}
*where++ = *from++;
}
}

Here is a little sanity check:

#include <iterator>
#include <iostream>

int main ( void ) {
format( std::istream_iterator<char>( std::cin ),
std::istream_iterator<char>(),
std:stream_iterator<char>( std::cout ) );
}


Of course, "fromat" is less of a perfect name.


Best

Kai-Uwe Bux

 

[Noah Roberts]

How would folks usually approach this sort of problem, in an STL idiom?

Really there isn't anything I can see that is already set up to do what
you want, or could be combined to do what you want. All I would do is
take what you have and wrap it up in something generic:

template < typename InputIter, typename OutputIter >
void group(InputIter beg, InputIter end, OutputIter dest)
{
int i = 1; // not 0 so it makes later checks more intuitive

while (beg != end)
{
dest++ = beg++;
if (!(i % 60)) dest++ = '\n';
else if (!(i % 5)) dest++ = ' ';
++i;
}
}

This would then be used like so:

group(cipherText.begin(), cipherText.end(),
std::back_inserter(outputText));

This is untested but I expect it to work.

The benefits here are that group() looks like any other stl algorithm
and can accept data from any container and insert into any container
(assuming it holds values assignable from char and from whatever value
type is in the input container). It can also be used to override
values in an existing container as well as various other uses through
the use of a general output iterator instead of push_back...which the
example call ends up doing.

I'm sure there is room for improvement...

 

[Noah Roberts]

dest++ = beg++;
if (!(i % 60)) dest++ = '\n';
else if (!(i % 5)) dest++ = ' ';

All of those assignments should have dereferences.

 

[Daniel T.]

I've been programming in C++ for a good long while, but there are aspects
of the language I've never needed, and hence never bothered to really
learn.

It's the curse of working on a developed product - many fundamental issues
were set long ago, and there's no reason to go back and revisit them just
because the language has come out with a new set of tools.

Case in point - the Standard Template Library. We fixed on a set of
collection classes long before the STL was available for the compilers we
were using. I've read about it, played around a bit with it, but haven't
used it on the day-to-day basis to completely internalize its capabilities
and the normal idioms with which it is used.

So I've decided to spend some time on learning the STL.

As a testbed, I'm writing some crypto programs - encrypt, decrypt,
calculate statistics to help in breaking, etc.

I'm keeping the text, both plain- and cipher-, in vector<char>'s. I've
figured out how to use algorithm copy() with stream iterator adapters to
read and write the text vectors from stdio and/or files.

I've figured out how to use algorithm transform() and ::toupper() to
change everything to uppercase, and how to use algorithm remove_if() and
::isalpha() to remove everything that isn't a letter.

What I'm trying to do next is to output the text in cipher groups, five
characters to a group, 12 groups to a line.

This works:

vactor<char> cipherText;
vector<char> outputText;

// ...

vector<char>::iterator iter;
int i;
for (iter = cipherText.begin(), i=0;
iter != cipherText.end();
iter++, i++)
{
outputText.push_back(*iter);

if (i%60 == 59)
out2Text.push_back('\n');
else if (i%5 == 4)
out2Text.push_back(' ');
}

if (i%60 != 0)
out2Text.push_back('\n');

But this seems a very non-STL'ish way of doing things.

How would folks usually approach this sort of problem, in an STL idiom?

This could be done with for_each but I don't think it would gain you
anything (because the last bit can't be contained within the structure
passed in.)

I think the best bet would be to wrap the loop into an algorithm like
construct that is templated. That would allow you to take advantage of
the iterator concept.

template < typename InIt, typename OutIt >
void copy_groups( InIt first, InIt last, OutIt out,
unsigned major, unsigned minor ) {
unsigned i = 0;
while ( first != last ) {
*out++ = *first++;
++i;
if ( i % major == 0 )
*out++ = '\n';
else if ( i % minor == 0 )
*out++ = ' ';
}
if ( i % major != 0 )
*out++ = '\n';
}

Now you can output this to another container with a back_inserter, or
directly to a file or other output stream with an ostream_iterator. The
input can be from any container at all.

An example of use:

copy_groups( cypherText.begin(), cypherText.end(),
ostream_iterator<char>(cout), 60, 5 );

 

[Jeff Dege]

What I'm trying to do next is to output the text in cipher groups, five
characters to a group, 12 groups to a line.

This works:

[...]

But this seems a very non-STL'ish way of doing things.

How would folks usually approach this sort of problem, in an STL idiom?

I think the best bet would be to wrap the loop into an algorithm like
construct that is templated. That would allow you to take advantage of
the iterator concept.

[...]

An example of use:

copy_groups( cypherText.begin(), cypherText.end(),
ostream_iterator<char>(cout), 60, 5 );

That works fine.

Thanks.

--
Only justice, and not safety, is consistent with liberty, because safety
can be secured only by prior restraint and punishment of the innocent,
while justice begins with liberty and the concomitant presumption of
innocence and imposes punishment only after the fact.
- Jeffrey Snyder

 

[Old Wolf]

As a testbed, I'm writing some crypto programs - encrypt, decrypt,
calculate statistics to help in breaking, etc.

I'm keeping the text, both plain- and cipher-, in vector<char>'s.

I suggest a vector<unsigned char> -- because when you're
doing crypto you're often doing bit shifts and manipulations,
which are not as well defined for signed chars as they are
for unsigned chars.

You'll also find it easier to display an unsigned char

I've figured out how to use algorithm transform() and ::toupper() to
change everything to uppercase, and how to use algorithm remove_if() and
::isalpha() to remove everything that isn't a letter.

Be aware that toupper and isalpha are locale-specific, and
aren't very useful for some international situations.

What I'm trying to do next is to output the text in cipher groups, five
characters to a group, 12 groups to a line.

vector<char>::iterator iter;
int i;
for (iter = cipherText.begin(), i=0;
iter != cipherText.end();
iter++, i++)
{
outputText.push_back(*iter);

if (i%60 == 59)
out2Text.push_back('\n');
else if (i%5 == 4)
out2Text.push_back(' ');
}

if (i%60 != 0)
out2Text.push_back('\n');

Well, firstly I would not use two iterators! Either use 'i' or
'iter'. Since you have a vector there's nothing wrong with
using
cipherText
instead of
*iter
and it will save you a lot of typing. Don't worry about
whether one is more optimal than the other or not --
optimizing array indices is something that compilers
have been good at since day one ... and I think it
would be better at optimizing an int than an interator!

Is outputText meant to be different to out2Text ?

Finally, if you are going to use STL iterators, then
++iter
is preferred to
iter++
becaus the latter requires a copy of the iterator to
be made, so that it can be returned -- so the former
is generally more efficient. (Another micro-optimization,
but people seem to like this one).

 

[Jeff Dege]

I suggest a vector<unsigned char> -- because when you're
doing crypto you're often doing bit shifts and manipulations,
which are not as well defined for signed chars as they are
for unsigned chars.

When I get beyond mod-26 Caesar, Vignere, and Playfair, I will certainly
need to deal with that.

Be aware that toupper and isalpha are locale-specific, and aren't very
useful for some international situations.

Yep. The whole upper-lower case distinction isn't very portable. But
then, mod-26 encryption isn't very portable.

Well, firstly I would not use two iterators! Either use 'i' or 'iter'.
Since you have a vector there's nothing wrong with using
cipherText
instead of
*iter
and it will save you a lot of typing. Don't worry about whether one is
more optimal than the other or not -- optimizing array indices is
something that compilers have been good at since day one ... and I think
it would be better at optimizing an int than an interator!

Something I will keep in mind.

--
One bleeding-heart type asked me in a recent interview if I did not
agree that "violence begets violence." I told him that it is my earnest
endeavor to see that it does. I would like very much to ensure - and
in some cases I have - that any man who offers violence to his fellow
citizen begets a whole lot more in return than he can enjoy.
- Jeff Cooper

 

[Daniel T.]

What I'm trying to do next is to output the text in cipher groups, five
characters to a group, 12 groups to a line.

This works:

[...]

But this seems a very non-STL'ish way of doing things.

How would folks usually approach this sort of problem, in an STL idiom?

I think the best bet would be to wrap the loop into an algorithm like
construct that is templated. That would allow you to take advantage of
the iterator concept.

[...]

An example of use:

copy_groups( cypherText.begin(), cypherText.end(),
ostream_iterator<char>(cout), 60, 5 );

That works fine.

Here's an even more interesting way to do it. This is more complicated,
but it allows more formatting options and lets you wow your friends.

template < typename T, typename OutIt >
class formatted_out_t:
public std::iterator< std:utput_iterator_tag,
void, void, void, void >
{
public:
formatted_out_t( OutIt out, char pad, unsigned dist ):
out( out ),
pad( pad ),
dist( dist ),
cur( 0 )
{ }
void operator=( T t )
{
*out = t;
++cur;
if ( cur % dist == 0 )
*out = pad;
}
formatted_out_t& operator*() { return *this; }
formatted_out_t& operator++() { return *this; }
private:
OutIt out;
char pad;
unsigned dist;
unsigned cur;
};

template < typename T, typename OutIt >
formatted_out_t<T, OutIt> formatted_out( OutIt it, char pad, unsigned
dist )
{
return formatted_out_t<T, OutIt>( it, pad, dist );
}

using namespace std;

int main() {
vector<char> vec( 65, 'b' );
ostringstream oss;
copy( vec.begin(), vec.end(),
formatted_out<char>(
formatted_out<char>(
ostream_iterator<char>( oss ), '\n', 72 ), ' ', 5 ) );
assert( oss.str() == "bbbbb bbbbb bbbbb bbbbb bbbbb bbbbb bbbbb bbbbb
bbbbb bbbbb bbbbb bbbbb \nbbbbb " );
}

Now a question for those more knowledgable than I. If I made a typedef
for the above like this:

typedef formatted_out_t<char, formatted_out_t<char,
std:stream_iterator<char, char, std::char_traits<char> > > >
CypherFormat;

How would I create an object of type CypherFormat?

 

[Greg Buchholz]

I'm keeping the text, both plain- and cipher-, in vector<char>'s. I've
figured out how to use algorithm copy() with stream iterator adapters to
read and write the text vectors from stdio and/or files.

I've figured out how to use algorithm transform() and ::toupper() to
change everything to uppercase, and how to use algorithm remove_if() and
::isalpha() to remove everything that isn't a letter.

What I'm trying to do next is to output the text in cipher groups, five
characters to a group, 12 groups to a line.

/*
If you don't want to make another copy of you data just for output,
you could instead make a wrapper around the iterator which does
the formatting for you.
*/

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>

using namespace std;
char sp = ' ';
char nl = '\n';

template<class Iter> class Formated_Iter : public iterator_traits<Iter>
{
typename std::iterator_traits<Iter>::difference_type pos;
Iter i;

public:
typedef typename std::input_iterator_tag iterator_category;

Formated_Iter(Iter init) : i(init), pos(0) {};

typename std::iterator_traits<Iter>::reference operator*() const
{
return (pos%5==4) ? sp : (pos%60==59) ? nl : *i;
}

Formated_Iter& operator++()
{
if(not (pos%5==4 or pos%60==59))
++i;
++pos;
return *this;
}

friend bool operator!=(const Formated_Iter& a, const Formated_Iter&
b)
{
return a.i!=b.i;
}

// You'll probably also want to implement operator==, postfix ++,
->, etc.
};

int main(int argc, char* argv[])
{
string txt = "Thequickbrownfoxjumpsoverthelazydog.\n";
vector<char> cipherText(txt.begin(),txt.end());

typedef Formated_Iter<vector<char>::iterator> wrap;

copy(wrap(cipherText.begin()),
wrap(cipherText.end()),ostream_iterator<char>(cout, ""));

return 0;
}