Container questions

[Peter87]

Why are there 3x destructors here?

It can depend on the implementation but I only see two destructor calls with GCC/libstdc++ and Clang/libc++ which makes sense because std::for_each takes the functor argument by value.

https://godbolt.org/z/zKE1cEs85

Is it because "for_each" makes 2x extra copies, and then there are a total of 3x instances of vector v1?

It's not the vector that is copied. It is the functor Display<int>().

This is usually not a big deal because functors tend to be cheap to copy (and easy to optimize).

https://godbolt.org/z/647vM1Y6z <-- std::for_each generates exactly the same instructions as when using a for loop.
https://godbolt.org/z/1ehx1EaWe <-- This is even the case when the functor contains a variable.

This will obviously not be true if the functor contains a more expensive type like std::string but in that case you might want to store a reference instead.

[mbozzi]

Avoiding copies of function objects ("functors") is one of the use-cases for std::reference_wrapper

Display<int> display;
for_each(v1.cbegin(), v1.cend(), std::ref(display));

[SubZeroWins]

Yes, not the vector, I mean the struct's (Display) is copied 3x.
I tried it with Dev++ and it only made 2x copies there. I suppose functors are mostly low hit, unless maybe you are cross-referencing data with another object. They are usually well thought out, even when sometimes you wish to question motives and I imagine they did that for a good reason, instead of treating it as a pass by const ref.

It worked (std::ref), I had to "#include <functional>" and it made only 1x copy this time. What sort of voodoo magic is this? What does that wrapper actually do, change the functor 3rd parameter to a const ref during compile time?

[seeplus]

For VS std::ref is part of type_traits. Including functional will also include type_traits.

If you examine the ref source code you'll find something like:

template <class _Ty>
reference_wrapper(_Ty&) -> reference_wrapper<_Ty>;

_EXPORT_STD template <class _Ty>
_NODISCARD _CONSTEXPR20 reference_wrapper<_Ty> ref(_Ty& _Val) noexcept {
    return reference_wrapper<_Ty>(_Val);
}

_EXPORT_STD template <class _Ty>
void ref(const _Ty&&) = delete;

[SubZeroWins]

There are quite a few things in that snippet that I have not seen before and that are new to me. I gather that it sets itself up as a reference input parameter to the original "display", which then points to the original. It does the work and then at the end return the original "display".

[Peter87]

std::ref(display) returns a std::reference_wrapper<Display<int>>.

https://en.cppreference.com/w/cpp/utility/functional/reference_wrapper

std::reference_wrapper is a class template that wraps a reference in a copyable, assignable object.

If the stored reference is Callable, std::reference_wrapper is callable with the same arguments.

[mbozzi]

A reference_wrapper<T> is essentially a class that contains a pointer, along with the member functions required to make it "act" like a T&:

template <typename T> 
  class my_reference_wrapper // (simplified)
  {
    T* ptr;
  public:
    // my_reference_wrapper<T> can be implicitly converted to T&:
    operator T&() { return *ptr; } 
    // my_reference_wrapper<T> can be called like a function
    auto operator()(int n) { return (*ptr)(n); }
    // ...
  };

No magic, it's just a fairly weird class.

[SubZeroWins]

Thanks fellas!

4) Built-in find() method vs algorithm find().
If I wouldn't have checked and looked, I would have suspected that the built-in member s1.find() should return an iterator and not a size_t (unsigned integral). I would have assume this since containers are so closely tied to iterators and it does indeed facilitate matters. It is also safer to dereference an iterator, since it checks that one does not go beyond the container boundaries during compile time and less safer to use the subscript [] that is without the boundary check.

Maybe they decided to return size_t as opposed to an iterator, because typically an iterator just refers to a single element. I also know that one can custom program a search for "too" as separate elements ('t' and '0' followed by another '0') for the algorithm find();. I would have assumed they should have also overloaded the algorithm find() with the ability to find strings, with the iterator return being the first char of the search.

I also noticed that the algorithm find() does not take a string, but a single character only. So I gather that they intended the algorithm find() to be used for single characters only and if you want to find strings, then use the string member find() with size_t return.

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

int main()
{
	string s1{ "Me too, I am too full!" };

	size_t charPos = s1.find("too", 0);		//Works! (Pos = 3, 13)
	while (charPos != string::npos)
	{
		cout << "\"too\" found, letter '" << s1[charPos] << "' at pos = " << charPos << endl;
		charPos = s1.find("too", ++charPos);
	}
	
	const char* pChar = "too";
	const char tooArray[4]{ 't','o','o','\0' };
	//string::const_iterator findChar = find(s1.cbegin(), s1.cend(), "too");	//NOT WORK!
	//string::const_iterator findChar = find(s1.cbegin(), s1.cend(), pChar);	//NOT WORK!
	//string::const_iterator findChar = find(s1.cbegin(), s1.cend(), tooArray); //NOT WORK!

	return 0;
}
/*
OUTPUT:
"too" found, letter 't' at pos = 3
"too" found, letter 't' at pos = 13
*/

[George P]

Some of the C++ containers have a "custom" sort algorithm associated with the container. std::list, for example. https://en.cppreference.com/w/cpp/container/list/sort

Other containers do not have a "custom" sort algo. std::vector, for example.

Some containers do automatic sorting when adding/inserting elements to the container, others are unordered.

https://en.cppreference.com/w/cpp/container

[Peter87]

If I wouldn't have checked and looked, I would have suspected that the built-in member s1.find() should return an iterator and not a size_t (unsigned integral).

std::find just steps through each element, one by one, until it finds the value or reaches the end. Most containers doesn't have a find member function and you're just supposed to use std::find.

std::set/std::map (and the equivalent unordered containers) do have a find member function (that returns an iterator) because these containers provide a more efficient way to look up the elements. Using std::find would be suboptimal for these containers.

std::string is a bit special. It does indeed have a find member function that returns an index. It feels like it tries to be user-friendly by providing a lot of member functions while at the same time providing an interface that is consistent with the other containers. Part of the reason might be that the initial design was made before the standard algorithms and the other containers where added.

I have an early draft of the C++ standard from 1994 (N0414). It contains a string class that is very similar to std::string. It does not contain the other containers that we know today (vector, deque, list, etc.) and it also doesn't contain any of the standard algorithms (I don't think it even mention iterators). It does however contain a container called dynarray (similar to std::vector) but that one also used indices instead of iterators.

It is also safer to dereference an iterator, since it checks that one does not go beyond the container boundaries during compile time and less safer to use the subscript [] that is without the boundary check.

None of them are bounds-checked at compile time. Both of them can be checked at runtime in a debug build.

I would have assumed they should have also overloaded the algorithm find() with the ability to find strings, with the iterator return being the first char of the search.

That's what std::search is for. https://en.cppreference.com/w/cpp/algorithm/search

I also noticed that the algorithm find() does not take a string, but a single character only. So I gather that they intended the algorithm find() to be used for single characters only and if you want to find strings, then use the string member find() with size_t return.

std::find is meant to be useful, and work the same way, for any container (it doesn't even have to be a container as long as you can iterate over it using iterators).

[SubZeroWins]

Thanks.

Yes, sorting can be different for different containers and I have to be mindful for such containers that require a sort for their instantiation (such as a set).

I assumed their might be some history in the find, good to know.

"It is also safer to dereference an iterator, since it checks that one does not go beyond the container boundaries during compile time and less safer to use the subscript [] that is without the boundary check."

None of them are bounds-checked at compile time. Both of them can be checked at runtime in a debug build.

I guess I have been too good with not going beyond my bounds lately with these easier code samples. But I just checked by going out of bounds and yes, it is runtime.

I could have sworn I read a post that said compile time check and I was ecstatic that they found a way to check, and figured the compiler must have ran through the code in just the applicable parts pertaining to the container and figured it out. I must have misunderstood. I remember the poster also stating that instead of operator[], to use at() and that it also checked. I just ran the at() and it is also runtime.

So basically, there is no way to check at compile time, since that would mean running your code.

	string searchStr{ "too" };
	string::const_iterator searchResult =
		search(s1.cbegin(), s1.cend(), searchStr.cbegin(), searchStr.cend());

search noted.

[jonnin]

A compile time check would be one of the NP complete problems I believe: a variant of https://en.wikipedia.org/wiki/Post_correspondence_problem

I mean yes, it can compile time check to see if a fixed sized array that is looped over will go out of bounds. It can even check if a flexible sized vector goes out of bounds in a similar loop. But what about like a complicated hash table, can it check that your hash function returns a value in the table? If it just uses a simple %currentsize then yes, it probably can, but you may not do it that way, so it now has to figure out that your call to max() or min() or some other weird logic does the same thing. The more you dig into it the more places you can see where it would need a powerful AI to determine if the bounds were violated.