Main

Week 7

Some useful Bash commands

As you work on your projects, you may wish to find some files or check whether a package is installed. These commands are certainly not the only way this can be done, but they can help.

find and grep

The find Unix command is used to search for files. In combination with grep, it can be a powerful tool. 

 find /usr/include -name SDL\*.h
 find /usr/include -name SDL\*.h | grep image

Linux packages

 dpkg -l | grep libsdl

locate

This is a very handy command if it was configured properly on the system. You can search the /usr subtree for anything matching a certain string. 

 locate SDL

Command-line arguments in your bash scripts

Here is a simple script example that shows how you can access its command line arguments:

  1. #!/bin/bash
  2.  
  3. # Usage: args.sh arg1 arg2 arg3 ...
  4. echo "All the arguments: $@"
  5. echo "Just the last argument: ${*: -1:1}"
  6.  
  7. # Check that we have more than one argument and show the next-to-last one
  8. if [ $# -ge 1 ]; then
  9.   echo "The next-to-last argument: ${*: -2:1}"
  10.   echo "The last two arguments: ${*: -2:2}"
  11. fi
  12.  
  13. # Loop through arguments
  14. echo "All arguments one by one:"
  15. for arg in "$@"; do
  16.     echo "$arg"
  17. done
[$[Get Code]]

Here is some example output: 

$ ./args.sh 1 2 3
All the arguments: 1 2 3
Just the last argument: 3
The next-to-last argument: 2
The last two arguments: 2 3
All arguments one by one:
1
2
3

C++ Sets

The set and the multiset are both containers that manage data components that have keys, but the keys and the rest of the data are not separated and placed in pair values like they are in maps and multimaps. In the simplest cases the data in a set or multiset component consists of just the key alone.

The essential difference between the set and the multiset is that in a set the keys must be unique, while a multiset permits duplicate keys. This is analogous to the situation with maps and multimaps In both sets and multisets, the sort order of components is the sort order of the keys, so the components in a multiset that have duplicate keys may appear in any order. Nearly everything said here about sets is also true of multisets, with minor differences showing up in the count() member function and one of the insert() member functions.

How do you decide between a set and a map?

If you need the following features:

  • add an element, but do not allow duplicates
  • remove elements
  • get count of elements (distinct elements)
  • check whether elements are present in set

then a set is probably sufficient for your needs.

  1.  set<int> s;
  2.  
  3.  for(int i = 1; i <= 100; i++) {
  4.       s.insert(i); // Insert 100 elements, [1..100]
  5.  }
  6.  
  7.  s.insert(42); // does nothing, 42 already exists in set
  8.  
  9.  // for(int i = 2; i <= s.size(); i += 2) {  !! This is not a good idea because s is modified in the loop
  10. int num_elems = s.size();
  11. for (int i = 2; i <= num_elems; i+=2) {
  12.       s.erase(i); // Erase even values
  13.  }
  14.  
  15.  int n = int(s.size()); // n will be 50
[$[Get Code]]

First look at STL algorithms and lambda expressions

To get us started with STL algorithms and lambda expressions, let us rewrite the last loop above in a more concise, but equivalent, way of erasing even values: 

for_each(s.begin(), s.end(),
	       [&s](int i)->void { if (i % 2 == 0) s.erase(i); });

The for_each algorithm applies the function provided as the third argument to the range of container elements specified by the first and second iterator arguments. It's an example of a generic algorithm that can be applied to any container.

We will look at lambda expressions in more detail during next lecture, but in general, you can use them to define functions that you only need to call once. The function doesn't have a name, but it can have parameters, a return value and a function body, just like regular functions.

Continuing with set operations

The push_back() member may not be used with set. It make sense: since the order of elements in set does not matter, push_back() is not applicable here.

Since set is not a linear container, it’s impossible to take the element in set by index. Therefore, the only way to traverse the elements of set is to use iterators.

  1.  // Calculate the sum of elements in set
  2.  set<int> S;
  3.  // ...
  4.  int r = 0;
  5.  for(set<int>::const_iterator it = S.begin(); it != S.end(); it++) {
  6.       r += *it;
  7.  }
[$[Get Code]]

It's more elegant to use traversing macros here. Why? Imagine you have a set< pair<string, pair< int, vector<int> > >. How to traverse it? Write down the iterator type name? No need for that -- just use auto:

  1.  set< pair<string, pair< int, vector<int> > > SS;
  2.  int total = 0;
  3.  for(auto it = SS.begin(); it != SS.end(); it++) {
  4.       total += it->second.first;
  5.  }
[$[Get Code]]

Notice the 'it->second.first' syntax. Since 'it' is an iterator, we need to take an object from 'it' before operating. So, the correct syntax would be '(*it).second.first'. However, it’s easier to write 'something->' than '(*something)'. The full explanation will be quite long –just remember that, for iterators, both syntaxes are allowed.

To determine whether some element is present in set use 'find()' member function. Don’t be confused, though: there are several 'find()' ’s in STL. There is a global algorithm 'find()', which takes two iterators, element, and works for O(N). It is possible to use it for searching for element in set, but why use an O(N) algorithm while there exists an O(log N) one? While searching in set and map (and also in multiset/multimap, hash_map/hash_set, etc.) do not use global find – instead, use member function 'set::find()'. As 'ordinal' find, set::find will return an iterator, either to the element found, or to 'end()'. So, the element presence check looks like this:

  1.  set<int> s;
  2.  // ...
  3.  if(s.find(42) != s.end()) {
  4.       // 42 presents in set
  5.  }
  6.  else {
  7.       // 42 not presents in set
  8.  }
[$[Get Code]]

Another algorithm that works for O(log N) while called as member function is count. Some people think that

  1.  if(s.count(42) != 0) {
  2.       // …
  3.  }
[$[Get Code]]

or even

  1.  if(s.count(42)) {
  2.       // …
  3.  }
[$[Get Code]]

is easier to write. Personally, I don’t think so. Using count() in set/map is overkill: the element is either present or not. Insted you should use find(), and if that's too much typing, you can define some macros if you do this frequently:

  1.  #define present(container, element) (container.find(element) != container.end())
  2.  #define cpresent(container, element) (find(container.begin(),container.end()),element) != container.end())
[$[Get Code]]

Here, present() returns whether the element presents in the container with member function find() (i.e. set/map, etc.) while cpresent is for vector.

To erase an element from set use the erase() function.

  1.  set<int> s;
  2.  // …
  3.  s.insert(54);
  4.  s.erase(29);
[$[Get Code]]

The erase() function also has the interval form:

  1.  set<int> s;
  2.  // ..
  3.  
  4.  set<int>::iterator it1, it2;
  5.  it1 = s.find(10);
  6.  it2 = s.find(100);
  7.  // Will work if it1 and it2 are valid iterators, i.e. values 10 and 100 present in set.
  8.  s.erase(it1, it2); // Note that 10 will be deleted, but 100 will remain in the container
  9. Set has an interval constructor:
  10.  int data[5] = { 5, 1, 4, 2, 3 };
  11.  set<int> S(data, data+5);
  12. It gives us a simple way to get rid of duplicates in vector, and sort it:
  13.  vector<int> v;
  14.  // …
  15.  set<int> s(all(v));
  16.  vector<int> v2(all(s));
[$[Get Code]]

Here v2 will contain the same elements as v but sorted in ascending order and with duplicates removed.

Green Marinee theme adapted by David Gilbert, powered by PmWiki