#include <iostream>
#include <string>
#include <list>
using namespace std;
// https://zh.cppreference.com/w/cpp/container/list
/*
* std::list 是支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。它通常实现为双向链表。
*
* 在 list 内或在数个 list 间添加、移除和移动元素不会非法化迭代器或引用。迭代器仅在对应元素被删除时非法化。
*
* T 必须满足可复制赋值 (CopyAssignable) 和可复制构造 (CopyConstructible) 的要求。
*/
std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
for (auto &i : list) {
ostr << " " << i;
}
return ostr;
}
class item
{
public:
item() = delete;
item(const int& a, const int& b)
: m_a(a), m_b(b)
{}
bool operator< (const item& comp) const
{
return m_a*m_b < comp.m_a*comp.m_b;
}
bool operator== (const item& comp) const
{
return m_a==comp.m_a && m_b==comp.m_b;
}
private:
int m_a;
int m_b;
};
int main()
{
int a[] = {1,2,3};
list<int> l;
list<int> l2({4,5,6});
list<int> l3(a, a+3);
//list<int> l4(l3); // deep copy
list<int> l5 = l3; // deep copy
list<int> l5_2 = { 1,2,3,4,5,6,7,8,9,0 };
//////////////////////////////////////////////////////////////////////////
l.push_back(1);
l.push_back(2);
l.push_front(-1);
l.push_front(-2); // -2, -1, 1, 2
l.pop_back(); // 去尾
l.pop_front(); // 去头
l.emplace_back(10); // 比 push_back 少执行一次 copy ctor / 拷贝构造。当元素为自定义的类时，效率差异明显。
l.emplace_front(-10);
l.emplace(l.begin(), 5); // 比 insert 少执行一次 copy ctor / 拷贝构造。当元素为自定义的类时，效率差异明显。
//////////////////////////////////////////////////////////////////////////
// void assign(std::initializer_list<T> ilist);
l.assign({});
l.assign({11,12,13});
// void assign( size_type count, const T& value );
l.assign(5, 14); // 5个14
// template< class InputIt >
// void assign(InputIt first, InputIt last);
l.assign(l3.begin(), l3.end());
//////////////////////////////////////////////////////////////////////////
// begin end
for (auto it = l5.begin(); it != l5.end(); ++it)
{
cout << *it;
}
cout << endl; // 123
// cbegin cend 常量，保证不改变 list 中的元素
for (auto it = l5.cbegin(); it != l5.cend(); ++it)
{
cout << *it;
}
cout << endl; // 123
// rbegin rend 注意偏移是 ++ 操作
for (auto it = l5.rbegin(); it != l5.rend(); ++it)
{
cout << *it;
}
cout << endl; // 321
//////////////////////////////////////////////////////////////////////////
// iterator erase (const_iterator position);
l5.erase(l5.begin()); // delete 1; size = 2
// iterator erase (const_iterator first, const_iterator last);
l5.erase(l5.begin(), l5.end()); // delete all
list<int> l5_3({ 1,2,3,4,5,6,7,8,9,0 });
auto it = l5_3.begin();
it++; // 不支持 + ，没有 + 重载。但是可以使用 std::advance 函数来完成固定步长的迭代器移动。
++it;
l5_3.erase(l5_3.begin(), it); // delete 1 and 2
list<int> l6({ 1,2,3,4,5,6,7,8,9,0 });
auto it6 = l6.begin();
std::advance(it6, 2); // 使用 std::advance 函数来完成固定步长的迭代器移动。
l6.erase(l6.begin(), it6); // delete 1 and 2
//////////////////////////////////////////////////////////////////////////
// max_size; Returns the maximum number of elements that the vector can hold.
// 系统或者库的设计上线。并非机器所能申请的最大大小。
size_t maxSize = l5.max_size();
bool isEmpty = l5.empty();
size_t listSize = l5.size();
//////////////////////////////////////////////////////////////////////////
l5.clear();
l5.swap(l); // 两者交换
///l5.swap(std::list<int>()); // 2015支持，2017不支持
//////////////////////////////////////////////////////////////////////////
list<int> l7({ 1,2,3,4,5,6,7,8,9,0 });
// iterator insert( iterator pos, const T& value );
l7.insert(l7.begin(), 101); // 101,1,2,3,4,5,6,7,8,9,0
// void insert( iterator pos, size_type count, const T& value );
l7.insert(l7.begin(), 2, 102); // 102,102,101,1,2,3,4,5,6,7,8,9,0
// template< class InputIt >
// void insert(iterator pos, InputIt first, InputIt last);
list<int> l8({ 11,21,31,41,51,61,71,81 });
l7.insert(l7.end(), l8.begin(), l8.end()); // 102,102,101,1,2,3,4,5,6,7,8,9,0,11,21,31,41,51,61,71,81
// iterator insert( const_iterator pos, std::initializer_list<T> ilist );
l7 = { 1,2,3,4,5,6,7,8,9,0 };
l7.insert(l7.end(), { 11,21,31 }); // 1,2,3,4,5,6,7,8,9,0,11,21,31
///l7.insert(l7.end(), l8); // 非法。此第二形参好像仅支持 {} 。
///l7.insert(l7.end(), std::list<int>(l8)); // 非法。此第二形参好像仅支持 {} 。
///l7.insert(l7.end(), std::list<int>(a, a+3)); // 非法。此第二形参好像仅支持 {} 。
//////////////////////////////////////////////////////////////////////////
//void resize( size_type count );
l7.resize(2); // 1,2
//void resize( size_type count, T value = T() );
//void resize( size_type count, const value_type& value );
l7.resize(4, 5); // 1,2,5,5
//////////////////////////////////////////////////////////////////////////
// 不复制或移动元素，仅重指向链表结点的内部指针。
// 归并二个已排序链表为一个。链表应以升序排序
// void merge( list& other );
std::list<int> list1 = { 5,9,0,1,3 };
std::list<int> list2 = { 8,7,2,6,4 };
list1.sort(); // 默认升序
list2.sort();
std::cout << "list1: " << list1 << "
";
std::cout << "list2: " << list2 << "
";
list1.merge(list2); // 归并二个已排序链表为一个。链表应以升序排序。list2 会变成空！！！
std::cout << "merged: " << list1 << "
";
// template <class Compare>
// void merge(list& other, Compare comp);
std::list<item> list1_item = { {1,1}, {7,7}, {2,2}, {0,0} };
std::list<item> list2_item = { {2,2}, {4,4}, {3,3} };
list1_item.sort(); // 默认升序，operator < 已经在 class item 中定义。
list2_item.sort();
list1_item.merge(list2_item, [&](item A, item B) { return A < B; }); // list2_item 会变成空！！！没有拷贝操作。
//////////////////////////////////////////////////////////////////////////
// 和 insert 相比，没有赋值操作。
std::list<int> l9 = { 1, 2, 3, 4, 5 };
std::list<int> ltt = { 10, 20, 30, 40, 50 };
auto it9 = l9.begin();
std::advance(it9, 2);
// void splice( const_iterator pos, list&& other );
l9.splice(it9, ltt); // 1, 2, 10, 20, 30, 40, 50, 3, 4, 5；执行结果与 insert 相同。ltt 变为空。insert 时 ltt不会清空。
l9 = { 1, 2, 3, 4, 5 };
it9 = l9.begin();
ltt = { 10, 20, 30, 40, 50 };
// void splice( const_iterator pos, list& other, const_iterator it );
auto it_ltt = ltt.begin();
std::advance(it_ltt, 2);
l9.splice(it9, ltt, it_ltt); // 30, 1, 2, 3, 4, 5 // ltt 若为空，出错。// 只移动一个。
l9 = { 1, 2, 3, 4, 5 };
it9 = l9.begin();
ltt = { 10, 20, 30, 40, 50 };
// void splice( const_iterator pos, list& other, const_iterator first, const_iterator last);
l9.splice(it9, ltt, ltt.begin(), ltt.end()); // 1, 2, 100, 200, 10, 20, 30, 40, 50, 3, 4, 5 // 移动一段。
//////////////////////////////////////////////////////////////////////////
l9.reverse(); // 反转
std::list<int> l10 = { 1,100,2,3,10,1,11,-1,12 };
l10.remove(1); // 移除两个等于 1 的元素
l10.remove_if([](int n) { return n > 10; }); // 移除全部大于 10 的元素
//////////////////////////////////////////////////////////////////////////
// 从容器移除所有 相邻 的重复元素。只留下相等元素组中的第一个元素。
std::list<int> l11 = { 1, 2, 2, 3, 3, 2, 1, 1, 2 };
// void unique();
l11.unique(); // 1 2 3 2 1 2
std::list<item> l12 = { {1,1}, {7,7}, {7,7}, {2,2}, {0,0}, {2,2} };
l12.unique(); // item 必须要重载 == // {1,1}, {7,7}, {2,2}, {0,0}, {2,2} // 自定义比较方法
// template< class BinaryPredicate >
// void unique(BinaryPredicate p); // 自定义比较方法
l11 = { 1, 3, 3, 1, 2, 2, 1, 2, 2, 15 };
l11.unique([](int a, int b) { return abs(b-a)<=1; }); // 1 3 1 15 // 自定义相等的条件。
//////////////////////////////////////////////////////////////////////////
l11.sort(); // 1 1 3 15 // 默认升序
l12.sort(); // 默认升序，operator < 已经在 class item 中定义。
l11.sort(std::greater<int>()); // 降序
}
* std::list 是支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。它通常实现为双向链表。与 std::forward_list 相比，此容器提供双向迭代但在空间上效率稍低。