Is std::string size() a O(1) operation?

by

If you’re asking if MSVC’s implementation of string::size() has constant complexity, then the answer is yes. But Don Wakefield mentioned Table 65 in 23.1 of the C++ Standard where it says that the complexity of size() should follow what’s said in ‘Note A’. Note A says:

Those entries marked ‘‘(Note A)’’
should have constant complexity.

However, that does not mean that those entries shall have constant complexity. Standards use very specific terminology, and “should” means that it is not mandatory.

‘Note A’ was added to the standard specifically to appease those who believed that size() should be allowed to have linear complexity so it would not be necessary to keep the size when the containers were modified.

So you can’t rely on size() having constant complexity, but I’m honestly not sure if there are any implementations that do not have a constant string::size().

More Related Contents:

  1. char* vs std::string in c++ [closed]
  2. How to implode a vector of strings into a string (the elegant way)
  3. std::string::c_str() and temporaries
  4. Why don’t the std::fstream classes take a std::string?
  5. I want to convert std::string into a const wchar_t *
  6. What the heque is going on with the memory overhead of std::deque?
  7. C++20 constexpr vector and string not working
  8. Do I need to protect read access to an STL container in a multithreading environment?
  9. Visual c++ “for each” portability
  10. How to increment an iterator by 2?
  11. stl::map assert [closed]
  12. std::string formatting like sprintf
  13. How to determine if a string is a number with C++?
  14. Macro for dllexport/dllimport switch
  15. How to get std::vector pointer to the raw data?
  16. Why floating point value such as 3.14 are considered as double by default in MSVC?
  17. How to iterate over a priority_queue?
  18. Using the less than comparison operator for strings
  19. How to target Windows XP in Microsoft Visual Studio C++ [duplicate]
  20. How do I erase elements from STL containers?
  21. What happens when you call data() on a std::vector?
  22. Layout of compiled objects
  23. trying to use VideoCapture and imshow(), raises Assertion failed (size.width>0 && size.height>0) in cv::imshow
  24. STL analogue in Fortran
  25. Padding stl strings in C++
  26. Finding “dead code” in a large C++ legacy application [closed]
  27. Vector Iterators Incompatible
  28. How to load a custom binary resource in a VC++ static library as part of a dll?
  29. Why can’t I replace std::map with std::unordered_map
  30. C++ delete does not free all memory (Windows)

Leave a Comment