Cpp-Primer-5th-Exercises-Chapter-9

1
2
3
4

// (a): list
// (b): deque
// (c): vector (vector.sort())

1
2
3
4
5

int main()
{
  std::list<std::deque<int>> sample;
}

1
2
3
4

// iterators which make a iterator range must be:
// 1. both point to one container's elements, or point to the off the end element of one container
// 2. iterator begin could be repeated increase to reach end iterator, in another word, end iterator must not be in front of begin iterator.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

bool find_i(vector<int>::iterator begin, vector<int>::iterator end, int i)
{
  while(begin != end && begin < end)
    {
      if(*begin == i) return true;
      else ++begin;
    }
  return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// Chinese translation verseion of this exercise is ambiguous
// Guess that function should return a iterator
using vit = vector<int>::iterator;
vit find_i(vit begin, vit end, int i)
{
  while(begin != end && begin < end)
    {
      if(*begin == i) return begin;
      else ++begin;
    }
  return end;
}

1
2
3
4
5
6
7

int main()
{
  list<int> lst1;
  list<int>::iterator iter1 = lst1.begin(), iter2 = lst1.end();
  while(iter1 != iter2) continue; // iterator of list<int> does not support < operator(for that the elements whitin is not stored in sequence)
}

1
2
3

// That exercise is confusing, define 'index'
// vector<int>::size_type

1
2
3
4

// confused too
// read: list<string>::const_reference(const_iterator)
// write: list<string>::reference(iterator)

1
2
3

// begin(): returns a const_iterator or a iterator based on whether the calling iterator is const or not.
// cbegin(): always returns a const_iterator.

1
2
3
4
5
6
7
8

int main()
{
  vector<int> v1;
  const vector<int> v2;
  auto it1 = v1.begin(), it2 = v2.begin(); // illegal see P61 2.5.2
  auto it3 = v1.cbegin(), it4 = v2.cbegin(); // both const_iterator
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int main()
{
  vector<int> iv1;		// empty
  vector<int> iv2 = {1, 2, 3, 4, 5}; // {1, 2, 3, 4, 5}
  vector<int> iv3 = iv2;	     // {1, 2, 3, 4, 5"
  vector<int> iv4(iv3.begin(), iv3.end()); // {1, 2, 3, 4, 5"
  vector<int> iv5(6);			   // {0, 0, 0, 0, 0, 0}
  vector<int> iv6(6, 1);		   // {1, 1, 1, 1, 1, 1}
}

1
2
3
4
5

// container which is copy initialized with another container:
// type of container must match, type of element of container must match.
// container which is directly initialized with two iterators:
// type of container could be different, type of element of container could be different, too, only require that conversion from one element type to another is capable.

1
2
3
4
5
6
7
8

int main()
{
  list<int> lst_i = {1, 2, 3, 4, 5};
  vector<double> vec_d1(lst_i.begin(), lst_i.end());
  vector<int> vec_i= {1, 2, 3, 4, 5};
  vector<double> vec_d2(vec_i.begin(), vec_i.end());
}

1
2
3
4
5
6
7

int main()
{
  list<const char *> lst_c = {"hello", "world"};
  vector<string> vec_s;
  vec_s.assign(lst_c.begin(), lst_c.end());
}

1
2
3
4
5

bool is_equal_iv(vector<int> iv1, vector<int> iv2)
{
  return iv1 == iv2;
}

1
2
3
4
5
6

bool is_equal_iv_il(vector<int> iv, list<int> il)
{
  vector<int> iv2(il.begin(), il.end());
  return iv == iv2;
}

1
2
3
4
5
6

// c1 and c2 are both containers
// if(c1 < c2)
// 1. c1 and c2 must be same type, which means they have identical container type and element type.
// 2. the type of element should support '<' operator.
// 3. both should not be unordered associative containers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int main()
{
  string s;
  deque<string> ds;
  while(cin >> s)
    ds.push_back(s);
  deque<string>::iterator bit = ds.begin(), eit = ds.end();
  while(bit != eit)
    {
      cout << *bit << endl;
      ++bit;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int main()
{
  string s;
  list<string> ds;
  while(cin >> s)
    ds.push_back(s);
  list<string>::iterator bit = ds.begin(), eit = ds.end();
  while(bit != eit)
    {
      cout << *bit << endl;
      ++bit;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int main()
{
  list<int> li = {1, 2, 3, 4, 5};
  deque<int> di1;
  deque<int> di2;
  for(const auto &i : li)
    (i % 2) ? di1.push_back(i) : di2.push_back(i);
  for(const auto &j : di1)
    cout << j << endl;
  for(const auto &k : di2)
    cout << k << endl;
}

1
2
3
4

// if insert element into vector type object
// program works
// but processing would be really slow, every time a element is inserted, the memory space of vector type object may be re-allocated.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// Changing the size of vector type object may cause re-allocation of its memory space.
// the iterator iter and mid in original program would be invalid when program processing
int main()
{
  vector<int> iv = {1, 2, 2, 4, 2, 6, 2, 3, 4, 5};
  list<int> il(iv.begin(), iv.end());
  list<int>::iterator iter = il.begin();
  vector<int>::difference_type count = 0, dff_iv = iv.size() / 2;
  while(count != dff_iv)
    {
      if(*iter == 2)
      il.insert(iter, 2 * 2);
      ++count;
      ++iter;
    }
  iv.assign(il.begin(), il.end());
  for(const auto &i : iv)
    cout << i << endl;
}

1
2

// va1, va2, va3 and va4 all equals to the first element of container c.

1
2
3
4
5
6
7
8
9

int main()
{
  vector<int> iv;
  cout << iv.front() << endl;	// segment fault
  cout << *iv.begin() << endl;	// same
  cout << iv[0] << endl;	// same
  cout << iv.at(0) << endl;	// std::out_of_range
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// c.erase(elem1, elem2)
// if elem1 and elem2 ponits to same element, the iterator range is empty, so erase nothing, return this elem1(or elem2, no matter, identical)
// if elem2 is a end off iterator, remove the one pointed by elem1 and till the last one, return elem2
// if elem1 and elem2 both end off iterator, remove nothing, return end off iterator
int main()
{
  list<int> li = {0, 1, 2, 3, 4};
  auto iter1 = li.begin(), iter2 = iter1;
  auto iter = li.erase(iter1, iter2);
  cout << *iter << endl;
  auto iter3 = li.end(), iter4 = iter3;
  iter = li.erase(iter3, iter4);
  cout << *iter << endl;	// the result is 5, there is no 5 in li, this operation is illegal
  // iter is the end off iterator
}

 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

int main()
{
  int ia[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89};
  vector<int> iv;
  list<int> il;
  auto ia_bg = begin(ia), ia_ed = end(ia);
  while(ia_bg != ia_ed)
    {
      iv.push_back(*ia_bg);
      il.push_back(*ia_bg);
      ++ia_bg;
    }
  auto it_iv = iv.begin();
  while(it_iv != iv.end())
    {
      if(*it_iv % 2 == 0)
      it_iv = iv.erase(it_iv);
      else
      ++it_iv;
    }
  auto it_il = il.begin();
  while(it_il != il.end())
    {
      if(*it_il % 2)
      it_il= il.erase(it_il);
      else
      ++it_il;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int main()
{
  forward_list<int> flst = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  auto prev = flst.before_begin();
  auto curr = flst.begin();
  while(curr != flst.end())
    {
      if(*curr % 2)
      curr = flst.erase_after(prev);
      else
      {
	prev = curr;
	++curr;
      }
    }
}

 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

void insert_ss(forward_list<string> &flst, string s1, string s2)
{
  auto curr = flst.begin();
  decltype(curr) temp;
  while(curr != flst.end())
    {
      if(*curr == s1)
      {
	flst.insert_after(curr, s2);
	return;
      }
      else
      {
	temp = curr;
	++curr;
      }
    }
  flst.insert_after(temp, s2);
}
int main()
{
  forward_list<string> sample = {"hello", "amigo", "aloha", "nihao"};
  insert_ss(sample, "amigo", "test");
  insert_ss(sample, "surprise", "ok");
  for(const auto &s : sample)
    cout << s << endl;
}

1
2
3

// vec.resize(100) will extend vec to 100 elements, 75 elements value initialized and put in right side of the original 25.
// vec.resize(10) will delete the tail 90 elements of this container.

1
2

// The one parameter version of resize requires that the element type must support value initialization, or it must has a default constructor if it is a class type.

 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

// list<element_type>::iterator and forward_list<element_type>::iterator do not support 'iter += n' operation for that list<element_type> object is not stored in sequence memory.
int main()
{
  list<int> li = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  // for forawrd_list, forward_list<int>::iterator prev = li.before_begin();
  auto iter = li.begin();
  while(iter != li.end())
    {
      if(*iter % 2)
      {
	iter = li.insert(iter, *iter);
	++(++iter);
	// for forward_list
	// iter = li.insert_after(iter, *iter);
	// prev = iter;
	// ++iter;
      }
      else
      // for forward_list
      // iter = li.erase_after(prev);
      iter = li.erase(iter);
    }
  for(const auto &i : li)
    cout << i << endl;
}

1
2
3
4
5

// iter = vi.insert(iter, *iter++);
// illegal
// for that the evaluation of arguments(initialization of parameters) of a function calling maybe not in order,
// in this case, iter may increase it self at first or later, that calling may have different results per processing, which is not allowed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// for vector, if do not assign the return value to begin, begin would be a invalid iterator, causes a run time error,
int main()
{
  vector<int> v = {1, 2, 3, 4, 5};
  auto beg = v.begin();
  while(beg != v.end())
    {
      ++beg;
      v.insert(beg, 42);	// segment fault
      ++beg;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// infinite loop, always insert a copy at the front of the fitst encountered odd number.
int main()
{
  vector<int> vi = {1, 2, 3, 4, 5};
  auto iter = vi.begin();
  while(iter != vi.end())
    {
      if(*iter % 2)
      iter = vi.insert(iter, *iter);
      ++iter;
    }
}

1
2
3

// A vector's capacity means the number of elements it can hold whitout memory re-allocation
// size means the number of elements the vector contains now.

1
2

// Never.

1
2
3

// For list is not stored in sequence memory, it does not need memory re-allocation when insert a new element.
// And for array type capacity is unnecessary, because array's size is constant, add or delete element is forbidden, there is no memory re-allocation either, so size as member function is enough.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int main()
{
  vector<int> vi;
  cout << "size " << vi.size() << " "
       << "capacity " << vi.capacity() << endl;
  vi.push_back(1);
  cout << "size " << vi.size() << " "
       << "capacity " << vi.capacity() << endl;
  vi.push_back(2);
  cout << "size " << vi.size() << " "
       << "capacity " << vi.capacity() << endl;
  vi.push_back(3);
  cout << "size " << vi.size() << " "
       << "capacity " << vi.capacity() << endl;
  vi.push_back(4);
  vi.push_back(5);
  cout << "size " << vi.size() << " "
       << "capacity " << vi.capacity() << endl;
}

1
2
3

// Only when 1.5*svec.size() > svec.capacity() (1024) or words read in exceeds svec.capacity() there is a memory re-allocation for svec;
// else just put new elements in the back of svec.

1
2
3
4
5

// if read in 256 words: capacity 1024
// 512 words: capacity 1024
// 1000 words: capacity 2048
// 1048 words: capacity 2048

1
2
3
4
5
6

int main()
{
  vector<char> vc = {'h', 'e', 'l', 'l', 'o'};
  string s(vc.begin(), vc.end());
}

1
2
3
4
5
6
7
8
9

int main()
{
  string s;
  char c;
  s.reserve(100);
  while(cin >> c)
    s.push_back(c);
}

 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
31
32

string &my_replace(string &s, string oldVal, string newVal)
{
  string::difference_type len = oldVal.size();
  string::iterator iter1 = s.begin(), iter2;
  while(s.end() - iter1 >= len)
    {
      iter2 = iter1 + len;
      string temp(iter1, iter2);
      if(temp == oldVal)
      {
	iter1 = s.erase(iter1, iter2);
	iter1 = s.insert(iter1, newVal.begin(), newVal.end());
	iter1 += newVal.size();
      }
      else
      ++iter1;
    }
  return s;
}
int main()
{
  string s1 = "test test test test test skip test skiptesttest";
  my_replace(s1, "test", "yes");
  cout << s1 << endl;
  string s2 = "short";
  my_replace(s2, "testtest", "no");
  cout << s2 << endl;
  string s3 = "test test test skipendhere";
  my_replace(s3, "test", "yes");
  cout << s3 << endl;
}

 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

string &my_replace(string &s, string oldVal, string newVal)
{
  decltype(s.size()) index = 0, len = oldVal.size();
  while(s.size() - index >= len)
    {
      string temp = s.substr(index, len);
      if(temp == oldVal)
      {
	s.replace(index, len, newVal);
	index += newVal.size();
      }
      else
      ++index;
    }
  return s;
}
int main()
{
  string s1 = "test test test test test skip test skiptesttest";
  my_replace(s1, "test", "yes");
  cout << s1 << endl;
  string s2 = "short";
  my_replace(s2, "testtest", "no");
  cout << s2 << endl;
  string s3 = "test test test skipendhere";
  my_replace(s3, "test", "yes");
  cout << s3 << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

string complete_name(string name, string prefix, string suffix)
{
  auto beg = name.begin();
  beg = name.insert(beg, 1, ' ');
  name.insert(beg, prefix.begin(), prefix.end());
  name.append(" ");
  name.append(suffix);
  return name;
}
int main()
{
  string s = "Robert Jones";
  string result = complete_name(s, "Mr.", "Jr.");
  cout << result << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

string complete_name(string name, string prefix, string suffix)
{
  name.insert(0, " ");
  name.insert(0, prefix);
  name.insert(name.length(), " ");
  name.insert(name.length(), suffix);
  return name;
}
int main()
{
  string s = "Robert Jones";
  string result = complete_name(s, "Mr.", "Jr.");
  cout << result << endl;
}

 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
31
32
33
34
35

int main()
{
  string s("ab2c3d7R4E6");
  string number("0123456789");
  string albetical("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
  string::size_type index = 0;
  while((index = s.find_first_of(number, index)) != string::npos)
    {
      cout << "found number at index: " << index
	 << " element is: " << s[index] << endl;
      ++index;
    }
  index = 0;
  while((index = s.find_first_of(albetical, index)) != string::npos)
    {
      cout << "found albetical at index: " << index
	 << "element is: " << s[index] << endl;
      ++index;
    }
  index = 0;
  while((index = s.find_first_not_of(albetical, index)) != string::npos)
    {
      cout << "found number at index: " << index
	 << " element is: " << s[index] << endl;
      ++index;
    }
  index = 0;
  while((index = s.find_first_not_of(number, index)) != string::npos)
    {
      cout << "found albetical at index: " << index
	 << "element is: " << s[index] << endl;
      ++index;
    }
}

1
2

// string::npos

 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

int main(int argc, char *argv[])
{
  if(argc != 2)
    {
      cerr << "Invalid arguments, need 2, now " << argc << endl;
      return -1;
    }
  ifstream ifs(argv[argc - 1]);
  if(!ifs)
    {
      cerr << "Invalid file name " << argv[argc - 1] << endl;
      return -1;
    }
  string ascender("bdfhkltBDFHT");
  string descender("gjpqyGPY");
  string word, result;
  while(ifs >> word)
    {
      if(word.find_first_of(ascender) == string::npos &&
       word.find_first_of(descender) == string::npos)
      if(word.size() > result.size())
	result = word;
    }
  cout << result << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int main()
{
  vector<string> vsi = {"1", "2", "3"};
  int sum = 0;
  for(const auto &s : vsi)
    sum += stoi(s.substr(s.find_first_of("+-0123456789")));
  cout << sum << endl;
  vector<string> vsd = {"1.1", "2.2", "3.3"};
  double d_sum = 0.0;
  for(const auto &s : vsd)
    d_sum += stod(s.substr(s.find_first_of("+-.0123456789")));
  cout << d_sum << endl;
}

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

 unsigned month_transform(const string&);
 stru#+DATE
 {
#+DATE(const string &s);
   void print() {cout << year << " " << month << " " << day << endl;}
 private:
   unsigned year;
   unsigned month;
   unsigned day;
 };
 date::date(const string &s)
 {
   // type1: January 1, 1900
   string type1_symbol = ",";
   // type2: 1/1/1990
   string type2_symbol = "/";
   // type3: Jan 1 1900
   string type3_symbol = " ";
   string::size_type index;
   if((index = s.find(type1_symbol)) != string::npos)
     {
       auto index_of_first_number = s.find_first_of("0123456789");
       day = stoi(s.substr(index_of_first_number, index - index_of_first_number));
       string m = s.substr(0, index_of_first_number - 1);
       month = month_transform(m);
       auto index_of_next_number = s.find_first_of("0123456789", index_of_first_number + 1);
       year = stoi(s.substr(index_of_next_number));
     }
   else if((index = s.find(type2_symbol)) != string::npos)
     {
       auto index_of_first_number = s.find_first_of("0123456789");
       day = stoi(s.substr(index_of_first_number, index - index_of_first_number));
       index = s.find(type2_symbol, index_of_first_number + 1);
       auto index_of_second_number = s.find_first_of("0123456789", index_of_first_number + 1);
       month = stoi(s.substr(index_of_second_number, index - index_of_second_number));
       auto index_of_third_number = s.find_first_of("0123456789", index_of_second_number + 1);
       year = stoi(s.substr(index_of_third_number));
     }
   else if((index = s.find(type3_symbol)) != string::npos)
     {
       string m = s.substr(0, index);
       month = month_transform(m);
       auto index_of_first_number = s.find_first_of("0123456789");
       index = s.find(type3_symbol, index_of_first_number);
       day = stoi(s.substr(index_of_first_number, index - index_of_first_number));
       auto index_of_second_number = s.find_first_of("0123456789", index);
       year = stoi(s.substr(index_of_second_number));
     }
   else
     throw runtime_error("Invalid argument " + s);
 }
 unsigned month_transform(const string &s)
 {
   if(s == "January" || s == "Jan") return 1;
   else if(s == "February" || s == "Feb") return 2;
   else if(s == "March" || s == "Mar") return 3;
   else if(s == "April" || s == "Apr") return 4;
   else if(s == "May" || s == "May") return 5;
   else if(s == "June" || s == "Jun") return 6;
   else if(s == "July" || s == "Jul") return 7;
   else if(s == "August" || s == "Aug") return 8;
   else if(s == "September" || s == "Sep") return 9;
   else if(s == "October" || s == "Oct") return 10;
   else if(s == "November" || s == "Nov") return 11;
   else if(s == "December" || s == "Dec") return 12;
   else throw runtime_error("Invaild argument " + s);
 }
 int main()
 {
   string s1 = "January 1, 1990";
   string s2 = "1/1/1990";
   string s3 = "Jan 1 1990";
#+DATE date1(s1);
#+DATE1.print();
#+DATE date2(s2);
#+DATE2.print();
#+DATE date3(s3);
#+DATE3.print();
 }

 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

// As much I can do here, if given some functions on transforming char to int and the reverse transform, it would exactly meet the requirement
int main()
{
  string s = "(((1+2)+3)+4)";
  stack<char> sc;
  int temp = 0;
  for(const auto &c : s)
    {
      if(c != ')')
      {
	sc.push(c);
      }
      else
      {
	while(sc.top() != '(')
	  {
	    if(isdigit(sc.top())) temp += (sc.top() - 48);
	    sc.pop();
	  }
	sc.pop();
      }
    }
  cout << temp << endl;
}