Map string in cpp

Question

I want to store all substrings in a unordered_map .I am thinking to use substr function of stl but it worst case time complexity comes out to be O(n) and when I am going to use inside a loop for all indexes of string it will give me O(n^2).

Can we do something better in O(n) by using pointer or something else so that i can access the substring later.

try string view. You can represent substring in a very efficient way. However storing all substring in a map will be slow no matter what you try. Using the map as a cache for already computer result given a substring will be much much better — Guillaume Racicot
– Guillaume Racicot, Commented Mar 8, 2019 at 20:12
Curious how you plan to use this map, i suspect thats where we should focus on — tinkertime
– tinkertime, Commented Mar 8, 2019 at 20:15

NathanOliver · Accepted Answer · 2019-03-08 20:28:02Z

1

If you don't want to copy the sub strings into the map then you can use std::string_view to store a view of the sub string. This cost you a pointer and a length, so it's as efficient as it can be.

You can build a vector of all the sub strings like

int main()
{
    std::string word = "word";
    auto size = word.size();
    std::vector<std::string_view> parts;
    parts.reserve(size * (size + 1)/2); // reserve space for all the sub strings
    for(size_t i = 0; i < size; ++i)
        for(size_t j = i; j < size; ++j)
            parts.emplace_back(word.data() + i, j - i + 1);
}

answered Mar 8, 2019 at 20:28

NathanOliver

183k29 gold badges323 silver badges439 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Map string in cpp

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related