In addition to container classes and iterators, STL also provides a number of generic algorithms for working with the elements of the container classes. These allow you to do things like search, sort, insert, reorder, remove, and copy elements of the container class.
Note that algorithms are implemented as functions that operate using iterators. This means that each algorithm only needs to be implemented once, and it will generally automatically work for all containers that provides a set of iterators (including your custom container classes). While this is very powerful and can lead to the ability to write complex code very quickly, it’s also got a dark side: some combination of algorithms and container types may not work, may cause infinite loops, or may work but be extremely poor performing. So use these at your risk.
STL provides quite a few algorithms -- we will only touch on some of the more common and easy to use ones here. The rest (and the full details) will be saved for a chapter on STL algorithms.
To use any of the STL algorithms, simply include the algorithm header file.
min_element and max_element
The std::min_element and std::max_element algorithms find the min and max element in a container class. std::iota generates a contiguous series of values.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <algorithm> // std::min_element and std::max_element #include <iostream> #include <list> #include <numeric> // std::iota int main() { std::list<int> li(6); // Fill li with numbers starting at 0. std::iota(li.begin(), li.end(), 0); std::cout << *std::min_element(li.begin(), li.end()) << ' ' << *std::max_element(li.begin(), li.end()) << '\n'; return 0; } |
Prints:
0 5
find (and list::insert)
In this example, we’ll use the std::find() algorithm to find a value in the list class, and then use the list::insert() function to add a new value into the list at that point.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <algorithm> #include <iostream> #include <list> #include <numeric> int main() { std::list<int> li(6); std::iota(li.begin(), li.end(), 0); // Find the value 3 in the list auto it{ find(li.begin(), li.end(), 3) }; // Insert 8 right before 3. li.insert(it, 8); for (int i : li) // for loop with iterators std::cout << i << ' '; std::cout << '\n'; return 0; } |
This prints the values
0 1 2 8 3 4 5
When a searching algorithm doesn’t find what it was looking for, it returns the end iterator.
If we didn’t know for sure that 3 is an element of li, we’d have to check if std::find found it before we use the returned iterator for anything else.
|
1 2 3 4 5 6 7 8 |
if (it == li.end()) { std::cout << "3 was not found\n"; } else { // ... } |
sort and reverse
In this example, we’ll sort a vector and then reverse it.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vect{ 7, -3, 6, 2, -5, 0, 4 }; // sort the vector std::sort(vect.begin(), vect.end()); for (int i : vect) { std::cout << i << ' '; } std::cout << '\n'; // reverse the vector std::reverse(vect.begin(), vect.end()); for (int i : vect) { std::cout << i << ' '; } std::cout << '\n'; return 0; } |
This produces the result:
-5 -3 0 2 4 6 7 7 6 4 2 0 -3 -5
Alternatively, we could pass a custom comparison function as the third argument to std::sort. There are several comparison functions in the <functional> header which we can use so we don’t have to write our own. We can pass std::greater to std::sort and remove the call to std::reverse. The vector will be sorted from high to low right away.
Note that std::sort() doesn’t work on list container classes -- the list class provides its own sort() member function, which is much more efficient than the generic version would be.
Conclusion
Although this is just a taste of the algorithms that STL provides, it should suffice to show how easy these are to use in conjunction with iterators and the basic container classes. There are enough other algorithms to fill up a whole chapter!
 22.1 -- std::string and std::wstring |
 Index |
 21.3 -- STL iterators overview |
Would it be better to place this set before learning about std::vector?
I tried looking for a specific value using string_view and std::map
illegal indirection is the error.
`mMap.begin()->second` is an `int`. Same for `mMap.end()->second`, just that this additionally causes undefined behavior.
You cannot iterate over `std::map` values alone, you need to iterate over the `std::map` elements, which are `std::pair`s. If you don't want to change `containsNuts()`, you can wrap it in a lambda
Since we're just iterating with just the second value from begin()->second to end()->second, would it not work with a llamda like
`std::find_if` wants to have iterators, but you're giving it `int`s. That doesn't work.
I had a look at the std::find_if implementation on cppreference.com and I understand it now.
However I tried implementing std::iota as a function of my own however I was getting an error that kept saying class T type is ambigious.
Your code compiles with the latest version of gcc, clang, and msvc. I suspect there's something else wrong.
Hello,
I am a student from India
I had made a code on TCS codevita platform of "minimum sum"
It has passed all public test cases but in private test cases its showing "Time limit exceeded error"
could you please figure out what modifications should I do in order to make code error free...
This is the problem statement...
Minimize The Sum
Problem Description
Given an array of integers, perform atmost K operations so that the sum of elements of final array is minimum. An operation is defined as follows -
Consider any 1 element from the array, arr[i].
Replace arr[i] by floor(arr[i]/2).
Perform next operations on updated array.
The task is to minimize the sum after atmost K operations.
Constraints
1 <= N, K <= 10^5.
Input
First line contains two integers N and K representing size of array and maximum numbers of operations that can be performed on the array respectively.
Second line contains N space separated integers denoting the elements of the array, arr.
Output
Print a single integer denoting the minimum sum of the final array.
Time Limit
1
Examples
Example 1
Input
4 3
20 7 5 4
Output
17
Explanation
Operation 1 -> Select 20. Replace it by 10.
New array = [10, 7, 5, 4]
Operation 2 -> Select 10. Replace it by 5.
New array = [5, 7, 5, 4].
Operation 3 -> Select 7. Replace it by 3.
New array = [5,3,5,4].
Sum = 17.
And this is my code-
Thank you...
Waiting for your reply at earliest..
BTW your tutorials are awesome.
First to your code, because it doesn't seem like you read to tutorials or at least never had a quiz solution reviewed.
- Declare one variable per line.
- Initialize variables with list initialization.
- Declare variables in the smallest scope possible.
- Name variables descriptively.
- Use ++prefix unless you need postfix++
- `n` is a duplicate of `N`
- You're performing integer arithmetic, you don't need `std::floor`.
- You can't create arrays with a size that's unknown at compile-time. Your code is invalid C++. Disable compiler extensions.
Get those straight and we can look into your algorithm.
All your asked corrections I had performed in my code..
Thanks for your feedback..
The below mentioned is the new and corrected code
I forgot to add "break" statement in line no. 31..
Plz review..
That was quick, nice.
You're now overflowing the array if `array_size` is larger than 50. Use a `std::vector` to create the array after you know the required size.
`size` is a duplicate of `array_size`, remove it.
Line 16, 20, 25, 37 can all use list initialization. The loops can be range-based for-loops.
So, to your algorithm
Assuming all elements are > 0, line 27 is always true. The loop (line 25+) always stops on the first iteration. This makes your code incorrect. You don't need this loop at all if you sort the array, which you do, because than the highest element is always at index 0 (Or index 1 if you divided the element at index 0).
First, complexity, this is what makes your algorithm slow:
-The while-loop runs `operations` times
--The for-loop runs `array_size` times
--`std::sort` internally runs `array_size * log(array_size)` times
Overall complexity is `operations * array_size * log(array_size)`. That's horrendous.
You don't even need to sort the entire array. All you need to do is find the first `operations` largest elements. You'll never touch any elements smaller than those. When you've found those elements, you can sort them. Then halve the largest of those elements until you run out of operations. You can probably even do some smart math to figure out how often you have to halve the largest element so that you don't have to re-visit it, but I'll leave that up to you.
"some combination of algorithms and container types may not work, may cause infinite loops, or may work but be extremely poor performing. So use these at your risk."
Hi, should I always rely upon them in the classes you mention in this section ?
Hi,
regarding the code line
What kind of type does it return?
I could only check its returned value by
It returns an `std::list::iterator`. `operator*` or `operator->` give you access to the value.
Of course... Thank you!
Hi,
In the last example:
std::sort(vect.begin(), vect.end()); // sort the list
std::reverse(vect.begin(), vect.end()); // reverse the list
Comment should say sort the vector!?
Thanks for lessons! Keep it up!!!
You can think of a vector as a list, so I wouldn't say to comment is wrong. However in the context of the lesson, I agree that it can be confusing. I'll update the lesson later, thanks for pointing it out :)
EDIT: Lesson amended, thanks again
The second paragraph says "algorithms are implemented as global functions", but the examples use `std::sort()` and `std::reverse()`, which one is true?
They're inside the std namespace. I removed the word global, as it was misleading.
Hi, thanks again for all the tutorials :D They really got me started with programming :D Btw, are there any topics about type traits or metaprogramming coming?
I don't know about Alex' plans about these topics.
C++20 adds constraints and concepts, those should make restrictions of templates a lot easier. You can learn about type traits if you want to, but it might be worth waiting for C++20.
Perhaps eventually, but not soon. There are other topics I want to get to first.
where is the chapter on STL algorithms you mentioned in the above tutorial?
Hasn't been written yet.
Will it take more time? thank you.
As others have pointed out, iterators should use pre-increment operators.
The post-increment version can be more expensive if the iterator is expensive to copy because post-increment implicitly creates a copy.
The compiler may not be able to elide that copy.
Lesson updated. This whole chapter is due for a serious revision pass.
Thank you, much appreciated.
Hopefully you'll be pleased to hear that I regularly recommend this tutorial because of its attention to the more modern features of C++ (i.e. from C++11 onwards).
Thanks! On this note, I'm doing another full pass on the existing lessons to add new stuff and integrate best practices. So even more C++11/14/17 goodness will be coming over the next months and year!
Hi Pharap,
>> "As others have pointed out, iterators should use pre-increment operators."
I don't see anyone else, at least in this chapter, having pointed out this fact. It would be of great help to fellow learners if you or someone else could explain why pre-increment of iterators is better than post. How are the two any different from each other?
I know that a = ++b is different from a = b++. But if there's no assignment going on, then how is b++ different from ++b? In both cases, 'b' would become 'b + 1'.
Hi Nitin!
Recap: The ++prefix operator returns the value after incrementing it. The postfix++ operator returns the value before incrementing it.
Somehow, the code in the article doesn't look like it's from you, with that using directive and nCount++ instead of ++nCount.
Maybe you're too busy, so here you go:
or alternatively
Same for the next example:
or
and here's the last one:
or
The articles in chapter 16 and beyond still need a stylistic update. :( Thanks for reminding me that I need to get to that.
When will be the full chapter on STL algorithm be available online?
Honestly, not likely all that soon. It's still on my to-do but I haven't had much time to devote to new articles lately.
can't wait for the STL algorithms chapter.
Me too. :)
What's wrong with my code? Please help I'm trying to replace a pair.
I corrected your program
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
map<int,string> items;
items.insert(make_pair(5,".orange"));
items.insert(make_pair(6,".apple"));
items.insert(make_pair(1,".grape"));
map<int,string>::iterator counter;
//counter = find(items.begin(),items.end(),make_pair(1,".grape"));
counter=items.find(1); // you have to find value by key
// map<int,string>::iterator counterx;
items.insert(counter,make_pair(54,".step"));
map<int,string>::iterator counterxx;
for(counterxx = items.begin();counterxx != items.end();counterxx++){ // counterxx not counter
cout<<counterxx->first<<counterxx->second<<endl;
}
return 0;
}
Here is the result of the program. I made some remarks about your program.
Here is the result of the program.
Output:
1.grape
5.orange
6.apple
54.step
great
Section "find (and list::insert)", in code, line-12:
We cannot use const_iterator because we are changing(both read and write operations are performed) the container class through the iterator. Using const_iterator produces a bunch of error that basically complains about 'not being able to find a suitable insert() for std::list<int>::const_iterator it' and other conversions. Using list<int>::iterator solves the problem:
Fixed. Thanks!
Typo ("it's" should be "its"): "...the list class provides it’s own sort() member function..."
Fixed. Thanks!
I'm trying to substitute the for loops for while loops in the last example, but I am having no success. Is there anyone who can help me with this? Thanks!
-- Edit
The first one is working, while the second one not! I'm having an assertion error telling me that the vector operator is not dereferencable.
Code:
#include
#include
#include
int main()
{
using namespace std;
vector vect;
vect.push_back(7);
vect.push_back(-3);
vect.push_back(6);
vect.push_back(2);
vect.push_back(-5);
vect.push_back(0);
vect.push_back(4);
sort(vect.begin(), vect.end()); // sort the list
vector::const_iterator it; // declare an iterator
it = vect.begin();
while (it != vect.end())
{
cout << *it << " ";
it++;
}
cout << endl;
reverse(vect.begin(), vect.end()); // reverse the list
for (it = vect.begin(); it != vect.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
Here's a working implementation:
These tutorials are Great!!!
Can you please add tutorials on the new features in c++14.
Also it would be great to have tutorials on uses of specific header files. Like a tutorial on <i>graphics</i> header file.
Dear Alex,
I have read through all your tutorials twice already and I still come back frequently for references, just because this is so good for someone who does not have a CS background like me. Now I am really looking forward to your STL algorithm chapters that you mentioned earlier as well as any other materials. However it looks like this site is not updated since about 2 years ago, so I am kinda wondering if you are still going to add in more materials as you said.
Thank you again and best wishes.
Just a minor typo, you wrote "provides it’s own sort() member function" instead of "its"
Dear Alex,
Also there is much left in STL.
Please do provide tutorials on STL in C++ in more detail
Dear Alex,
When are you starting with Data Structures in C++?
Please provide us tutorials for data structures in c++
Hi, man, when I was trying to compile the find code. g++ said "find.cpp: In function ‘int main()’:
find.cpp:15:20: error: no matching function for call to ‘std::list::insert(std::list::const_iterator&, int)’
find.cpp:15:20: note: candidates are:
/usr/include/c++/4.6/bits/list.tcc:99:5: note: std::list::iterator std::list::insert(std::list::iterator, const value_type&) [with _Tp = int, _Alloc = std::allocator, std::list::iterator = std::_List_iterator, std::list::value_type = int]
/usr/include/c++/4.6/bits/list.tcc:99:5: note: no known conversion for argument 1 from ‘std::list::const_iterator {aka std::_List_const_iterator}’ to ‘std::_List_iterator’
/usr/include/c++/4.6/bits/stl_list.h:1095:7: note: void std::list::insert(std::list::iterator, std::list::size_type, const value_type&) [with _Tp = int, _Alloc = std::allocator, std::list::iterator = std::_List_iterator, std::list::size_type = unsigned int, std::list::value_type = int]
/usr/include/c++/4.6/bits/stl_list.h:1095:7: note: candidate expects 3 arguments, 2 provided
/usr/include/c++/4.6/bits/stl_list.h:1116:9: note: template void std::list::insert(std::list::iterator, _InputIterator, _InputIterator) [with _InputIterator = _InputIterator, _Tp = int, _Alloc = std::allocator, std::list::iterator = std::_List_iterator]
and I need to
#include
#include
#include
int main()
{
using namespace std;
list li;
for (int nCount=0; nCount < 6; nCount++)
li.push_back(nCount);
//list::const_iterator it; // declare an iterator
_List_iterator it; // declare an iterator
it = find(li.begin(), li.end(), 3); // find the value 3 in the list
li.insert(it, 8); // use list::insert to insert the value 8 before it
for (it = li.begin(); it != li.end(); it++) // for loop with iterators
cout << *it << " ";
cout << endl;
}
~
~
~
~
~
~
~
~
~
~
"find.cpp" 22L, 572C 1,1 All
"
to satisfy the compiler,
On line 12 the iterator should be declared as follows:
list::iterator it;
This makes it a read/write iterator and will allow it to work with the list::insert function.
Sorry line 12 should be: