encryption problem

W

Wilson

i am learning to program using c++ and was set a task of making a
simple encryption algorithim. I choose to start with one where simply
each letter is replaced with its equivilent in the alphabet when
written backmards, i am hoping to make this more complex soon. Below
is the program i wrote but it does not work, it simply returns the
exact same text you enter. Could you please advise on how to sort
this, and also suggest any ways of generating random letters, for
future refernce.

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

char alphabet[27] = "ZYXWVUTSRQPONMLKJIHGFEDCBA";
char plain_text[27];
int string_length;

int main()
{
cout << "text: ";
cin >> plain_text;
string_length = strlen(plain_text);
for(int i=0; i < string_length; i++)
{
plaintext = alphabet;
}
cout << plain_text;
system ("PAUSE");
 
O

osmium

Wilson said:
i am learning to program using c++ and was set a task of making a
simple encryption algorithim. I choose to start with one where simply
each letter is replaced with its equivilent in the alphabet when
written backmards, i am hoping to make this more complex soon. Below
is the program i wrote but it does not work, it simply returns the
exact same text you enter. Could you please advise on how to sort
this, and also suggest any ways of generating random letters, for
future refernce.

It didn't do what you say it does for me. If I type mary I get back ZYXW.
The first four letters in the backwards alphabet you provided as a literal.
That's what the code said it should do. The code says: replace the first
letter with Z, the next letter with Y and so on. You don't even examine
the *value* of the character read. Think about it and try again. The
random letter issue is covered in the FAQ for comp.lang.c

I don't think it is a good idea to write an enciphered message, even if done
properly, in a variable named plain_text. It is confusing. If you only
have a few hundred bytes of memory, name it buffer. If you can cram it in,
create a new variable named cipher_text and put the enciphered text there.
Also, cut and paste next time, what you posted does not compile.
#include <iostream>
#include <string>
using namespace std;

char alphabet[27] = "ZYXWVUTSRQPONMLKJIHGFEDCBA";
char plain_text[27];
int string_length;

int main()
{
cout << "text: ";
cin >> plain_text;
string_length = strlen(plain_text);
for(int i=0; i < string_length; i++)
{
plaintext = alphabet;
}
cout << plain_text;
system ("PAUSE");
 
D

dogatemycomputer

I'm a newbie too so it took me a few minutes to realize what went
wrong with your code. I'm sure i'll get flamed (especially when the
blind is leading the blind) but i'm hoping someone will correct both
of us so we can do better next time.

Here is your code:



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

char alphabet[27] = "ZYXWVUTSRQPONMLKJIHGFEDCBA";
char plain_text[27];
int string_length;

int main()
{
cout << "text: ";
cin >> plain_text; // plain_text = "test"
string_length = strlen(plain_text); //string_length is 4;
for(int i=0; i < string_length; i++) // do this 4 times
{
plaintext = alphabet; // take alphabet which is Z, then Y,
then X then W and assign it to plaintext[0-4] which equates too ZYXW;
}

cout << plain_text; // output ZYXW
system ("PAUSE");




-----------------------------


Here are my thoughts:

#include <iostream>
#include <string.h>
using namespace std;

// this should be a list of all possible characters that can be
converted
char decrypted[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// list of the corresponding converted text
char encrypted[27] = "ZYXWVUTSRQPONMLKJIHGFEDCBA"; //encrypted key
char plain_text[80]; //plain text string
char converted_text[80]; //converted string for output
int string_length; // initialize the string

int main()
{

cout << "text: "; // enter some text
cin >> plain_text; //assign the array of text to plain_text
string_length = strlen(plain_text); //find the length of the text
string entered by the user


for (int i=0; i<string_length; ++i) // for the current character in
the string (i is the current character)
{
for (int j=0; j<(strlen(decrypted)); j++) //for the number of
possible decrypted characters
{
if (decrypted[j] == plain_text) //if the current character
matches in the possible list of decrypted characters
{
converted_text = encrypted[j]; //then take the corresponding
encrypted character and assign it to the converted text string

}
}
}
cout << converted_text << "\n";
return 0;
}

------------------------

Here are my thoughts:

- i used a "decrypted" but incomplete list of possible characters
entered. Its probably a better idea to compare every character with
the entire list of ascii characters and output an offset (rather than
depending on a 1-to-1 translation on manually entered character list)
That shouldn't be too difficult.

- i'm not sure i'm adhering to any proper coding practices by using a
variable from one for-loop as a basis for comparison in a nested for
loop. Should these "constructs" (is that an appropriate word?) allow
mingling of variables?

- should I move the for-loops and character comparisons to a function
outside of main()?

Any other critiques would be appreciated. Please keep in mind i'm a
newbie so additional explanation and examples would be helpful.

Thanks!
 
B

BobR

I'm a newbie too so it took me a few minutes to realize what went
wrong with your code. I'm sure i'll get flamed (especially when the
blind is leading the blind) but i'm hoping someone will correct both
of us so we can do better next time.
Here is your code:
#include <iostream>
#include <string>
-----------------------------
Here are my thoughts:

#include <iostream>
#include <string.h>
using namespace std; // for pure laziness

// this should be a list of all possible characters that can be
converted
char decrypted[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// list of the corresponding converted text
char encrypted[27] = "ZYXWVUTSRQPONMLKJIHGFEDCBA"; file://encrypted key
char plain_text[80]; file://plain text string
char converted_text[80]; file://converted string for output
int string_length; // initialize the string

int main(){
cout << "text: "; // enter some text
cin >> plain_text; file://assign the array of text to plain_text
string_length = strlen(plain_text); file://find the length of the text
string entered by the user

for (int i=0; i<string_length; ++i){ // for the current character in
the string (i is the current character)
for (int j=0; j<(strlen(decrypted)); j++){ file://for the number of
possible decrypted characters
if (decrypted[j] == plain_text){ file://if the current character
matches in the possible list of decrypted characters
converted_text = encrypted[j]; file://then take the corresponding
encrypted character and assign it to the converted text string
}
}
}
cout << converted_text << "\n";
return 0;
}
------------------------

Here are my thoughts:

- i used a "decrypted" but incomplete list of possible characters
entered. Its probably a better idea to compare every character with
the entire list of ascii characters and output an offset (rather than
depending on a 1-to-1 translation on manually entered character list)
That shouldn't be too difficult.


See below.
- i'm not sure i'm adhering to any proper coding practices by using a
variable from one for-loop as a basis for comparison in a nested for
loop. Should these "constructs" (is that an appropriate word?) allow
mingling of variables?

The lines are so garbaged by your long comments, I don't feel like picking
it apart. If I understand what you were asking, I think the answer is "yes".
- should I move the for-loops and character comparisons to a function
outside of main()?

Why not. Everything else is outside of main()! (global vars bad!).
Any other critiques would be appreciated. Please keep in mind i'm a
newbie so additional explanation and examples would be helpful.
Thanks!

The OP included <string>, you should use that.

#include <iostream>
#include <string>
#include <algorithm>

int main(){
// - maintain one list -
std::string decrypted( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
// - copy and reverse the list -
std::string encrypted( decrypted );
std::reverse( encrypted.begin(), encrypted.end() );

std::cout<<encrypted<<std::endl;
std::cout<<"encrypted 9th char is:"
<<encrypted.at( 8 )<<std::endl; // zero based index
return 0;
} // main()

Now look up 'std::string find()', and use it with your first 'thought'
above.
Hint: you will NOT use nested loops in the encrypt/decrypt. Only 'scan' the
input string/c-string.
http://www.dinkumware.com/manuals/.

If you get stuck, post back here for help.

If you read this old thread, you may get some more ideas.
// - Original Message -
From: Protoman <[email protected]>
Newsgroups: comp.lang.c++
Sent: Monday, July 02, 2007 8:00 PM
Subject: Any way to make this code more compact, and/or be able to change at
runtime?

But remember, I didn't tell you.
[ I don't want to get yelled at for doing someones homework/exercises. <G>]
 
J

Juha Nieminen

I'm a newbie too so it took me a few minutes to realize what went
wrong with your code. I'm sure i'll get flamed (especially when the
blind is leading the blind) but i'm hoping someone will correct both
of us so we can do better next time.

Your code is really horrific indeed.
This has little to do with C++ specifically and much more to do
with (procedural) programming in general, and I'm not completely sure
how on-topic this is in this group, but anyways.
#include <iostream>
#include <string.h>

The header for C string manipulation functions is <cstring>,
not said:
using namespace std;

Just a piece of advice: Even though it's tempting to write that
"using" line, don't. It will only teach you bad habits in the long
run. Those namespace prefixes are not so tedious.

// this should be a list of all possible characters that can be
converted
char decrypted[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

What if you want to also support lowercase characters?

The <cctype> standard library has many handy functions for
checking and converting characters. For example, isalpha(),
isupper(), islower(), tolower(), toupper() and so on. You should
get acquainted with those.

Anyways, even though technically not supported by the C++ standard
(as far as I know), in practice 100% of systems (at least those which
you care) use the ASCII codes for the first 127 characters in the
character set (even if the input is UTF-8 encoded).
Add to this that in C++ for example 'A' means the ascii value of
that character, and suddenly you can check if a certain character
is, for example, between A and Z by a simple (c >= 'A' && c <= 'Z').

Another feature in C++ is that characters are simply integer values
and thus support integer arithmetic. This allows an ample set of nice
conversions to be done with simple math. For example, if you want to
map 'A' to 'Z', 'B' to 'Y' and so on, you can do it with a simple
'Z'-(c-'A'). The (c-'A') part maps the character from the range
'A'-'Z' to the range 0-25, and this value is then substracted from
the ascii value 'Z'. The result is that 'A'...'Z' gets mapped to
'Z'...'A'.

If you want to make a rotation instead of an inversion, you can
simply perform an addition and modulo, but I'll leave that for now.

Another nice trick is that since character values are just integers,
character values can be used to index arrays. Thus if you have checked
that c is indeed inside the range 'A'...'Z', then you can use (c-'A')
(which, as mentioned above, results in values between 0 and 25) to
index an array of 26 elements. Thus if c equals 'A' the first element
will be indexed, 'B' would index the second one and so on.
char plain_text[80]; //plain text string

Have you ever heard of the term "buffer overflow"? That kind of
code you have written above is exactly one of the causes. Don't do it.

You should *always* think: "What happens if the user enters more
than 80 characters?" And no, the solution is not to increase the
size of that array to some thousands of characters.

In C++ there's no need to use fixed-sized arrays for text because
there's this useful class called std::string. It will dynamically
grow itself as necessary and thus buffer overflows can be avoided.
Another plus side is that std::string is way easier to use than
char arrays and C string functions. It's usually a lot faster, too.
cout << "text: "; // enter some text
cin >> plain_text; //assign the array of text to plain_text

Here is the critical point. What happens if the user enters more
than 80 characters?
You don't want to do that. You want to do this:

std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);

Now it doesn't matter how much text the user writes. It won't cause
a buffer overflow.
string_length = strlen(plain_text); //find the length of the text
string entered by the user

First advantage of using std::string: That line is obsolete.

plainText.length() will give the length of the string when you need
it. And way faster than strlen().
for (int i=0; i<string_length; ++i) // for the current character in
the string (i is the current character)
{
for (int j=0; j<(strlen(decrypted)); j++) //for the number of
possible decrypted characters
{
if (decrypted[j] == plain_text) //if the current character
matches in the possible list of decrypted characters
{
converted_text = encrypted[j]; //then take the corresponding
encrypted character and assign it to the converted text string

}
}
}


Have you given any thought about how inefficient that code is?

For each character in the input you loop through the "decrypted"
array, each time recalculating its size with strlen. Even if the
compiler is so smart as to be able to optimize the strlen outside
the loops you are still making 26 loops for each character in the
input. This is completely unnecessary and needlessly complicated.

You don't need to traverse any "decrypted" array. By doing so
you are actually calculating (plain_text-'A'), which accomplishes
the same thing with one line and way faster.

Consider this:

std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);
std::string converted;

for(unsigned i = 0; i < plainText.length(); ++i)
{
char c = plainText;
if(c >= 'A' && c <= 'Z')
converted += encrypted[c-'A'];
else
converted += plainText;
}

std::cout << converted << "\n";

In fact, if you are simply making the conversion and don't need the
original input text for anything else, you could as well modify the
original string instead of creating a new one, saving a few lines:

std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);

for(unsigned i = 0; i < plainText.length(); ++i)
{
char c = plainText;
if(c >= 'A' && c <= 'Z')
plainText = encrypted[c-'A'];
}

std::cout << plainText << "\n";

Of course that allows the "encrypted" array to contain *anything*.
If you are simply making a character inversion, you can do it without
that array:

std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);

for(unsigned i = 0; i < plainText.length(); ++i)
{
char c = plainText;
if(c >= 'A' && c <= 'Z')
plainText = 'Z' - (c-'A');
}

std::cout << plainText << "\n";
 
B

BobR

Juha Nieminen said:
Here is the critical point. What happens if the user enters more
than 80 characters?
You don't want to do that. You want to do this:

std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);

Now it doesn't matter how much text the user writes. It won't cause
a buffer overflow.

Well, it will:

plainText.max_size() == 1073741820 [Intel, win98, MinGW].

Not too many people type that much into one line though. <G>
[ at the old (80 char line) x (66 lines per page), thats over200k pages.
So, be sure to tell your users to limit the input to "one book per line"!
:-} ]

First advantage of using std::string: That line is obsolete.

plainText.length() will give the length of the string when you need
it. And way faster than strlen().

Or 'plainText.size()'
[On my GCC(MinGW) .length() just returns .size(). ]

Sure hope that wasn't homework you just furnished them. <G>
<holey crap, I've done that. I better take that back.>
On second thought, ignore the snip about homework!
 
K

Kai-Uwe Bux

BobR said:
Juha Nieminen said:
Here is the critical point. What happens if the user enters more
than 80 characters?
You don't want to do that. You want to do this:

std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);

Now it doesn't matter how much text the user writes. It won't cause
a buffer overflow.

Well, it will:

plainText.max_size() == 1073741820 [Intel, win98, MinGW].

Not too many people type that much into one line though. <G>
[ at the old (80 char line) x (66 lines per page), thats over200k pages.
So, be sure to tell your users to limit the input to "one book per line"!
:-} ]

No, it won't cause a buffer overflow. Instead, getline() will stop after
max_size() characters and then set the failbit of the stream. [21.3.7.9/6]


Best

Kai-Uwe Bux
 
J

Jerry Coffin

[ ... ]
Anyways, even though technically not supported by the C++ standard
(as far as I know), in practice 100% of systems (at least those which
you care) use the ASCII codes for the first 127 characters in the
character set (even if the input is UTF-8 encoded).
Add to this that in C++ for example 'A' means the ascii value of
that character, and suddenly you can check if a certain character
is, for example, between A and Z by a simple (c >= 'A' && c <= 'Z').

OTOH, by using std::isupper, you get portability and often even better
efficiency -- not to mention more readable code. Then again, with other
methods of mapping, you don't need to use the step at all.
Another feature in C++ is that characters are simply integer values
and thus support integer arithmetic. This allows an ample set of nice
conversions to be done with simple math. For example, if you want to
map 'A' to 'Z', 'B' to 'Y' and so on, you can do it with a simple
'Z'-(c-'A'). The (c-'A') part maps the character from the range
'A'-'Z' to the range 0-25, and this value is then substracted from
the ascii value 'Z'. The result is that 'A'...'Z' gets mapped to
'Z'...'A'.

Once again, there's another method that is not only portable, but also
likely to be more efficient as a rule -- just build a table to look up
your translated values, and you get get it all, so to speak.

[ ... ]
char plain_text[80]; //plain text string

Have you ever heard of the term "buffer overflow"? That kind of
code you have written above is exactly one of the causes. Don't do it.

A fixed array does _not_ necessarily have much (if anything) to do with
buffer overflows. Using something like fgets, it's entirely possible to
do so with complete safety. Don't get me wrong: I'm not arguing against
using a string and getline, just pointing out that you're overstating
the shortcomings of fixed-size arrays in this situation.
In C++ there's no need to use fixed-sized arrays for text because
there's this useful class called std::string. It will dynamically
grow itself as necessary and thus buffer overflows can be avoided.

The buffer overflow is avoided, but replaced with the potential for a
denial of service attack, which is not necessarily a huge improvement.
Another plus side is that std::string is way easier to use than
char arrays and C string functions. It's usually a lot faster, too.


Here is the critical point. What happens if the user enters more
than 80 characters?

It generally still won't cause a problem. The real problem here is that
this only attempts to read and encrypt the first word entered by the
user. A buffer overflow results only when/if the user enters 80
characters or more without any whitespace.
You don't want to do that. You want to do this:

std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);

Now it doesn't matter how much text the user writes. It won't cause
a buffer overflow.

This is a real improvement, but there's quite a bit more to it than
avoiding a buffer overflow.

[ ... ]
plainText.length() will give the length of the string when you need
it. And way faster than strlen().

It may be faster -- it certainly _can_ be. Then again, in some
implementations it's NOT any faster at all -- in fact, it's minutely
slower. I'll repeat: I'm not arguing against using std::string -- just
pointing out that your argument is a bit overstated.

[ ... ]
std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);

for(unsigned i = 0; i < plainText.length(); ++i)
{
char c = plainText;
if(c >= 'A' && c <= 'Z')
plainText = 'Z' - (c-'A');
}

std::cout << plainText << "\n";


There are quite a few other ways of doing the "encryption" while
maintaining efficiency and portability. Here's a way of doing it that's
a bit more extensible, such as making it easy to add support for
characters with accents, umlauts, etc., in a language of your choice,
instead of being restricted to English.

#include <iostream>
#include <iterator>
#include <algorithm>
#include <iomanip>
#include <limits.h>

// Just for grins, we'll put the encryption into a functor:
class encrypt {
char table[UCHAR_MAX];
static const char *un;
static const char *en;
public:
// here we build our encryption table:
encrypt() {
for (int i=0; i<UCHAR_MAX; i++)
table = i;

for (i=0; i<strlen(un); i++) {
table[un] = en;

// might as well support lower-case...
table[tolower((unsigned char)un)] =
tolower((unsigned char)en);
}
}

// do the actual encryption using a simple table lookup.
char operator()(char ch) {
return table[(unsigned char)ch];
}
};

// Here are the real tables that handle the mapping.
// If you wanted to handle a language other than English,
// you'd add the appropriate plain/encrypted characters here.
// Each character in the un string maps to the corresponding
// character in the en string.
const char *encrypt::un = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const char *encrypt::en = "ZYXWVUTSRQPONMLKJIHGFEDCBA";

int main() {

std::cin.unsetf(std::ios_base::skipws);

// encrypt (or decrypt) from cin to cout:
std::transform(std::istream_iterator<char>(std::cin),
std::istream_iterator<char>(),
std::eek:stream_iterator<char>(std::cout),
encrypt());
return 0;
}
 
D

dogatemycomputer

I am sure more conversation/discussion will follow but I really want
to thank everyone for their contributions to this thread. Bob's
comments lead me to cplusplus.com which helped me understand his
comments and thoughts. Jerry's post will take me more time to disect
and document only because I don't recognize some of the include
statements listed and how they relate to some of the text in the
class.

I'm still having trouble trying to understand the relationship between
a variable, a reference and a pointer. I am positive that one moment
I will be in the shower and suddenly the meaning of life (and
pointers) will dawn on me and all will be well with the world. Until
then I will continue to be amazed at how naturally it comes to most of
you.

If anyone has any other words of wisdom then feel free to post or
email your thoughts. I'm sure anything further would be considered
offtopic so I will digress.

Thanks again for your help!
 
B

BobR

I'm still having trouble trying to understand the relationship between
a variable, a reference and a pointer. I am positive that one moment
I will be in the shower and suddenly the meaning of life (and
pointers) will dawn on me and all will be well with the world. Until
then I will continue to be amazed at how naturally it comes to most of
you.

I can't speak for everybody, but, I'd bet a very small percentage got
pointers the first time through.

Short download.
Alf P. Steinbach's "Pointers" document:
http://home.no.net/dubjai/win32cpptut/special/pointers/ch_01.pdf

..... it's 'the shower'. <G>
 
J

Juha Nieminen

Jerry said:
It may be faster -- it certainly _can_ be. Then again, in some
implementations it's NOT any faster at all -- in fact, it's minutely
slower.

Why would any compiler implementation count the length of the
string (like strlen() does) each time you call size()/length()?
It just doesn't make any sense.

For a std::string to be dynamic it *must* know its own size.
How else could it know when to allocate more space? It would be
crazy to perform a strlen() each single time eg. something is
appended to the string, the at() function is called, etc.

The slowest possible rational implementation of std::string::size()
that I can think of is the substraction of two pointers (which is
not far-fetched because eg. the gcc implementation of std::vector
does exactly that). Nothing comparable to the overhead caused by
a loop with a comparison inside it.
 
J

James Kanze

BobR wrote:
cout << "text: "; // enter some text
cin >> plain_text; file://assign the array of text to plain_text
Here is the critical point. What happens if the user enters more
than 80 characters?
You don't want to do that. You want to do this:
std::string plainText;
std::cout << "text: ";
std::getline(std::cin, plainText);
Now it doesn't matter how much text the user writes. It won't cause
a buffer overflow.
Well, it will:
plainText.max_size() == 1073741820 [Intel, win98, MinGW].
Not too many people type that much into one line though. <G>
[ at the old (80 char line) x (66 lines per page), thats over200k pages.
So, be sure to tell your users to limit the input to "one book per line"!
:-} ]
No, it won't cause a buffer overflow. Instead, getline() will
stop after max_size() characters and then set the failbit of
the stream. [21.3.7.9/6]

Unless, of course, bad_alloc gets thrown before that:). Or the
machine starts paging so violently that it slows down radically,
and pisses the user off so much that he kills the process.
 
J

Jerry Coffin

[ ... ]
Why would any compiler implementation count the length of the
string (like strlen() does) each time you call size()/length()?
It just doesn't make any sense.

I really couldn't tell you why -- quite frankly, when people first told
me about it, I found it hard to believe as well. It was stated and
demonstrated by people I'd tend to trust. OTOH, it was quite a while ago
(somewhere around gcc 2.9x or so, if memory serves) so with any luck
it's just a minor footnote in history by now.
 
J

James Kanze

[ ... ]
Why would any compiler implementation count the length of the
string (like strlen() does) each time you call size()/length()?
It just doesn't make any sense.
I really couldn't tell you why -- quite frankly, when people first told
me about it, I found it hard to believe as well. It was stated and
demonstrated by people I'd tend to trust. OTOH, it was quite a while ago
(somewhere around gcc 2.9x or so, if memory serves) so with any luck
it's just a minor footnote in history by now.

It's probably a question of leveraging off existing C routines.
The std::string in VC++ 6.0 had problems if the string contained
a'\0', because it occasionally leveraged off the C routines,
which, of course, considered that the end of the string.

But as you say, that's all in the past.
 
J

Juha Nieminen

Jerry said:
I really couldn't tell you why -- quite frankly, when people first told
me about it, I found it hard to believe as well. It was stated and
demonstrated by people I'd tend to trust. OTOH, it was quite a while ago
(somewhere around gcc 2.9x or so, if memory serves) so with any luck
it's just a minor footnote in history by now.

Does the C++ standard state any speed requirements for the at()
method?
 
M

Michael DOUBEZ

Juha Nieminen a écrit :
Does the C++ standard state any speed requirements for the at()
method?

23.1.1/12 specifies sequence container should implement it when it runs
in constant time. IMO is applies to basic_string.

Michael
 
J

Juha Nieminen

Michael said:
23.1.1/12 specifies sequence container should implement it when it runs
in constant time. IMO is applies to basic_string.

Is that the reason some very old versions of g++ didn't support
at() for basic_strings?
 
K

Kai-Uwe Bux

Michael said:
Juha Nieminen a écrit :

23.1.1/12 specifies sequence container should implement it when it runs
in constant time. IMO is applies to basic_string.

I don't think the standard considers basic_string a sequence container. It
is not listed as a sequence container in [23.1.1/1]. As far as I know,
there are no complexity promisses for std::string whatsoever.


Best

Kai-Uwe Bux
 
M

Michael DOUBEZ

Kai-Uwe Bux a écrit :
Michael said:
Juha Nieminen a écrit :
23.1.1/12 specifies sequence container should implement it when it runs
in constant time. IMO is applies to basic_string.

I don't think the standard considers basic_string a sequence container. It
is not listed as a sequence container in [23.1.1/1]. As far as I know,
there are no complexity promisses for std::string whatsoever.

It is a sequence. The container part is more tricky because of reference
counting I guess.

But 21.3/2
"basic_string conforms to the requierement of a sequence as described in
23.1.1"

Michael
 
K

Kai-Uwe Bux

Michael said:
Kai-Uwe Bux a écrit :
Michael said:
Juha Nieminen a écrit :
Jerry Coffin wrote:
I really couldn't tell you why -- quite frankly, when people first
told me about it, I found it hard to believe as well. It was stated
and demonstrated by people I'd tend to trust. OTOH, it was quite a
while ago (somewhere around gcc 2.9x or so, if memory serves) so with
any luck it's just a minor footnote in history by now.
Does the C++ standard state any speed requirements for the at()
method?
23.1.1/12 specifies sequence container should implement it when it runs
in constant time. IMO is applies to basic_string.

I don't think the standard considers basic_string a sequence container.
It is not listed as a sequence container in [23.1.1/1]. As far as I know,
there are no complexity promisses for std::string whatsoever.

It is a sequence. The container part is more tricky because of reference
counting I guess.

But 21.3/2
"basic_string conforms to the requierement of a sequence as described in
23.1.1"

Ah, thanks. That's good to know. (Unfortunately, it does not strictly rule
out linear time for size(), but it strongly suggests constant time.)


Best

Kai-Uwe Bux
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,769
Messages
2,569,579
Members
45,053
Latest member
BrodieSola

Latest Threads

Top