Unable to have concatenated string in vector of strings when tried to concat using dereferenced iterator

Question

My intention is to have a vector with all substrings of a given string. I am attempting to push element by concating current strings in vector with iterated character of str

What is going wrong in below code.

void Substring(string str)
{
    vector<string> vec={""};
    for(auto i =0; i<str.length(); i++)
    {
        auto end = vec.end();
        string s(1,str[i]);
        for (auto iter = vec.begin(); iter!=end; iter++)
        {
            vec.push_back(s+ static_cast<string>(*iter)); // --> what is the problem here in concatenation
        }
    }
    for (auto iter = vec.begin(); iter!=vec.end(); iter++)
    {
        cout <<"iter_val:"<<*iter <<endl; //--> does not print concated element
    }
}

If the storage of a vector is reallocated (which can happen quite frequently when you `push_back`) then *all* iterators become invalidated. — Some programmer dude, Apr 09 '18 at 06:19
On an unrelated note: `*iter` already is a `std::string`, you don't need to cast it. — Some programmer dude, Apr 09 '18 at 06:19
@codekaizer : I just want to have substrings of str into vector and display it. — ceasif, Apr 09 '18 at 06:29
For a possible solution, use the *size* instead, and iterate using indexes. — Some programmer dude, Apr 09 '18 at 06:33

Maxim Egorushkin · Accepted Answer · 2018-04-10T09:05:35.960

2

vec.push_back invalidates existing iterators. You may like to change the algorithm to avoid that, e.g.:

std::vector<std::string> substrings(std::string const& s) {
    std::vector<std::string> result;
    for(size_t i = 0, j = s.size(); i < j; ++i)
        for(size_t k = 1, l = j - i - !i; k <= l; ++k)
            result.push_back(s.substr(i, k));
    return result;
}

int main() {
    for(auto const& s : substrings("abc"))
        std::cout << s << '\n';
}

edited Apr 10 '18 at 09:05

answered Apr 09 '18 at 09:47

Maxim Egorushkin

131,725
17
180
271

it would be helpful if you share, how does push_back invalidates the iterator. I am quite confused with the output I get. Is it undefined output, my code delivers? Output -> I find that it concats every time with " " but maintains the number of iterations otherwise I would expect infinite iteration – ceasif Apr 09 '18 at 10:01
Haha. At first I thought there was a bug, because it does not print the string itself among the substrings. Then !i saw, not bug, feature. – Jive Dadson Apr 09 '18 at 10:09
@ceasif It invalidates the iterators by design. Read [`std::vector::push_back`](http://en.cppreference.com/w/cpp/container/vector/push_back). – Maxim Egorushkin Apr 09 '18 at 10:14
Nice, but I wouldn't consider constructs like `l = j - i - !i` to be "nice maintainable code" ;) – JHBonarius Apr 10 '18 at 09:15
@JHBonarius A good design is not when there is nothing left to add, rather when there is nothing left to remove. – Maxim Egorushkin Apr 10 '18 at 09:19
I respect you opinion, but truth is in the eye of the beholder. For instance: it seems the OP also wants to consider 'substring' "abc", which your code does not return: unhappy customer. So consider how this will go in a big company: the guys send to fix this code must first find out what is happening in this code... – JHBonarius Apr 10 '18 at 09:34

Jive Dadson · Answer 2 · 2018-04-09T13:11:03.770

Here is one that lists the substrings in order of decreasing length.

#include <vector>
#include <string>

static
std::vector<std::string> 
substrings(const std::string &str) {
    std::vector<std::string> subs;
    const auto m = str.length();
    for (size_t N = m; N > 0; --N) {
        for (size_t i = 0; i <= m-N; ++i) {
            subs.push_back(str.substr(i, N));
        }
    }
    return subs;
}

int main() {
    for(const auto &s : substrings("foobar"))
        std::cout << s << ' ';
}

Say this out loud:

foobar fooba oobar foob ooba obar foo oob oba bar fo oo ob ba ar f o o b a r

Coming soon to a compiler near you... No vector, no std::strings, no copying!

#include <generator>
#include <string_view>

std::generator<std::string_view>
substrings(std::string_view const s) {
    const auto m = s.length();
    for (size_t N = m; N > 0; --N) {
        for (size_t i = 0; i <= m-N; ++i) {
             co_yield s.substr(i, N);
        }
    }
}

int main() {
    for (auto const s : substrings("foobar")) {
        std::cout << s << ' ';
    }
}

score 0 · Answer 3 · answered Apr 09 '18 at 10:03

0

works using size() instead of iterator

void Substring(string str)
{
    vector<string> vec={""};
    for(auto i =0; i<str.length(); i++)
    {
        auto size = vec.size();
        string s(1,str[i]);
        for (auto iter = 0; iter<size; iter++)
        {
            vec.push_back(vec[iter]+s);
        }
    }
    for (auto iter = vec.begin(); iter!=vec.end(); iter++)
    {
        cout <<"iter_val:"<<*iter <<endl; 
    }
}

answered Apr 09 '18 at 10:03

ceasif

345
2
14

don't use [`using namespace std`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). And don't ignore the compiler warnings: `i` is type `int`, while `str.length()` returns a `size_t` type, thus comparing them will return a warning. And are you sure you also want to consider an empty string? – JHBonarius Apr 10 '18 at 09:37

Unable to have concatenated string in vector of strings when tried to concat using dereferenced iterator

3 Answers3