Re-validating an iterator

I wrote a simple program that removes all people from the vector based on age. Normally, when i write a program like this i usually remove only one person, so i decided to write a program that removes multiple, and it works, but I'm wondering if this is the best approach to re-validating the iterator after removing an element. The line is line 59 in my while loop where i redefine find_if.

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <chrono>
#include <thread>
#include <random>
#include <algorithm>

int main()
{
    std::mt19937 mt(static_cast<unsigned int>(std::chrono::high_resolution_clock::now().time_since_epoch().count()));

    auto age = std::uniform_int_distribution<int>(18, 60);

    std::vector<std::pair<std::string, int>> employees;

    employees.push_back(std::make_pair("Kim", 20));
    employees.push_back(std::make_pair("Joe", 20));
    employees.push_back(std::make_pair("Dave", age(mt)));
    employees.push_back(std::make_pair("Steve", age(mt)));
    employees.push_back(std::make_pair("Scott", age(mt)));
    employees.push_back(std::make_pair("Mark", age(mt)));
    employees.push_back(std::make_pair("Megan", age(mt)));
    employees.push_back(std::make_pair("Stephanie", age(mt)));
    employees.push_back(std::make_pair("Jim", age(mt)));
    employees.push_back(std::make_pair("Kylie", age(mt)));

    for (auto& i : employees)
    {
        std::cout << i.first << " - " << i.second << '\n';
    }

    std::cout << "\nLets remove  all people with the same age!, Pick an age to remove the person.\n";
    std::cout << '>';
    
    int input{ };

    std::cin >> input;

    auto compare = [&input](const auto& a)
        {
            return a.second == input;
        };

    auto it = std::find_if(employees.begin(), employees.end(), compare);

    int counter{ 0 };

    std::vector<std::string> removedPeople;

    while (it != employees.end())
    {
        removedPeople.push_back(it->first);
        employees.erase(it);
        ++counter;
        //We redefine find_if here because when we remove a name from the vector the iterator
        //pointing to that element is invalidated, so we need to re-validate it by callinf find_if again.
        it = std::find_if(employees.begin(), employees.end(), compare);
    }

    if(counter > 0)
    {
        std::cout << "Found " << counter << " instances of the number " << input << '\n';
    }
    else
    {
        std::cout << "No instances of the number " << input << " were found.\n";
    }

    std::cout << "\n\n";

    std::cout << "The following people were removed from the list\n\n";

    for (auto& i : removedPeople)
    {
        std::cout << i << "\n";
    }
}

Last edited on

Peter87 (11235)

erase returns an iterator to the position after the removed element. You can use that to avoid having to search from the start each time.

auto it = std::find_if(employees.begin(), employees.end(), compare);
while (it != employees.end())
{
	it = employees.erase(it);
	it = std::find_if(it, employees.end(), compare);
}

It might be tempting to try and combine find_if and erase in the same statement
it = std::find_if(employees.erase(it), employees.end(), compare);
but that is not guaranteed to work because you don't know which argument will be evaluated first. If employees.end() is evaluated before the call to erase then you'll end up with an invalid iterator.

To avoid having to repeat find_if twice in your code you could call it from within the loop condition, like this:

auto it = employees.begin();
while ((it = std::find_if(it, employees.end(), compare)) != employees.end())
{
    it = employees.erase(it);
}

Last edited on

As C++20:

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <random>
#include <algorithm>

int main() {
	std::mt19937 mt(std::random_device {}());
	auto agedist { std::uniform_int_distribution<int>(18, 60) };

	std::vector<std::pair<std::string, int>> employees {{"Kim", 20}, { "Joe", 20 }, { "Dave", agedist(mt) },
		{ "Steve", agedist(mt) }, { "Scott", agedist(mt) }, { "Mark", agedist(mt) }, { "Megan", agedist(mt) },
		{ "Stephanie", agedist(mt) }, { "Jim", agedist(mt) }, { "Kylie", agedist(mt) }};

	for (const auto& [name, age] : employees)
		std::cout << name << " - " << age << '\n';

	int age { };
	std::vector<std::string> removedPeople;

	std::cout << "\nLets remove all people with the same age!\nPick an age to remove the person: ";
	std::cin >> age;

	const auto removed { std::erase_if(employees, [&](const auto& data) {
		const auto erase {data.second == age};

		if (erase)
			removedPeople.push_back(data.first);

		return erase;
	}) };

	if (removed > 0) {
		std::cout << "\nFound " << removed << " people of the age " << age << '\n';
		std::cout << "\nThe following people were removed from the list\n\n";

		for (const auto& r : removedPeople)
			std::cout << r << "\n";
	} else
		std::cout << "\nNo instances of the number " << age << " were found.\n";
}

Or for the OP code as a 1 liner :)

for (auto it {employees.begin()}; (it = std::find_if(it, employees.end(), compare)) != employees.end(); ++counter, removedPeople.emplace_back(it->first), it = employees.erase(it));

Note that vector .erase() can be 'slow' as it has to re-adjust the vector elements by shuffling them. If std::erase_if() can't be used, then the old erase-remove idiom can be used:

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <random>
#include <algorithm>

int main() {
	std::mt19937 mt(std::random_device {}());
	auto agedist { std::uniform_int_distribution<int>(18, 60) };

	std::vector<std::pair<std::string, int>> employees {{"Kim", 20}, { "Joe", 20 }, { "Dave", agedist(mt) },
		{ "Steve", agedist(mt) }, { "Scott", agedist(mt) }, { "Mark", agedist(mt) }, { "Megan", agedist(mt) },
		{ "Stephanie", agedist(mt) }, { "Jim", agedist(mt) }, { "Kylie", agedist(mt) }};

	for (const auto& [name, age] : employees)
		std::cout << name << " - " << age << '\n';

	int age { };
	std::vector<std::string> removedPeople;

	const auto compare { [&](const auto& data) {
		const auto erase { data.second == age };

		if (erase)
			removedPeople.push_back(data.first);

		return erase;
	} };

	std::cout << "\nLets remove all people with the same age!\nPick an age to remove the person: ";
	std::cin >> age;

	employees.erase(std::remove_if(employees.begin(), employees.end(), compare), employees.end());

	if (!removedPeople.empty()) {
		std::cout << "\nFound " << removedPeople.size() << " people of the age " << age << '\n';
		std::cout << "\nThe following people were removed from the list\n\n";

		for (const auto& r : removedPeople)
			std::cout << r << "\n";
	} else
		std::cout << "\nNo instances of the number " << age << " were found.\n";
}

https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom

PS. This works without falling foul of the 'which argument evaluated first' mentioned by Peter87 above because in this case std::remove_if() doesn't change the size of the vector (it just swaps elements) so .end() doesn't change so it doesn't matter in this case which argument is evaluated first.

Last edited on

Thank you! that helps, also i didnt know about structured bindings so thats nice to know as well. Ive been studying C++ every single day for like the past 4 months and theres still just sooo much to learn. I learn new stuff almost every day, this language really is massive.

http://coliru.stacked-crooked.com/a/cb3a2140ef4ea3a7

this language really is massive.

C++23 is coming out anytime now. And they've started on the new things that will appear in C++26! :) :)

JLBorges (13770)

> std::remove_if() doesn't change the size of the vector

But it leaves the 'to-be-erased' values in an unspecified state.

Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable,
but the elements themselves have unspecified values (as per MoveAssignable post-condition) (since C++11).
https://en.cppreference.com/w/cpp/algorithm/remove

Use std::partition (or std::stable_partition) instead.

> this language really is massive.

Fairly old stuff (C++11):

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <iterator>

int main()
{
    using employee_t = std::pair<std::string,int> ;
    std::vector<employee_t> employees { { "kim", 20 },
                                        { "joe", 30 },
                                        { "dave", 20 },
                                        { "steve", 42 },
                                        { "scott", 20 },
                                        { "mark", 18 },
                                        { "megan", 24 } } ;

    const int target_age = 20 ;
    const auto partition_pt = std::partition( employees.begin(), employees.end(),
                                              []( const employee_t& e ) { return e.second != target_age ; } ) ;
    const std::vector<employee_t> removedPeople( std::make_move_iterator(partition_pt),
                                                 std::make_move_iterator(employees.end() ) ) ;
    employees.resize( std::size_t( partition_pt - employees.begin() ) ) ;

    std::cout << employees.size() << " | " << removedPeople.size() << '\n' ; // 4 | 3
}

>> C++23 is coming out anytime now.

I guess that makes it less bothersome that VS 2022 is not fully 100% C++23/C++26 compliant than several of the other compiler suites.

I thought C++23 was already officially released as the 'new' current standard. I see now it isn't. The current standard is still C++20.

>> Ive been studying C++ every single day for like the past 4 months

I've been solo learning/self-teaching C++ since before C++98 was a "thing." I am still way behind on knowing all the possibilities of what C++ has to offer.

I suggest treating any C++ code you see that is pre-C++11 as not existing. C++11 was a such a major change as to make it a totally different language. C++14/C++17 made some changes though not as fundamental overall as C++11.

C++17added the file system library. Learn that.

C++20 is probably the 2nd largest update change to the language. One really nice feature IMO is the formatting library.

import <iostream>;
import <format>;

int main( )
{
   unsigned int limit { };

   std::cout << "This program calculates n! and the sum of the integers "
      << "up to n for values 1 to limit.\n";
   std::cout << "What upper limit for n would you like? ";
   std::cin >> limit;

   // the format string for all rows of the table
   const auto table_format { "{:>8} {:>8} {:>20}\n" };

   // output column headings
   std::cout << std::format(table_format, "integer", "sum", "factorial");

   for ( unsigned long long n { 1 }, sum {}, factorial { 1 }; n <= limit; ++n )
   {
      sum += n;
      factorial *= n;

      std::cout << std::format(table_format, n, sum, factorial);
   }
}

This program calculates n! and the sum of the integers up to n for values 1 to limit.
What upper limit for n would you like? 20
 integer      sum            factorial
       1        1                    1
       2        3                    2
       3        6                    6
       4       10                   24
       5       15                  120
       6       21                  720
       7       28                 5040
       8       36                40320
       9       45               362880
      10       55              3628800
      11       66             39916800
      12       78            479001600
      13       91           6227020800
      14      105          87178291200
      15      120        1307674368000
      16      136       20922789888000
      17      153      355687428096000
      18      171     6402373705728000
      19      190   121645100408832000
      20      210  2432902008176640000

@Ch1156,

If'n you haven't already been there I suggest spending some time at "Learn C++". You won't learn all of what is in the C++ toolbox, but it is a decent tutorial for a lot of what the language offers.

https://www.learncpp.com/

The site does get frequent updates.

@ George P

Ive actually been studying C++ for about 14 years now, on and off, but recently ive been really going hard on actually learning the advanced stuff and forcing myself to study, having ADHD makes it super difficult sometimes but i try to at least write code every day and practice the stuff i learned so it stays fresh. Im also taking notes as well.

And yeah ive been using learncpp.com, really great site, i also use cppreference.com for references, its a little hard to read sometimes but im getting used to it. and the biggest help of all i would say is chatGPT. Whenever i have an issue i can just paste my code in the chat and it tells me exactly whats wrong and why its wrong, mega helpful and sped up my learning by a lot. Just have to be careful with it cause it can and sometimes does give wrong info, but ive found that its not too common and its mostly small things. I usually double check stuff on websites and sometimes on here. I know enough c++ to kind of catch it when it happens too so it hasnt been much of an issue. pretty amazing tool.

I still need to completely read through learncpp.com and my programming book Professional C++ 5th edition, but ive been doing a LOT of learning and coding lately so ive kind of been neglecting those resources, but ill get back into them soon.

Yeah I dont bother learning anything thats not considered modern C++. Im never going to work with older code or anything like that so i just focus on everything C++ 11 and onward.

I havent heard of the file system library, ill check that out! As for the format library, I only used it once about 5 or 6 days ago actually. I was practicing with chrono stuff and I wanted to output year, hour, minute, day etc separately and chatGPT suggested I use the format library and gave me a few examples and i took it from there. i'll have to look more into it for sure it seems really useful, heres my code for that:

    auto EasternTimeOffset = std::chrono::hours(-4);
    const auto currentTime = std::chrono::system_clock::now() + EasternTimeOffset;
    std::cout << std::format("{:%B}", currentTime); //Month
    std::cout << std::format("{:%e}", currentTime) << "th "; //Day
    std::cout << std::format("{:%Y}", currentTime); //Year

    auto currentHours = std::format("{:%I}", currentTime);
    auto currentMinutes = std::format("{:%M}", currentTime);
    auto amOrPm = std::format("{:%p}", currentTime);

    std::cout << " @ " << currentHours << ":" << currentMinutes << ' ' << amOrPm;

@JLBorges

I'll check out std::partition as well, I've been going through the headers of C++ and picking out all the stuff I think would be useful and learning those. I kinda sidelined it for the time being though as ive been focusing so much effort on learning new concepts of the language, but i want to get back into that as well.

@seeplus

Yeah haha, ive read some of the papers for the new features and some of them seem interesting, doesnt seem to have as many new features as 23, but 23 has a new addition for string, contains which im excited about cause it makes it easier to check for substrings. Bunch of other nice little improvements in 23 as well.

>> my programming book Professional C++ 5th edition

Good book, but having multiple tomes, print or eBook, is even better.

Another print book I can recommend is "Beginning C++20: From Novice"
https://www.amazon.com/gp/product/1484258835/

For eBooks I recommend Leanpub. Many times the author(s) put the book up for sale there before it is done being written and the price for an "incomplete" book is less than the finished price.

Books by Bartłomiej Filipek, Nicolai M. Josuttis and Rainer Grimm are good ones to consider purchasing. I own a number of those as eBooks. C++17/C++20 and select aspects of the language such as concurrency, the stdlib, move semantics and lambdas. Each of those books deal more in depth with the subject than an over all book on C++17/C++20 does.

Leanpub lets you download your books as .pdf and .epub. If you own an Amazon Fire tablet (along with an Amazon account) you can have the site automatically "send" the books to your tablet. They are routed to the Docs part.

More and more source code for books is being hosted on github so you can download. For example you can clone the repo for the Beginning C++20 book at:
https://github.com/Apress/beginning-cpp20

Even though the Horton/Van Weert Beginning C++23 book has NOT been released, it is a "work in progress," there is a github repo for the code.
https://github.com/Apress/beginning-cpp23

Many of the leanpub books I own also have github repos available.

I also purchased several Packt eBooks when they were running a special sale about a year ago. C++ and Windows© programming related. All the Packt books I purchased have github repos available.

Last edited on

Even though the Horton/Van Weert Beginning C++23 book has been released

The release date is 18 Sep 2023.

"NOT released" was what I meant to say. *Yikes*

Before I buy the C++23 book I do believe I'll wait until C++23 is officially made the C++ standard AND VS 2022 is closer to being C++23 compliant than it is now. Kinda like what 2022 did with C++20.

@George P

Thanks for the suggestion, I ordered Beginning C++20, it will be here monday! In the meantime I was able to find a PDF of it. I usually like to have both, a paper copy so i can support the author, and a PDF copy so i can read it on my phone and ipad. I'll check out leanpub as well, I like digital books, makes it easier to take notes and read on the go.

Books by Bartłomiej Filipek, Nicolai M. Josuttis and Rainer Grimm

Do you have any specific recommendations from those authors?

I'll check out the git repo for the cpp 23 version of the horton/van weert book, I also added that to my cart and im gonna buy that as soon as it releases as well.

Yeah its nice having those git repos now, i remember when they used to come with CD's and those would get lost so you'd have to type out the project from the book, haha.

I started my vacation from work so i have the next 9 days off and i plan to get a lot of learning done.

Oh also I wanted to ask, would stroustrups A tour of C++ 3rd edition be a good buy at all? its been on my amazon wishlist for a little while now. I have the second edition and its nice as kind of a quick overview of things, which i like, but idk.

Last edited on

I only mention the leanpub eBooks I have purchased (in reverse purchase order):

C++ Initialization Story - A Guide Through All Initialization Options and Related C++ Areas by Bartłomiej Filipek
https://leanpub.com/cppinitbook

C++20 (See the Details) by Rainer Grimm
https://leanpub.com/c20

Concurrency with Modern C++ - What every professional C++ programmer should know about concurrency by Rainer Grimm
https://leanpub.com/concurrencywithmodernc

The C++ Standard Library - What every professional C++ programmer should know about the C++ standard library by Rainer Grimm
https://leanpub.com/cpplibrary

C++20 - The Complete Guide by Nicolai M. Josuttis
https://leanpub.com/cpp20

C++ Move Semantics - The Complete Guide by Nicolai M. Josuttis
https://leanpub.com/cppmove

C++ Lambda Story - Everything you need to know about Lambda Expressions in Modern C++! by Bartłomiej Filipek
https://leanpub.com/cpplambda

C++17 in Detail - Learn the Exciting Features of The New C++ Standard! by Bartłomiej Filipek
https://leanpub.com/cpp17indetail

C++17 - The Complete Guide by Nicolai M. Josuttis
https://leanpub.com/cpp17

Even the C++17 books are worth purchasing, they delve into aspects of the standard that aren't covered by overall C++ books.

Another couple of eBooks by other authors than the 3 I mentioned earlier I have found useful:

The Legacy Code Programmer's Toolbox - Practical skills for software professionals working with legacy code by Jonathan Boccara
https://leanpub.com/legacycode

Learning to deal with older, legacy code is something even a programmer hobbyist like me needs to know. For example, knowing how to update ooooooooold Win32 code so it compiles and runs on modern Windows© systems. One of my attempts are here (shameless self-plug):
https://github.com/GeorgePimpleton/Win32-games

C++ Best Practices by Jason Turner
https://leanpub.com/cppbestpractices

Regarding Saint Bjarne books....

His tomes are IMO written for advanced programmers, similar to how material is presented at cppreference vs. Learn C++.

Being someone who has learned and still learning C++ on my own his books are good, but not overall useful for me. YMMV.

I am not now, nor do I ever want to be, a professional programmer. I prefer being a self-taught hobbyist. I can plink around with whatever fascinates me at my own pace and schedule.

Regarding Saint Bjarne books....

I'm not a fan but his books are popular - possibly because of the author. I would, however, advise against his 'C++ Programming Language (latest is 4th edition)' which is a reference tome for C++11 and hasn't been updated for later C++ versions. His 'Programming: Principles and Practice Using C++ (latest is 2nd edition)' only covers C++14 and again hasn't been updated for later C++ versions. The 'Tour of C++' third edition covers C++20 but as Bjarne himself says is only an overview of features of C++20 but is useful for 'what makes a modern C++ program'.

Awesome, thanks for the book recommendations!

Learning to deal with older, legacy code is something even a programmer hobbyist like me needs to know. For example, knowing how to update ooooooooold Win32 code so it compiles and runs on modern Windows© systems. One of my attempts are here (shameless self-plug):
https://github.com/GeorgePimpleton/Win32-games

Those Books! Those are the ones i started with! haha. The blue one was my first and the sams teach yourself one one was my second. I completely forgot about those two, what a blast from the past. I never learned much from them because i didnt have any resources to ask questions, but i remember reading through them to some degree and running some of the code.

I might give bjarnes book a shot but ill wait on it until i check those others out. I dont want to be a professional either, my ONLY goal is to just make a 2D game using C++ and SFML, thats all I want. I have all these ideas and no outlet so thats my goal. I have zero interest in ever working for a company or anything like that.

Even though im learning C++ as a means to an end, I do find it to be genuinely fun and interesting so that helps at least.

I would, however, advise against his 'C++ Programming Language (latest is 4th edition)' which is a reference tome for C++11 and hasn't been updated for later C++ versions. His 'Programming: Principles and Practice Using C++ (latest is 2nd edition)

I have both of these actually hahah, I havent read through them though nor do i ever really plan to, at least not to learn anything, maybe just out of curiosity, but thats it. I bought them quite a while back then found out they arent up to date so im stuck with them, but hey they make nice paperweights XD

Last edited on

His books are IMO more reference than books to learn from. I've found his writing style to be idiosyncratic and at times more than a bit dense. Probably because he is writing to college/university students.

And on occasion IIRC his book code violates core C++ recommendations even he says shouldn't be done.

The biggest detriment is his books are written for earlier standards, not to say his books aren't something to have in one's library. They are if you already have them.

FYI, I call Stroustrup Saint Bjarne since he invented the C++ language, and has been a Patron Saint in guiding its development ever since. Though that role is by necessity being diminished as time goes on.

Speaking of C++ Core Guidelines....

https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines

More of a reference than something to read from the beginning to the end, but worth the time to see what is considered by several C++ experts that goes into writing simpler, more efficient, more maintainable code. Resulting code that is also easier to read and understand.

Note well, they are guidelines for writing code. Suggestions. Not "written in stone rules" that must be mindlessly and slavishly followed.