usually when i started coding and started learning about string array or normal array ,i used to work with string array or array by typing strlen() or size() in the for loop condition.
for(int i=0;i<strlen();i++)
{
statement;
}
but its a totally wrong way to set up the condition.because normally if my algorithms complexity is O(n),and i use strlen() it,my time complexity will become O(n^2). **** this happens because every time for loop come to check the condition it will start checking what is the string length is,so total complexity will become n*n = n^2 **** so to avoid this kind of situation ,declare integer variable n= strlen(),and then put the code like this
int n= strlen();
for(int i=0;i<n;i++)
{
statement;
}
i hope this will be helpful :).
I use .size() yet no problem when the string size is constant
also yes you should put a lim for example for sqrt n
thanks for writing everything in bold ,it makes the whole thing easy to read
Yes,
strlenis linear sofor(int i = 0; i < strlen(...); i++)is quadratic. It's better to create and use a variablen.That is to give more emphasis and strength to the statement.
If the compiler is able to prove that the
const char *argument tostrlendoesn't change in the loop, it may hoist thestrlencall out of the loop.Try this with G++ in custom invocation, with or without
s[i] = '0'and observe the time.So it's not always lost. However, it is a good practice not to do this.
Your way of storing string data is C style. I use C++ way, the std::string. I would say it's beneficial to use std::string. It is easy to work with (like you are working with char array). you can add another string to the end of that with
+=operator and you can get it's length withsizemember function in constant time (which means you just have to type.size()and it won't affect your program's time complexity the way you described). If you wanted a C string (which isconst char*) you can have it by.c_str(). You can lexicographically compare two std::string s by</>. You can sort an array of them bystd::sort"easily" (By that I mean you don't have to write a comparator). It has handypop_backandsubstrmember functions. For further reading, check out basic_string. std::string may have some overhead but I'd say its negligible. BTW you don't have to typestd::all the time :).std::stringis as far as I know quite slower thanchar*. And yes it has a lot of useful functions but when your write them on your own you know exactly how they are implemented and can optimise them but it doesn't take a lot of time. It is different withstd::setorstd::mapwhich have a complicated implementation.C++ is as far as I know quite slower than Assembler. And yes it has a lot of useful functions but when your write them on your own you know exactly how they are implemented and can optimise them but it doesn't take a lot of time. It is different with Haskell or Postgres which have a complicated implementation.
C++ is on a lot of cases faster than (naively-written) assembly code. In general what you would say that makes
std::stringand other containers slow is heap allocations. As long as you make the same number of allocations forstd::stringas you would make withchar*, you shouldn't see much difference.A
std::stringprobably makes a logarithmic (in the number of elements) number of heap allocations, just asstd::vector, which is totally fine. What might not be as fine is allocating astd::stringat every iteration of a loop, where forchar*you might preallocate straight away (mainly because coding in a rudimentary C-style fashion goes implicitly hand-in-hand with making everything global). The allocation might or might not be optimized away by the compiler, but if you strive performance, just try to limit the number of allocations (stl or non-stl).I'd rather stick to STL as long as it provides the functionalities I want. I prefer to get used to that because time limits, most of the time, aren't that tight that small changes will be necessary and help you pass the tests. Another reason (at least for me) is that in an onsite contest when you are not allowed to copy/paste codes from web or your own library, and you have to type anything you want (at least once!), you can use language features and buy yourself some amount of time. Plus, C++ library is well written and you won't face an issue if you use it right.
There is no harm in doing strlen operation in a loop, unless you are modifying the string in the loop again and again. Length of the string gets stored in the memory and the value is accessed by the Hit, which is constant time. In case the string is modified, the modify flag becomes True, hence the program takes O(length of string) complexity to run the operation.
Also, string.size() works in constant time complexity.
thanks <3
What you described is a possible optimization which the compiler may make if it can prove that the string length isn't modified in the loop. It is not required by the C++ standard and you shouldn't rely on it because it's very possible that the compiler isn't able to make such a proof. For example, the compiler might not perform this optimization if you called a function that has access to the string, even if that function doesn't actually modify the string. A real-world example from ShapC shows the compiler not performing the optimization even though the string is
constand never modified resulting in much slower code. Don't take such an unnecessary risk in contests.https://sourceforge.net/p/notepad-plus/patches/473/
some coders use this trick
Do you have to do this with vectors as well?
.size()works ok, so you should not worry about it. When you usestrlen()it iterates through the wholechar[]to find null-termination characterI think .size() is constant and doesn't take linear time;
due to this link: http://www.cplusplus.com/reference/string/string/size/