C++/Data Structure/List — различия между версиями

Текущая версия на 10:24, 25 мая 2010

Содержание

1 A list splicing example.
2 An example of the transform algorithm.
3 Copy a list to a vector.
4 Create a reciprocal function object.
5 Define class and store in a list
6 Demonstrate advance() and distance() in list
7 Demonstrate bind2nd().
8 Demonstrate merge() in list
9 Demonstrate remove() in list
10 Demonstrate unique() in list
11 Demonstrate virtual functons: list interface
12 Difference between push_back() and push_front()
13 Elements can be put on the front or end of a list.
14 end() in list.
15 List basics: push, begin, end pop
16 Merge and splice lists.
17 Merge into descending order.
18 Merge two lists.
19 Merging One List with Another
20 Merging won"t work if the lists aren"t ordered.
21 Push value in the list
22 Sort a list.
23 Store class objects in a list.
24 Storing Class Objects in a List
25 The difference between push_back() and push_front().
26 Transform algorithm based on list.
27 Traverse a List Using an Iterator
28 Understanding end() in List
29 Use a binary function object in list "transform"
30 Use ostream_iterator for string
31 Using a list: push_back, begin, end, size
32 Using a list to store mailing addresses.
33 Using an arrays as a container
34 Using reverse() to create a palindrome tester.

A list splicing example.

#include <iostream>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
  list<string> sentence;
  list<string> phrase;
  list<string>::iterator p;
  
  string s1[] = {"A", "B", ""};
  string s2[] = {"C", "D", ""};
  string s3[] = {"E", "F", "G.", ""};
  string s4[] = {"A", "C,", "E", "G", ""};
  int i;
  for(i = 0; s1[ i ] != ""; i++)
    sentence.push_back(s1[i]);

  for(i = 0; s2[ i ] != ""; i++)
    phrase.push_back(s2[ i ]);
  cout << "Original sentence:\n";
  p = sentence.begin();
  while(p != sentence.end())
    cout << *p++ << " ";
  cout << endl;
  sentence.splice(sentence.begin(), phrase);
  cout << "Sentence after splicing at the front:\n";
  p = sentence.begin();
  while(p != sentence.end())
    cout << *p++ << " ";
  cout << endl;
  for(i = 0; s3[ i ] != ""; i++)
    phrase.push_back(s3[ i ]);
  sentence.splice(sentence.end(), phrase);
  cout << "Sentence after splicing at the end:\n";
  p = sentence.begin();
  while(p != sentence.end())
    cout << *p++ << " ";
  cout << endl;
  for(i = 0; s4[ i ] != ""; i++)
    phrase.push_back(s4[ i ]);

  p = find(sentence.begin(), sentence.end(), "or");
  sentence.splice(p, phrase);
  cout << "Sentence after splicing in the middle:\n";
  p = sentence.begin();
  while(p != sentence.end())
    cout << *p++ << " ";
  return 0;
}

An example of the transform algorithm.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int xform(int i) {
  return i * i;
}
int main()
{
  list<int> listObject;
  int i;
  for(i = 0; i <10; i++) 
     listObject.push_back(i);
  cout << "Original contents of listObject: ";
  list<int>::iterator p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl;
 
  p = transform(listObject.begin(), listObject.end(), listObject.begin(), xform);
  cout << "Transformed contents of listObject: ";
  p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Copy a list to a vector.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
  vector<char> v(20);
  list<char> listObject;
  int i;
  for(i = 0; i <20; i++) 
     v[i] = "A" + i;
  cout << "Original contents of vector:\n";
  for(i = 0; i <v.size(); i++) 
     cout << v[i] << " ";
  cout << "\n\n";
  char str[] = "-STL Power-";
  for(i = 0; str[i]; i++) 
     listObject.push_back(str[i]);
  copy(listObject.begin(), listObject.end(), v.begin());
  // display result
  cout << "Contents of vector after copy:\n";
  for(i = 0; i <v.size(); i++) 
     cout << v[i] << " ";
  return 0;
}

Create a reciprocal function object.

#include <iostream>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;
// A simple function object.
class reciprocal: unary_function<double, double> {
public:
  result_type operator()(argument_type i) { 
    return (result_type) 1.0/i; // return reciprocal
  }
};
int main()
{
  list<double> listObject;
  int i;
  for(i = 1; i <10; i++) 
     listObject.push_back((double)i);
  cout << "Original contents of listObject:\n";
  list<double>::iterator p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl;
 
  // use reciprocal function object
  // call function object
  p = transform(listObject.begin(), listObject.end(), listObject.begin(), reciprocal()); 
  cout << "Transformed contents of listObject:\n";
  p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Define class and store in a list

#include <iostream>
#include <list>
#include <cstring>
using namespace std;
class Project {
public:
  char name[40];
  int duration;
  Project() { 
    strcpy(name, "");
    duration = 0;
  }
  Project(char *n, int d) {
    strcpy(name, n);
    duration = d;
  }
  void add_days(int i) {
    duration += i;
  }
  void sub_days(int i) {
    duration -= i;
  }
  bool completed() { 
     return !duration; 
  }
 
  void report() {
    cout << name << ": ";
    cout << duration;
    cout << " days left.\n";
  }
};
bool operator<(const Project &a, const Project &b)
{
  return a.duration < b.duration;
}
bool operator>(const Project &a, const Project &b)
{
  return a.duration > b.duration;
}
bool operator==(const Project &a, const Project &b)
{
  return a.duration == b.duration;
}
bool operator!=(const Project &a, const Project &b)
{
  return a.duration != b.duration;
}
int main()
{
  list<Project> proj;
  proj.push_back(Project("Project 1", 35));
  proj.push_back(Project("Project 2", 190));
  proj.push_back(Project("Project 3", 1000));
  list<Project>::iterator p = proj.begin();
  while(p != proj.end()) {
    p->report();
    p++;
  }
  p = proj.begin();
  p->add_days(10);
  do {
    p->sub_days(5);
    p->report();
  } while (!p->completed());
  return 0;
}

Demonstrate advance() and distance() in list

#include <iostream>
#include <list>
#include <iterator>
using namespace std;
int main()
{
  list<char> listObject;
  list<char>::iterator p;
  int i;
  for(i = 0; i <10; i++) 
     listObject.push_back("A"+i);
  p = listObject.begin(); 
  cout << "Character at p: " << *p << endl;
  // move two characters forward using advance()
  advance(p, 2);
  cout << "Character at p+2: " << *p << endl;
  cout << "Number of elements from listObject.begin() ";
  cout << "to listObject.end(): ";
  cout << distance(listObject.begin(), listObject.end());
  return 0;
}

Demonstrate bind2nd().

#include <iostream>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;
int main()
{
  list<int> listObject;
  list<int>::iterator p, endp;
  int i;
  for(i =1; i < 20; i++) 
     listObject.push_back(i);
  cout << "Original sequence:\n";
  p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl;
  endp = remove_if(listObject.begin(), listObject.end(), bind2nd(greater<int>(), 8));
  cout << "Resulting sequence:\n";
  p = listObject.begin();
  while(p != endp) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Demonstrate merge() in list

#include <iostream>
#include <list>
using namespace std;
 
int main()
{
  list<int> listObject1, listObject2;
  int i;
  for(i = 0; i <10; i+=2) 
    listObject1.push_back(i);
  for(i =1; i <11; i+=2) 
    listObject2.push_back(i);
  cout << "Original size of listObject1: ";
  cout << listObject1.size() << endl;
  cout << "Original contents of listObject1:\n";
  list<int>::iterator p = listObject1.begin();
  while(p != listObject1.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  cout << "Original size of listObject2: ";
  cout << listObject2.size() << endl;
  cout << "Original contents of listObject2:\n";
  p = listObject2.begin();
  while(p != listObject2.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  // merge the two lists
  listObject1.merge(listObject2);
  cout << "Size of listObject1 after merge: ";
  cout << listObject1.size() << endl;
  cout << "Merged contents of listObject1:\n";
  p = listObject1.begin();
  while(p != listObject1.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  cout << "listObject2 is now empty, its size is ";
  cout << listObject2.size() << endl;
  return 0;
}

Demonstrate remove() in list

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject;
  list<int>::iterator p;
  int i;
  for(i = 0; i < 20; i++) 
     listObject.push_back(i%3);
  cout << "Original list: ";
  for(p = listObject.begin(); p != listObject.end(); p++)
    cout << *p << " ";
  cout << endl;
  listObject.remove(1); // remove all 1"s
  cout << "Modified list: ";
  for(p = listObject.begin(); p != listObject.end(); p++)
    cout << *p << " ";
  cout << endl;
  return 0;
}

Demonstrate unique() in list

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject;
  list<int>::iterator p;
  for(int i = 0; i < 5; i++)
    for(int j = 0; j < 3; j++) 
       listObject.push_back(i);
  cout << "Orignal list: ";
  for(p = listObject.begin(); p != listObject.end(); p++)
    cout << *p << " ";
  cout << endl;
  listObject.unique(); // remove consecutive duplicates
  cout << "Modified list: ";
  for(p = listObject.begin(); p != listObject.end(); p++)
    cout << *p << " ";
  cout << endl;
  return 0;
}

Demonstrate virtual functons: list interface

#include <iostream>
#include <cstdlib>
#include <cctype>
using namespace std;
class list {
public:
  list *head;             // pointer to start of list
  list *tail;             // pointer to end of list 
  list *next;             // pointer to next item
  int num;                // value to be stored
  list() { 
     head = tail = next = NULL; 
  }
  virtual void store(int i) = 0;
  virtual int retrieve() = 0;
};
class queue : public list {
public:
  void store(int i);
  int retrieve();
};
void queue::store(int i)
{
  list *item;
  item = new queue;
  if(!item) {
    cout << "Allocation error.\n";
    exit(1);
  }
  item->num = i;
  if(tail) 
     tail->next = item;
  tail = item;
  item->next = NULL;
  if(!head) 
     head = tail;
}
int queue::retrieve()
{
  int i;
  list *p;
  if(!head) {
    cout << "List empty.\n";
    return 0;
  }
  // remove from start of list
  i = head->num;
  p = head;
  head = head->next;
  delete p;
  return i;
}
class stack : public list {
public:
  void store(int i);
  int retrieve();
};
void stack::store(int i)
{
  list *item;
  item = new stack;
  if(!item) {
    cout << "Allocation error.\n";
    exit(1);
  }
  item->num = i;
  if(head) 
     item->next = head;
  head = item;
  if(!tail) 
     tail = head;
}
int stack::retrieve()
{
  int i;
  list *p;
  if(!head) {
    cout << "List empty.\n";
    return 0;
  }
  // remove from start of list
  i = head->num;
  p = head;
  head = head->next;
  delete p;
  return i;
}
int main()
{
  list *p;
  // demonstrate queue
  queue queueObject;
  p = &queueObject; // point to queue
  p->store(1);
  p->store(2);
  p->store(3);
  cout << "Queue: ";
  cout << p->retrieve();
  cout << p->retrieve();
  cout << p->retrieve();
  cout << "\n";
  // demonstrate stack
  stack stackObject;
  p = &stackObject; // point to stack
  p->store(1);
  p->store(2);
  p->store(3);
  cout << "Stack: ";
  cout << p->retrieve();
  cout << p->retrieve();
  cout << p->retrieve();
  cout << "\n";
  return 0;
}

Difference between push_back() and push_front()

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject1, listObject2;
  int i;
  for(i=0; i<10; i++) listObject1.push_back(i);
  for(i=0; i<10; i++) listObject2.push_front(i);
  list<int>::iterator p;
  cout << "Contents of listObject1:\n";
  p = listObject1.begin(); 
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n\n";
  cout << "Contents of listObject2:\n";
  p = listObject2.begin(); 
  while(p != listObject2.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Elements can be put on the front or end of a list.

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<char> listObject;
  list<char> revlistObject;
  int i;
  for(i = 0; i <10; i++) 
     listObject.push_back("A"+i);
  cout << "Size of listObject = " << listObject.size() << endl;
  cout << "Original contents: ";
  list<char>::iterator p;
  
  
  while(!listObject.empty()) {
    p = listObject.begin();
    cout << *p;
    listObject.pop_front();
    revlistObject.push_front(*p);
  }
  cout << endl << endl;
  
  cout << "Size of revlistObject = ";
  cout << revlistObject.size() << endl;
  cout << "Reversed contents: ";
  p = revlistObject.begin();
  while(p != revlistObject.end()) {
    cout << *p;
    p++;
  }
    
  return 0;
}

end() in list.

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject; // an empty list
  int i;
  for(i = 0; i <10; i++) 
     listObject.push_back(i);
  cout << "List printed forwards:\n";
  list<int>::iterator p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n";
  cout << "List printed backwards:\n";
  p = listObject.end();
  while(p != listObject.begin()) {
    p--;
    cout << *p << " ";
  }
  return 0;
}

List basics: push, begin, end pop

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<char> listObject;
  int i;
  for(i = 0; i <10; i++) 
     listObject.push_back("A"+i);
  cout << "Size = " << listObject.size() << endl;
  list<char>::iterator p;
  cout << "Contents: ";
  while(!listObject.empty()) {
    p = listObject.begin();
    cout << *p;
    listObject.pop_front();
  }
  
  return 0;
}

Merge and splice lists.

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<char> listObject1, listObject2, listObject3;
  int i;
  for(i = 0; i <10; i+=2) 
     listObject1.push_back(i + "A");
  for(i =1; i <11; i+=2) 
     listObject2.push_back(i + "A");
  cout << "Contents of listObject1:\n";
  list<char>::iterator p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n\n";
  cout << "Contents of listObject2:\n";
  p = listObject2.begin();
  while(p != listObject2.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n\n";
  
  listObject1.merge(listObject2);               // now, merge the two lists
  if(listObject2.empty())
    cout << "listObject2 is now empty\n";
  cout << "Contents of listObject1 after merge:\n";
  p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n\n";
  char str[] = "-splicing-";
  for(i = 0; str[i]; i++) 
     listObject3.push_back(str[i]);
  cout << "Contents of listObject3:\n";
  p = listObject3.begin();
  while(p != listObject3.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n\n";
  
  p = listObject1.begin();
  while(p != listObject1.end()) {
    if(*p == "F") listObject1.splice(p, listObject3);
    p++;
  }
  cout << "Contents of listObject1 after splice:\n";
  p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Merge into descending order.

#include <iostream>
#include <list>
using namespace std;
 
int main()
{
  list<int> listObject1, listObject2;
  int i;
  for(i = 10; i >= 0; i -= 2) 
    listObject1.push_back(i);
  for(i = 11; i >= 1; i -= 2) 
    listObject2.push_back(i);
  cout << "Original contents of listObject1:\n";
  list<int>::iterator p = listObject1.begin();
  while(p != listObject1.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  cout << "Original contents of listObject2:\n";
  p = listObject2.begin();
  while(p != listObject2.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  // merge using greater than, not less than
  listObject1.merge(listObject2, greater<int>());
  cout << "Merged contents of listObject1:\n";
  p = listObject1.begin();
  while(p != listObject1.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  return 0;
}

Merge two lists.

 
#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject1, listObject2;
  int i;
  for(i = 0; i < 10; i += 2) 
     listObject1.push_back(i);
  for(i =1; i < 11; i+=2) 
     listObject2.push_back(i);
  cout << "Contents of listObject1:\n";
  list<int>::iterator p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl << endl;
  cout << "Contents of listObject2:\n";
  p = listObject2.begin();
  while(p != listObject2.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl << endl;
  
  listObject1.merge(listObject2);
  if(listObject2.empty())
    cout << "listObject2 is now empty\n";
  cout << "Contents of listObject1 after merge:\n";
  p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Merging One List with Another

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject1, listObject2;
  int i;
  for(i=0; i<10; i+=2) listObject1.push_back(i);
  for(i=1; i<11; i+=2) listObject2.push_back(i);
  cout << "Contents of listObject1:\n";
  list<int>::iterator p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl << endl;
  cout << "Contents of listObject2:\n";
  p = listObject2.begin();  while(p != listObject2.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl << endl;
  // now, merge the two lists
  listObject1.merge(listObject2);
  if(listObject2.empty())
    cout << "listObject2 is now empty\n";
  cout << "Contents of listObject1 after merge:\n";
  p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Merging won"t work if the lists aren"t ordered.

#include <iostream>
#include <list>
using namespace std;
 
int main()
{
  list<int> listObject1, listObject2;
  int i;
  listObject1.push_back(2);
  listObject1.push_back(0);
  listObject1.push_back(8);
  listObject1.push_back(4);
  listObject1.push_back(6);
  for(i =1; i <11; i+=2) 
    listObject2.push_back(i);
  cout << "Original contents of listObject1:\n";
  list<int>::iterator p = listObject1.begin();
  while(p != listObject1.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  cout << "Original contents of listObject2:\n";
  p = listObject2.begin();
  while(p != listObject2.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  // this merge will fail
  listObject1.merge(listObject2);
  cout << "Contents of listObject1 after failed merge:\n";
  p = listObject1.begin();
  while(p != listObject1.end()) 
    cout << *p++ << " ";
  cout << "\n\n";
  return 0;
}

Push value in the list

#include <iostream>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;
int main()
{
  list<double> vals;
  int i;
  for(i =1; i <10; i++) 
     vals.push_back((double)i);
  cout << "Original contents of vals:\n";
  list<double>::iterator p = vals.begin();
  while(p != vals.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl;
 
  p = transform(vals.begin(), vals.end(), vals.begin(), negate<double>()); 
  cout << "Negated contents of vals:\n";
  p = vals.begin();
  while(p != vals.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Sort a list.

#include <iostream>
#include <list>
#include <cstdlib>
using namespace std;
int main()
{
  list<int> listObject;
  int i;
  for(i = 0; i < 10; i++)
    listObject.push_back(rand());
  cout << "Original contents:\n";
  list<int>::iterator p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl << endl;

  listObject.sort();
  
  cout << "Sorted contents:\n";
  p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  
  return 0;
}

Store class objects in a list.

#include <iostream>
#include <list>
#include <cstring>
using namespace std;
class myclass {
  int a, b;
  int sum;
public:
  myclass() { 
     a = b = 0; 
  }
  myclass(int i, int j) {
    a = i;
    b = j;
    sum = a + b;
  }
  int getsum() { 
     return sum; 
  }
  friend bool operator<(const myclass &object1, const myclass &object2);
  friend bool operator>(const myclass &object1, const myclass &object2);
  friend bool operator==(const myclass &object1, const myclass &object2);
  friend bool operator!=(const myclass &object1, const myclass &object2);
};
bool operator<(const myclass &object1, const myclass &object2)
{
  return object1.sum < object2.sum;
}
bool operator>(const myclass &object1, const myclass &object2)
{
  return object1.sum > object2.sum;
}
bool operator==(const myclass &object1, const myclass &object2)
{
  return object1.sum == object2.sum;
}
bool operator!=(const myclass &object1, const myclass &object2)
{
  return object1.sum != object2.sum;
}
int main()
{
  int i;
  list<myclass> listObject1;
  for(i = 0; i < 10; i++) 
     listObject1.push_back(myclass(i, i));
  cout << "First list: ";
  list<myclass>::iterator p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << p->getsum() << " ";
    p++;
  }
  cout << endl;
  list<myclass> listObject2;
  for(i = 0; i < 10; i++) 
     listObject2.push_back(myclass(i*2, i*3));
  cout << "Second list: ";
  p = listObject2.begin();
  while(p != listObject2.end()) {
    cout << p->getsum() << " ";
    p++;
  }
  cout << endl;
  
  listObject1.merge(listObject2);
  
  cout << "Merged list: ";
  p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << p->getsum() << " ";
    p++;
  }
  return 0;
}

Storing Class Objects in a List

#include <iostream>
#include <list>
#include <cstring>
using namespace std;
class myclass {
  int a, b;
  int sum;
public:
  myclass() { a = b = 0; }
  myclass(int i, int j) {
    a = i;
    b = j;
    sum = a + b;
  }
  int getsum() { return sum; }
  friend bool operator<(const myclass &object1,
                        const myclass &object2);
  friend bool operator>(const myclass &object1,
                        const myclass &object2);
  friend bool operator==(const myclass &object1,
                        const myclass &object2);
  friend bool operator!=(const myclass &object1,
                        const myclass &object2);
};
bool operator<(const myclass &object1, const myclass &object2)
{
  return object1.sum < object2.sum;
}
bool operator>(const myclass &object1, const myclass &object2)
{
  return object1.sum > object2.sum;
}
bool operator==(const myclass &object1, const myclass &object2)
{
  return object1.sum == object2.sum;
}
bool operator!=(const myclass &object1, const myclass &object2)
{
  return object1.sum != object2.sum;
}
int main()
{
  int i;
  // create first list
  list<myclass> listObject1;
  for(i=0; i<10; i++) listObject1.push_back(myclass(i, i));
  cout << "First list: ";
  list<myclass>::iterator p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << p->getsum() << " ";
    p++;
  }
  cout << endl;
  // create a second list
  list<myclass> listObject2;
  for(i=0; i<10; i++) listObject2.push_back(myclass(i*2, i*3));
  cout << "Second list: ";
  p = listObject2.begin();
  while(p != listObject2.end()) {
    cout << p->getsum() << " ";
    p++;
  }
  cout << endl;
  // now, merget listObject1 and listObject2
  listObject1.merge(listObject2);
  // display merged list
  cout << "Merged list: ";
  p = listObject1.begin();
  while(p != listObject1.end()) {
    cout << p->getsum() << " ";
    p++;
  }
  return 0;
}

The difference between push_back() and push_front().

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject1, listObject2;
  int i;
  for(i = 0; i < 10; i++) 
     listObject1.push_back(i);
     
  for(i = 0; i < 10; i++) 
     listObject2.push_front(i);
  
  list<int>::iterator p;
  
  cout << "Contents of listObject1:\n";
  p = listObject1.begin();  
  while(p != listObject1.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n";
  cout << "Contents of listObject2:\n";
  p = listObject2.begin();  
  while(p != listObject2.end()) {
    cout << *p << " ";
    p++;
  }
    
  return 0;
}

Transform algorithm based on list.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
double reciprocal(double i) {
  return 1.0/i;
}
int main()
{
  list<double> listObject;
  int i;
  for(i =1; i < 10; i++) 
     listObject.push_back((double)i);
  cout << "Original contents of listObject:\n";
  list<double>::iterator p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl;
 
  // transform listObject
  p = transform(listObject.begin(), listObject.end(), listObject.begin(), reciprocal);
  cout << "Transformed contents of listObject:\n";
  p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Traverse a List Using an Iterator

      #include <iostream>
      #include <list>
      using namespace std;
 
      typedef list<int> IntegerList;
      int main()
      {
          IntegerList    intList;
          for (int i = 1; i <= 10; ++i)
             intList.push_back(i * 2);
          for (IntegerList::const_iterator ci = intList.begin(); ci != intList.end(); ++ci)
             cout << *ci << " ";
          return 0;
      }

Understanding end() in List

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject; // create an empty list
  int i;
  for(i=0; i<10; i++) listObject.push_back(i);
  cout << "List printed forwards:\n";
  list<int>::iterator p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n\n";
  cout << "List printed backwards:\n";
  p = listObject.end();
  while(p != listObject.begin()) {
    p--; // decrement pointer before using
    cout << *p << " ";
  }
  return 0;
}

Use a binary function object in list "transform"

#include <iostream>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;
int main()
{
  list<double> vals;
  list<double> divisors;
  int i;
  for(i =10; i <100; i+=10) 
     vals.push_back((double)i);
  for(i =1; i <10; i++) 
     divisors.push_back(3.0);
  cout << "Original contents of vals:\n";
  list<double>::iterator p = vals.begin();
  while(p != vals.end()) {
    cout << *p << " ";
    p++;
  }
  cout << endl;
 
  p = transform(vals.begin(), 
                vals.end(),
                divisors.begin(), 
                vals.begin(),
                divides<double>()); // use function object
  cout << "Divided contents of vals:\n";
  p = vals.begin();
  while(p != vals.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Use ostream_iterator for string

#include <iostream>
#include <list>
#include <iterator>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
  list<string> listObject;
  ostream_iterator<string> out_it(cout);
  listObject.push_back("Stream ");
  listObject.push_back("iterators ");
  listObject.push_back("are ");
  listObject.push_back("useful.");
  copy(listObject.begin(), listObject.end(), out_it);
  return 0;
}

Using a list: push_back, begin, end, size

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> listObject; 
  int i;
  for(i = 0; i <10; i++) 
     listObject.push_back(i);
  cout << "Size = " << listObject.size() << endl;
  cout << "Contents: ";
  list<int>::iterator p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  cout << "\n\n";
  p = listObject.begin();
  while(p != listObject.end()) {
    *p = *p + 100;
    p++;
  }
  cout << "Contents modified: ";
  p = listObject.begin();
  while(p != listObject.end()) {
    cout << *p << " ";
    p++;
  }
  return 0;
}

Using a list to store mailing addresses.

#include <iostream>
#include <list>
#include <string>
using namespace std;
class Address {
  string name;
  string street;
  string city;
  string state;
  string zip;
public:
  Address() {
    name = street = city = state = zip = "";
  }
  Address(string n, string s, string c, string st, string z) {
    name = n;
    street = s;
    city = c;
    state = st;
    zip = z;
  }
  string getname() { 
     return name; 
  }
  string getcity() { 
     return city; 
  }
  string getstreet() { 
     return street; 
  }
  string getstate() { 
     return state; 
  }
  string getzip() { 
     return zip; 
  }
};
// List sorted by name.
bool operator<(Address &a, Address &b)
{
  return a.getname() < b.getname();
}
// List searched by name.
bool operator==(Address &a, Address &b)
{
  return a.getname() == b.getname();
}

void display(list<Address> &listObject) {
  list<Address>::iterator p;
  for(p = listObject.begin(); p != listObject.end(); p++) {
    cout << p->getname() << ": ";
    cout << p->getstreet() << ", ";
    cout << p->getcity() << ", ";
    cout << p->getstate() << " ";
    cout << p->getzip() << endl;
  }
}
int main()
{
  list<Address> mlistObjectA, mlistObjectB;
  mlistObjectA.push_back(Address("J", "1102 St", "Mission", "TX", "78572")); 
  mlistObjectA.sort();
  mlistObjectB.sort();
  // merge mailings lists
  mlistObjectA.merge(mlistObjectB);
  cout << "List A after sorting and merging.\n";
  display(mlistObjectA);
  cout << "List A now has " << mlistObjectA.size();
  cout << " entries.\n";
  // remove duplicates
  mlistObjectA.unique();
  cout << "List A after removing duplicates.\n";
  display(mlistObjectA);
  cout << "List A now has " << mlistObjectA.size();
  cout << " entries.\n";
  return 0;
}

Using an arrays as a container

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
  list<int> listObject(10);
  list<int>::iterator p;
  int *ip, *ip_end;
  int nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int i;
  cout << "Initial contents of nums: ";
  for(i = 0; i <10; i++) 
    cout << nums[ i ] << " ";
  cout << endl;

  copy(nums, &nums[9], listObject.begin());    // copy nums array to list
  cout << "Contents of listObject after copy: ";
  for(p=listObject.begin(); p!=listObject.end(); p++)
    cout << *p << " ";
  cout << endl;
  ip_end = remove_copy_if(listObject.begin(),   // remove elements that are less than 5
                          listObject.end(),
                          nums, 
                          bind2nd(less<int>(), 
                          5));
  cout << "Contents of nums after remove_copy_if(): ";
  for(ip=nums; ip!=ip_end; ip++)
    cout << *ip << " ";
  return 0;
}

Using reverse() to create a palindrome tester.

#include <iostream>
#include <list>
using namespace std;
char phrases[][80] = {
  "Madam, I"m Adam.",
  "Able was I ere I saw Elba.",
  "A man, a plan, a canal: Panama!",
  "This is not one.",
  ""
};
int main()
{
  list<char> pal;
  int i, j;
  list<char>::iterator p;
  for(i = 0; *phrases[ i ]; i++) {
    for(j = 0; phrases[ i ][ j ]; j++) 
      pal.push_back(phrases[ i ][ j ]);
    cout << "Phrase # " << i << " forward: ";
    p = pal.begin();
    while(p != pal.end()) cout << *p++;
    cout << endl;
    // remove extraneous characters
    pal.remove(",");
    pal.remove(".");
    pal.remove("!");
    pal.remove(":");
    pal.remove("\"");
    pal.remove(" ");
    cout << "Phrase # " << i << " after deletions: ";
    p = pal.begin();
    while(p != pal.end()) 
       cout << *p++;
    cout << endl;
    pal.reverse(); // reverse the list
    cout << "Phrase # " << i << " backward:        ";
    p = pal.begin();
    while(p != pal.end()) 
       cout << *p++;
    cout << endl;
    pal.clear(); // get ready to try next phrase
  }
  return 0;
}

Текущая версия на 10:24, 25 мая 2010 (просмотреть исходный код) Admin (обсуждение \| вклад) м (1 версия: Импорт контента...)	Текущая версия на 10:24, 25 мая 2010 (просмотреть исходный код) Admin (обсуждение \| вклад) м (1 версия: Импорт контента...)
(нет различий)

C++/Data Structure/List — различия между версиями

Текущая версия на 10:24, 25 мая 2010

Содержание

A list splicing example.

An example of the transform algorithm.

Copy a list to a vector.

Create a reciprocal function object.

Define class and store in a list

Demonstrate advance() and distance() in list

Demonstrate bind2nd().

Demonstrate merge() in list

Demonstrate remove() in list

Demonstrate unique() in list

Demonstrate virtual functons: list interface

Difference between push_back() and push_front()

Elements can be put on the front or end of a list.

end() in list.

List basics: push, begin, end pop

Merge and splice lists.

Merge into descending order.

Merge two lists.

Merging One List with Another

Merging won"t work if the lists aren"t ordered.

Push value in the list

Sort a list.

Store class objects in a list.

Storing Class Objects in a List

The difference between push_back() and push_front().

Transform algorithm based on list.

Traverse a List Using an Iterator

Understanding end() in List

Use a binary function object in list "transform"

Use ostream_iterator for string

Using a list: push_back, begin, end, size

Using a list to store mailing addresses.

Using an arrays as a container

Using reverse() to create a palindrome tester.

Навигация

Поиск