Does an empty string contain an empty string in C++?

Question

Just had an interesting argument in the comment to one of my questions. My opponent claims that the statement "" does not contain "" is wrong.

My reasoning is that if "" contained another "", that one would also contain "" and so on.

Who is wrong?

P.S.

I am talking about a std::string

P.S. P.S

I was not talking about substrings, but even if I add to my question " as a substring", it still makes no sense. An empty substring is nonsense. If you allow empty substrings to be contained in strings, that means you have an infinity of empty substrings. What is the point of that?

Edit:

Am I the only one that thinks there's something wrong with the function std::string::find?

C++ reference clearly says

Return Value: The position of the first character of the first match.

Ok, let's assume it makes sense for a minute and run this code:

string empty1 = "";
string empty2 = "";

int postition = empty1.find(empty2);

cout << "found \"\" at index " << position << endl;

The output is: found "" at index 0

Nonsense part: how can there be index 0 in a string of length 0? It is nonsense.

To be able to even have a 0th position, the string must be at least 1 character long.

And C++ is giving a exception in this case, which proves my point:

cout << empty2.at( empty1.find(empty2) ) << endl;

If it really contained an empty string it would had no problem printing it out.

Debark

I'm not sure I get it. Does an empty glass contain an empty glass? – Footlight

I really don't understand what you're asking here – Addiel

@Footlight That's a different (and more easily resolved) question – Suburbanite

@Suburbanite Maybe. If you'd explain the difference, maybe I'd understand :) – Footlight

Confusing question. Could be implementation specific. In a mathematical sense, I would assume the empty set contains the empty set. – Christology

@Footlight I'm not really sure I can explain it, and I definitely can't answer the main question, but an empty glass doesn't have another empty glass in it, whereas the empty string is closer to the empty set, which can be said to include itself – Suburbanite

@Christology If the empty set contained the empty set, it wouldn't be empty, so no, it doesn't. – Resonator

@Resonator According to wikipedia: Its only subset is the empty set itself. So if the only subset of the empty set is an empty set then the empty set contains itself? – Addiel

You forgot to add as a substring to your question and got a type error. No string contains any other string as an element (elements of strings are characters, not strings). – Eggleston

@n.m. No, I didn't forget. I updated the answer – Debark

Empty string is not really empty, it contains 1 char of null terminator. – Militarism

I was not talking about substrings --- your original question had isSubstringOf in the title. What else were you talking about if not substrings? – Eggleston

Be careful around subset and substring, they are not the same. Also consider in C++ a string s with length 10. s.substring(0,0), s.substring(1,0), etc. There are 10 such substrings that return the empty string. If you have string s = "";, then s.substring(0,0) also returns the empty string. – Princely

An empty substring is nonsense inasmuch as addition by 0 is nonsense. After all, if we allow addition with 0, we'll have an infinity of adding 0. – Resonator

@RyanWH What exactly is the difference between a subset and a substring then? I used the argument for myself, that if set a equals set b, a must contain all parts of b. An empty string equals an empty string, therefore it must contain it as well. Also, if one can get an empty string as a substring from any string, does that not imply that any string must contain an empty string? – Forland

Usually a secondary post script is P. P. S (post post script), not P. S. P. S. :-) – Haematoma

I found this question to be relevant for porting string-processing functions. – Baiss

Return value Position of the first character of the found substring or npos if no such substring is found. – Terpsichore

Answer 1

It depends on what you mean by "contains".

The empty string is a substring of the empty string, and so is contained in that sense.

On the other hand, if you consider a string as a collection of characters, the empty string can't contain the empty string, because its elements are characters, not strings.

Relating to sets, the set

{2}

is a subset of the set

A = {1, 2, 3}

but {2} is not a member of A - all A's members are numbers, not sets.

In the same way, {} is a subset of {}, but {} is not an element in {} (it can't be because it's empty).

So you're both right.

Resonator

Answer 2

C++ agrees with your "opponent":

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

int main()
{
    bool contains = string("").find(string("")) != string::npos;
    cout << "\"\" contains \"\": "
        << boolalpha << contains;
}

Output: "" contains "": true

Demo

Footlight

Do you think you have found a bug in your C++ implementation? – Eggleston

@n.m. No, why? Come to think of it, it makes sense. – Footlight

Just kidding. Of course it makes sense (but not to everyone it seems). – Eggleston

@n.m.: The standard defines the semantics of std::basic_string<>::find exactly like that, so no bug in the implementation. – Drida

Interestingly, my "STL implementation" (a very old one) gives a different result, and this is definitive not a philosophical question ;-) – Baiss

Answer 3

It's easy. String A contains sub-string B if there is an argument offset such that A.substr(offset, B.size()) == B. No special cases for empty strings needed.

So, let's see. std::string("").substr(0,0) turns out to be std::string(""). And we can even check your "counter-example". std::string("").substr(0,0).substr(0,0) is also well-defined and empty. Turtles all the way down.

Subastral

+1 rather good (and "pragmatic") explanation. Maybe the std::string("") should be replaced by std::string() – Baiss

Answer 4

Of course an empty string does not contain an empty string. It'll be turtles all the way down if it did.

Take String empty = ""; that is declaring a string literal that is empty, if you want a string literal to represent a string literal that is empty you would need String representsEMpty = """"; but of course, you need to escape it, giving you string actuallyRepresentsEmpty = "\"\"";

ps, I am taking a pragmatic approach to this. Leave the maths nonsense at the door.

Thinking about you amendment, it could be possible that your 'opponent' meant was that an 'empty' std::string still has an internal storage for characters which is itself empty of characters. That would be an implementation detail I am sure, it could perhaps just keep a certain size (say 10) array of characters 'just incase', so it will technically not be empty.

Of course, there is the trick question answer that 'nothing' fits into anything infinite times, a sort of 'divide by zero' situation.

Feverous

You're missing the point. He's asking if an empty string is a substring of an empty string. Of course it is, because a empty string is a substring of all the possible strings. – Stocking

string actuallyRepresentsEmpty = "\"\"" is far from an empty string, it is a string with 2 double quotes! – Drida

@DavidRodríguez-dribeas you missunderstood. It represents what you would need to 'program' and empty string. I am not saying that "\"\"" is an empty string that contains an empty string, it is a string that contains what would represent and empty string. – Feverous

-1 for giving a philosophical answer to a programming question. – Baiss

Ok, philosophical was probably a mistake, sorry for that. But is your answer really helpful? An important point for everyday programming is if special cases matter. You must decide if you check strings against being empty before passing it to the functions like find() and since you can get empty substrings from (empty) strings, finding these (maybe "absurd") patterns is coherent behaviour. Do you think it would be possible to improve your answer? – Baiss

Answer 5

The first thing that is unclear is whether you are talking about std::string or null terminated C strings, the second thing is why should it matter?. I will assume std::string.

The requirements on std::string determine how the component must behave, not what its internal representation must be (although some of the requirements affect the internal representation). As long as the requirements for the component are met, whether it holds something internally is an implementation detail that you might not even be able to test.

In the particular case of an empty string, there is nothing that mandates that it holds anything. It could just hold a size member set to 0 and a pointer (for the dynamically allocated memory if/when not empty) also set to 0. The requirement in operator[] requires that it returns a reference to a character with value 0, but since that character cannot be modified without causing undefined behavior, and since strict aliasing rules allow reading from an lvalue of char type, the implementation could just return a reference to one of the bytes in the size member (all set to 0) in the case of an empty string.

Some implementations of std::string use small object optimizations, in those implementations there will be memory reserved for small strings, including an empty string. While the std::string will obviously not contain a std::string internally, it might contain the sequence of characters that compose an empty string (i.e. a terminating null character)

Orthotropous

requirements for the component - this is definitely true. But have you a reference at hand, here these critical cases aren't covered: string::find - C++ Reference ? The (old) implementation I've to use gives string::npos for std::string().find(std::string()) and this seems not (or no more?) to be standard-conform, see Coliru Viewer Thanks in advance! – Baiss

@Wolf: I would not trust that particular source of documentation, consider using cppreference.com. The standard, C++03 is the oldest I checked, defines the result of the operation xpos as the location in the string such that xpos + arg.size() <= size() and the sequence of values in the object after xpos is the same sequence as the sequence of values in arg. The value 0 matches the requirements: 0 + empty.size() <= empty.size() (0 <= 0), and since there are no elements in empty, the second restriction is trivially matched. That is, anything.find("") == 0 by definition. – Drida

today I stumbled upon some strange test cases of mine (marked with questionable) and therefore searched this problem again. I think it's not about implementation details but about specification, so (sorry) this is distracting in my opinion. I added an answer that quotes at least Cppreference (as a deputy for "the standard") – Baiss

Answer 6

empty string doesn't contain anything - it's EMPTY. :)

Proven

@DavidRodríguez-dribeas there is nothing philosophical here. You just look up a definition in a textbook. – Eggleston

But the answer is a bit far from programming..., or is it not? std::string empty; std::string also_empty = empty.substr(0,0); seems to indicate that you can get a substring out of an empty string that is an empty string. Another question is what is the result of empty.find("") is 0, not std::string::npos, indicating that it found the empty string at the start of the empty string... – Drida

@n.m.: Well, if it is not philosophical then this answer is wrong on two accounts, it is not supported by evidence and it goes against what the standard states. – Drida

-1 this answer expresses a personal opinion. We should better not base software solutions on opinions. – Baiss

Answer 7

Today I had the same question since I'm currently bound to a lousy STL implementation (dating back to the pre-C++98 era) that differs from C++98 and all following standards:

TEST_ASSERT(std::string().find(std::string()) == string::npos); // WRONG!!! (non-standard)

This is especially bad if you try to write portable code because it's so hard to prove that no feature depends on that behaviour. Sadly in my case that's actually true: it does string processing to shorten phone numbers input depending on a subscriber line spec.

On Cppreference, I see in std::basic_string::find an explicit description about empty strings that I think matches exactly the case in question:

an empty substring is found at pos if and only if pos <= size()

The referred pos defines the position where to start the search, it defaults to 0 (the beginning).

A standard-compliant C++ Standard Library will pass the following tests:

TEST_ASSERT(std::string().find(std::string()) == 0);
TEST_ASSERT(std::string().substr(0, 0).empty());
TEST_ASSERT(std::string().substr().empty());

This interpretation of "contain" answers the question with yes.

Baiss