第4章 Container

reference 引用

Declaring references

Reference is a new way to manipulate objects in C++

– char c; // a character

– char* p = &c; // a pointer to a character

– char &r = c; // a reference to a character

区分指针*:

`int* p = &c; //标点，不参与计算，表示作用

*p = c;` //运算符，参与计算，计算后有结果

同理区分引用&

– char* p = &c; // 运算符，取c的地址

– char& r = c; // 标点，表示r是引用类型。等号右边必须是变量，而不是常量（变量的值，只能被读取，不能被写入）。r表示c的别名

    int main(){
      char c = 'A';
      char& r = c;
      r = 'B';
      cout << "c:" << c << endl;
      cout << "r:" << r << endl;
      c = 'C';
      cout << "c:" << c << endl;
      cout << "r:" << r << endl;
    }
    /*
    输出
    c: B
    r: B
    c: C
    r: C
    */

• Local or global variables

– type& refname = name;

– For ordinary variables, the initial value is required

• In parameter lists and member variables

– type& refname

– Binding defined by caller or constructor

References

• Declares a new name for an existing object 
int X = 47; 
int& Y = X; // Y is a reference to X 
// X and Y now refer to the same variable 
cout << "Y = " << y; // prints Y = 47 
Y = 18; 
cout << "X = " << x; // prints X = 18

Rules of references

• References must be initialized when defined

• Initialization establishes a binding

• In declaration

int x = 3;

int& y = x;

const int& z = x; z不能被修改，x可以被修改

• As a function argument

void f ( int& x ); 

f(y); // initialized when function is called

    void f(int& x){
      x++;
      cout << "in f() x = " << x << endl;
     }
    int main(){
      int a = 51;
      cout << "b4 f() a =" << a << endl;
      f(a);
      cout << "after f() a =" << a << endl;
    }
    /*
    输出：
    b4 f() a = 51
    in f() x = 52
    after f() a = 52
    
    把a传入后，x就是a的别名，对x操作就是对a操作，所以a的值会发生变化
    */

const作用：

void f(const int& x){
  x++;
  cout << "in f() x = " << x << endl;
 }
int main(){
  int a = 51;
  cout << "b4 f() a =" << a << endl;
  f(a);
  cout << "after f() a =" << a << endl;
}
//编译后会错误，不能给x++，因为x是const，不能被修改

• Bindings don’t change at run time, unlike pointers

• Assignment changes the object referred-to

int& y = x;

y = 12; // Changes value of x

• The target of a reference must have a location!

void func(int &x);

func (i * 3); // Warning or error!

因为i * 3结果是右值，不能赋给左值x

void f(int& x){
  x++;
  cout << "in f() x = " << x << endl;
 }
int main(){
  int a = 51;
  cout << "b4 f() a =" << a << endl;
  f(a + 2);
  cout << "after f() a =" << a << endl;
}

/*
f(a+2)不能传给void f(int& x)，会编译错误
如果改成void f(int x)可以编译通过
*/

Pointers vs. References

References

• can’t be null

• are dependent on an existing variable, they are an alias(别名) for an variable

• can’t change to a new “address” location

• Pointers

– can be set to null

– pointer is independent of existing objects

– can change to point to a different address

Restrictions

• No references to references 没有引用的引用

• No pointers to references 没有指向引用的指针

int&* p; // illegal *号离p近说明是指针

– Reference to pointer is ok 指针的引用可以

void f(int*& p);

• No arrays of references没有引用的数组

Container

A personal notebook

• It allows notes to be stored.

• It has no limit on the number of notes it can

store.

• It will show individual notes.

• It will tell us how many notes it is currently

storing.

Collection

• Collection objects are objects that can store an

arbitrary number of other objects.

What is STL

• STL = Standard Template Library

• Part of the ISO Standard C++ Library

• Data Structures and algorithms for C++.

Why should I use STL?

• Reduce development time.

–Data-structures already written and debugged.

• Code readability

–Fit more meaningful stuff（东西） on one page.

• Robustness 健壮性

–STL data structures grow automatically.

• Portable code. 可移植性

• Maintainable code 可维护代码

• Easy

C++ Standard Library

• Library includes:

–A Pair class (pairs of anything, int/int, int/char, etc)

–Containers

• Vector (expandable array) 扩展数组

• Deque (expandable array, expands at both ends)

• List (double-linked)

• Sets and Maps

–Basic Algorithms (sort, search, etc)

• All identifiers in library are in std namespace :

using namespace std;

The three parts of STL

• Containers

• Algorithms

• Iterators

The ‘Top 3’ data structures

• map

–Any key type, any value type.

–Sorted.

• vector

–Like c array, but auto-extending.

• list

–doubly-linked list

All Sequential Containers

• vector: variable array

• deque: dual-end queue

• list: double-linked-list

• forward_list: as it

• array: as “array”

• string: char. array

Example using the vector class

 #include <iostream>
    #include <vector>
    //Use “namespace std” so that you can refer to vectors in C++ library
    using namespace std;
    
    int main(){
      //Declare a vector of ints(no need to worry about size)
      vector<int> x;
      //Add elements
      for(int a = 0; a < 1000; a++){
        a.push_back(a);
      }
      //Have a pre-defined iterator for vector,can use it to print out thr items in vector
      vector<int>::iterator p;
      for(p = x.begin(); p < x.end(); p++){
        cout << *p << " ";//能用*因为重载了*运算符
      }
      return 0;
    }

    #include <iostream>
    #include <vector>
    //Use “namespace std” so that you can refer to vectors in C++ library
    using namespace std;
    
    int main(){
      vector<int> x;
      for(int i = 0; i < 100; i++){
        x.push_back(i);
      }
      for(auto i: x){
        cout << i << " ";
      }
      return 0;
    }

generic classes泛型类

vector notes;

• Have to specify two types: the type of the collection itself (here: vector) and the type of the elements that we plan to store in the collection

(here: string)

vector

• It is able to increase its internal capacity as required: as more items are added, it simply makes enough room for them.

• It keeps its own private count of how many items it is currently storing. Its size method returns the number of objects currently stored in it.

• It maintains the order of items you insert into it. You can later retrieve them in the same order.

Basic Vector Operations

• Constructors

vector c;

vector c1(c2); 用c2创建c1

• Simple Methods

V.size( ) // num items

V.empty( ) // empty?

==, !=, <, >, <=, >=

V.swap(v2) // swap

• Iterators

I.begin( ) // first position

I.end( ) // last position

• Element access

V.at(index)

V[index]

V.front( ) // first item

V.back( ) // last item

//可以这么遍历
for(int i = 0; i < x.size(); i++){
  cout << x[i] << " ";
}

• Add/Remove/Find

V.push_back(e)

V.pop_back( )

v.insert(pos, e)

V.erase(pos)

V.clear( )

V.find(first, last, item)

Two ways to use Vector

Preallocate

vector<int> v(130);//
v[80] = 1;//ok
v[200] = 1;//bad

Grow tail

vector<int> v2;
int i;
while(cin >> i){
  v.push_back(i);
}

List Class

• Same basic concepts as vector

–Constructors

–Ability to compare lists (==, !=, <, <=, >, >=)

–Ability to access front and back of list

x.front(), x.back()

–Ability to assign items to a list, remove items

x.push_back(item)

x.push_front(item)

x.pop_back()

x.pop_front()

x.remove(item)

Sample List Application

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main(){
  //Declare a list of strings
  list<string> s;
  s.push_back("hello");
  s.push_back("world");
  s.push_front("tide");
  s.push_front("crimson");
  s.push_front("alabama");
  list<string>::iterator p;
  for(p = s.begin(); p != s.end(); p++){
    cout << *p << " ";
  }
  cout << endl;
}
/*
输出：
alabama crimson tide hello world

Note the termination condition for our iterator p != s.end( ) 
–Cannot use p < s.end( ) as with vectors, as the list elements may not be stored in order
*/

Example of Lists

list<int> L;
for(int i = 1; i  <= 5; i ++){
  L.push_back(i);
}
//delete second item
L.erase(++L.begin());
copy(L.begin(), L.end(), ostream_iterator<int>(cout, ","));//Prints:1, 2, 3, 5

Maintaining an ordered list

  #include <iostream>
    #include <list>
    #include <string>
    using namespace std;
    int main(){
      list<string> s;
      string t;
      list<string>::iterator p;
      for(int a = 0; a < 5; a++){
        cout << "enter a string:" ;
        cin >> t;
        p = s.begin();
        while(p != s.end() && *p < t){
          p++;
        }
        s.insert(p, t);
      }
      for(p = s.begin(); p != s.end(); p++){
        cout << *p << " ";
      }
      cout << endl;
    }

Maps

• Maps are collections that contain pairs of values.

• Pairs consist of a key and a value.

• Lookup works by supplying a key, and

retrieving a value.

• An example: a telephone book

Example Map Program

   #include <map>
    #include <string>
    
    map<string, float> price;
    price{"snapple"} = 0.75;
    price{"coke"} = 0.50;
    string item;
    double total = 0;
    while(cin >> item){
      total += price{item};
    }

Simple Example of Map

map<long, int> root;
root[4] = 2;
root[1000000] = 1000;
long l;
cin >> l;
if(root.count(l)){//如果在映射容器中存在带有键K的元素,则该函数返回1。如果容器中不存在键为K的元素,则返回0
  cout << root[l];
}else{
  cout << "Not perfect square";
}

Iterator

• Declaring

list::iterator li;

• Front of container

list L;

li = L.begin();

• Past the end

li = L.end();

• Can increment

list::iterator li;

list L;

li=L.begin();

++li; // Second thing;

• Can be dereferenced

*li = 10;

Algorithms

• Take iterators as arguments

list<int> L;
vector<int> V;
// put list in vector
copy( L.begin(), 
 L.end(), 
 V.begin() )

List Example Again

list<int> L; 
for(int i=1; i<=5; ++i)
 L.push_back(i);
//delete second item.
L.erase( ++L.begin() );
copy( L.begin(). L.end(),
 ostream_iterator<int>(cout, “,"));
// Prints: 1,2,3,5

for-each loop

A for-each loop iterates over the elements of arrays,vectors,or any other data sets.It assigns the value of the current element to the variable iterator declared inside the loop

for(type variable_name array/vector_name){
  loop statements
···
}

for-each循环，不能修改值，只能读取值

Example of for-each

 #include<iostream>
    using namespace std;
    int main()
    int arr[]=(1,2,3,4,5);//array initialization
    cout<<"The elements are:"
    for(int i arr){//auto
      cout << i << " ";
      }
    return 0;
    }

    #include<iostream>
    #include<vector>
    using namespace std;
    int main(】
    vector<int>vec=(11,22,33,44,S5,66}:
    cout<<"The elements are:"
    for(auto var: vec){
      cout << var << " ";
    }
    return 0;
    }

Pros and Cons 利弊

Advantages of foreach loop

o It eliminates the possibility of errors and makes the code more readable.

o Easy to implement

o Does not require pre-initialization of the iterator

Disadvantages of foreach loop

o Cannot directly access the corresponding element indices

o Cannot traverse the elements in reverse order

o It doesn’t allow the user to skip any element as it traverses over each one of them

Using your own classes in STL Containers

• Might need:

–Assignment Operator, operator=()

–Default Constructor

• For sorted types, like map<>

–Need less-than operator: operator<()

• Some types have this by default:

–int, char, string

• Some do not:

–char *

The type in containers

What’s the difference?

vectorv1;

vector<Student&>v2;

vector<Student*>v3;

Pitfalls 陷阱/隐患

• Accessing an invalid vector<> element.

vector v;

v[100]=1; // Whoops!

Solutions:

–use push_back()

–Preallocate with constructor.

–Reallocate with reserve()

–Check capacity()

• Inadvertently inserting into map<>.

if (foo[”bob”]==1) //silently created entry “bob”

Use count() to check for a key without creating a new entry.

if ( foo.count(“bob”) )

• Not using empty() on list<> .

–Slow

if ( my_list.count() == 0 ) { … }

–Fast

if ( my_list.empty() ) {…}

• Using invalid iterator

list<int> L;
list<int>::iterator li;
li = L.begin();
L.erase(li);
++li; // WRONG
• Use return value of erase to advance 
li = L.erase(li); // RIGHT