[Mastering C++ Programming] - List

• List는 내부적으로 Double linked list 로 구현되어 있다.
• random value searching 은 O(N)의 시간이 걸린다.
• data insertion은 O(1)이다.
• 구성은 아래와 같다.

 

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

int main () {

  list<int> l;

  for (int count=0; count<5; ++count)
    l.push_back( (count+1) * 100 );

  auto pos = l.begin();

  cout << "\nPrint the list ..." << endl;
  while ( pos != l.end() )
    cout << *pos++ << "-->";
  cout << " X" << endl;

  return 0;
}

• STL은 이전 코드와 같이 같은 API를 제공한다.

 

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

int main () {

    list<int> l = { 100, 20, 80, 50, 60, 5 };

    auto pos = l.begin();
 
    cout << "\nPrint the list before sorting ..." << endl;
    copy ( l.begin(), l.end(), ostream_iterator<int>( cout, "-->" ));
    cout << "X" << endl;

    l.sort();

    cout << "\nPrint the list after sorting ..." << endl;
    copy ( l.begin(), l.end(), ostream_iterator<int>( cout, "-->" ));
    cout << "X" << endl; 

    return 0;
}

• generic API sort는 random access가 가능한 STL이 사용가능하다.
• list는 random access가 불가능하므로 내부적인 sort가 구현되어있다.
• sort는 O(Nlog2N) 이다.

 

• API는 아래와 같다.