C/C++编程：双向链表list

清疚 2022-05-17 10:18 211阅读 0赞

# list #

*  list<>由双向链表实现而成。这意味着list内的每个元素都以一部分内存指示其前导元素和后继元素
 *  list<>不提供随机访问，因此如果你要访问第10个元素，必须沿着链表依次走过前9个元素
 *  list<>的优势是：在任何位置上执行安插或者删除动作都非常快速，因为只需要改变链接就好
 *  `std::list` 是支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。与 [std::forward\_list][std_forward_list] 相比，此容器提供双向迭代但在空间上效率稍低。
 *  在 list 内或在数个 list 间添加、移除和移动元素不会非法化迭代器或引用。迭代器仅在对应元素被删除时非法化。
 *  list<>析构时，**若元素是指针，则不销毁所指向的对象**

##  ##

## 构造 ##

#include <list>
    #include <string>
    #include <iostream>
    
    template<typename T>
    std::ostream& operator<<(std::ostream& s, const std::list<T>& v)
    {
        s.put('[');
        char comma[3] = {'\0', ' ', '\0'};
        for (const auto& e : v) {
            s << comma << e;
            comma[0] = ',';
        }
        return s << ']';
    }
    
    int main()
    {
        // C++11 初始化器列表语法：
        std::list<std::string> words1 {"the", "frogurt", "is", "also", "cured"};
        std::cout << "words1: " << words1 << '\n';
    
        // words2 == words1
        std::list<std::string> words2(words1.begin(), words1.end());
        std::cout << "words2: " << words2 << '\n';
    
        // words3 == words1
        std::list<std::string> words3(words1);
        std::cout << "words3: " << words3 << '\n';
    
        // words4 为 {"Mo", "Mo", "Mo", "Mo", "Mo"}
        std::list<std::string> words4(5, "Mo");
        std::cout << "words4: " << words4 << '\n';
        return 0;
    }

![20210228142836337.png][]

## std::list<T,Allocator>::operator=、std::list<T,Allocator>::assign ##

*  std::list<T,Allocator>::assign作用：替换容器的内容
 *  std::list<T,Allocator>::operator=作用：替换容器的内容

#include <list>
    #include <string>
    #include <iostream>
    
    void display_sizes(const std::list<int>& nums1,
                       const std::list<int>& nums2,
                       const std::list<int>& nums3)
    {
        std::cout << "nums1: " << nums1.size()
                  << " nums2: " << nums2.size()
                  << " nums3: " << nums3.size() << '\n';
    }
    
    int main()
    {
        std::list<int> nums1 {3, 1, 4, 6, 5, 9};
        std::list<int> nums2;
        std::list<int> nums3;
    
        std::cout << "Initially:\n";
        display_sizes(nums1, nums2, nums3);
    
        // 复制赋值从 nums1 复制数据到 nums2
        nums2 = nums1;
    
        std::cout << "After assigment:\n";
        display_sizes(nums1, nums2, nums3);
    
        // 移动赋值从 nums1 移动数据到 nums3,
        // 一同修改 nums1 和 nums3
        nums3 = std::move(nums1);
    
        std::cout << "After move assigment:\n";
        display_sizes(nums1, nums2, nums3);
    
    
    
        return 0;
    }

![20210228143357202.png][]

#include <list>
    #include <string>
    #include <iostream>
    
    
    
    int main()
    {
        std::list<char> characters;
    
        characters.assign(5, 'a');
    
        for (char c : characters) {
            std::cout << c << ' ';
        }
    
        characters.assign({'\n', 'C', '+', '+', '1', '1', '\n'});
    
        for (char c : characters) {
            std::cout << c;
        }
    
        return 0;
    }

![20210228143806664.png][]

## front、back ##

*  std::list<T,Allocator>::front：返回到容器首元素的引用。在空容器上调用 `front` 会引发未定义行为
 *  std::list<T,Allocator>::back：返回到容器中最后一个元素的引用。在空容器上调用 `back` 会引发未定义行为

#include <list>
    #include <iostream>
    
    int main()
    {
        std::list<char> letters {'o', 'm', 'g', 'w', 't', 'f'};
    
        if (!letters.empty()) {
            std::cout << "The first character is: " << letters.front() << '\n';
            std::cout << "The last character is: " << letters.back() << '\n';
        }
    }

![20210228144332140.png][]

## begin、end、rbegin、rend ##

*  begin：返回指向list首元素的迭代器
 *  end： 返回指向 `list` 末元素后一元素的迭代器。

#include <iostream>
    #include <numeric>
    #include <list>
    #include <string>
    
    int main()
    {
        std::list<int> nums {1, 2, 4, 8, 16};
        std::list<std::string> fruits {"orange", "apple", "raspberry"};
        std::list<char> empty;
    
        // 求和 list nums 中的所有整数（若存在），仅打印结果。
        std::cout << "Sum of nums: " <<
            std::accumulate(nums.begin(), nums.end(), 0)  << "\n";
    
        // 打印 list fruits 中的首个 fruis
        if(!fruits.empty()){
            std::cout << "First fruit: " << *fruits.begin() << "\n";
        }
    
        if (empty.begin() == empty.end())
            std::cout << "list 'empty' is indeed empty.\n";
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70][]

## empty、size、max\_size、resize ##

*  empty：检查容器是否为空
 *  size：返回容器中的元素数，相当于 **[std::distance][std_distance](begin(), end())**
 *  max\_size：返回最大可以容纳的元素个数
 *  resize：重设容器大小以容纳count个元素

#include <list>
    #include <iostream>
     
    int main()
    {
        std::list<int> numbers;
        std::cout << "Initially, numbers.empty(): " << numbers.empty() << '\n';
     
        numbers.push_back(42);
        numbers.push_back(13317); 
        std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n';
    }

![20210228145216985.png][]

#include <list>
    #include <iostream>
    #include <limits>
    
    int main()
    {
        std::list<int> numbers;
        std::cout << "max size: " << numbers.max_size() << '\n';
        std::cout << "max size: " << std::numeric_limits<std::list<int>>::max().max_size()<< '\n';
    }

![20210228145730922.png][]

#include <iostream>
    #include <list>
    int main()
    {
        std::list<int> c = {1, 2, 3};
        std::cout << "The list holds: ";
        for(auto& el: c) std::cout << el << ' ';
        std::cout << '\n';
        c.resize(5);
        std::cout << "After resize up to 5: ";
        for(auto& el: c) std::cout << el << ' ';
        std::cout << '\n';
        c.resize(2);
        std::cout << "After resize down to 2: ";
        for(auto& el: c) std::cout << el << ' ';
        std::cout << '\n';
    }

# ![2021022816092045.png][] #

## swap ##

#include <list>
    #include <iostream>
    
    template<class Os, class Co>
    Os& operator<<(Os& os, const Co& co) {
        os << "{";
        for (auto const& i : co) { os << ' ' << i; }
        return os << " } ";
    }
    
    int main()
    {
        std::list<int> a1{1, 2, 3}, a2{4, 5};
    
        auto it1 = std::next(a1.begin());
        auto it2 = std::next(a2.begin());
    
        int & ref1 = a1.front();
        int & ref2 = a2.front();
        
        std::cout << a1 << a2 << *it1 << ' ' << *it2 << ' ' << ref1 << ' ' << ref2 << '\n';
        a1.swap(a2);
        std::cout << a1 << a2 << *it1 << ' ' << *it2 << ' ' << ref1 << ' ' << ref2 << '\n';
    
        // 注意交换后迭代器与引用保持与其原来的元素关联，例如指向 'a1' 中值为 2 的元素的 it1 仍指向同一元素，
        // 尽管此元素被移动到 'a2' 中。
    }

效果

#include <algorithm>
    #include <iostream>
    #include <list>
     
    int main()
    {
        std::list<int> alice{1, 2, 3};
        std::list<int> bob{7, 8, 9, 10};
     
        auto print = [](const int& n) { std::cout << " " << n; };
     
        // 打印交换前的状态
        std::cout << "alice:";
        std::for_each(alice.begin(), alice.end(), print);
        std::cout << '\n';
        std::cout << "bob  :";
        std::for_each(bob.begin(), bob.end(), print);
        std::cout << '\n';
     
        std::cout << "-- SWAP\n";
        std::swap(alice,bob);
     
        // 打印交换后的状态
        std::cout << "alice:";
        std::for_each(alice.begin(), alice.end(), print);
        std::cout << '\n';
        std::cout << "bob  :";
        std::for_each(bob.begin(), bob.end(), print);
        std::cout << '\n';
    }

效果

![20210228170105529.png][]

## clear、erase ##

*  clear：从容器擦除所有元素。此调用后 [size()][size] 返回零。
 *  erase：从容器擦除指定的元素

>  *  1) 移除位于 `pos` 的元素。
>  *  2) 移除范围 `[first; last)` 中的元素。

#include <algorithm>
    #include <iostream>
    #include <list>
    
    int main()
    {
        std::list<int> container{1, 2, 3};
    
        auto print = [](const int& n) { std::cout << " " << n; };
    
        std::cout << "Before clear:";
        std::for_each(container.begin(), container.end(), print);
        std::cout << "\nSize=" << container.size() << '\n';
    
        std::cout << "Clear\n";
        container.clear();
    
        std::cout << "After clear:";
        std::for_each(container.begin(), container.end(), print);
        std::cout << "\nSize=" << container.size() << '\n';
    }

![20210228150311326.png][]

#include <list>
    #include <iostream>
    #include <iterator>
     
    int main( )
    {
        std::list<int> c{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        for (auto &i : c) {
            std::cout << i << " ";
        }
        std::cout << '\n';
     
        c.erase(c.begin());
     
        for (auto &i : c) {
            std::cout << i << " ";
        }
        std::cout << '\n';
     
        std::list<int>::iterator range_begin = c.begin();
        std::list<int>::iterator range_end = c.begin();
        std::advance(range_begin,2);
        std::advance(range_end,5);
     
        c.erase(range_begin, range_end);
     
        for (auto &i : c) {
            std::cout << i << " ";
        }
        std::cout << '\n';
    }

![20210228150704644.png][]

#include <iostream>
    #include <numeric>
    #include <list>
     
    void print_container(const std::list<char>& c)
    {
        for (auto x : c) {
            std::cout << x << ' ';
        }
        std::cout << '\n';
    }
     
    int main()
    {
        std::list<char> cnt(10);
        std::iota(cnt.begin(), cnt.end(), '0');
     
        std::cout << "Init:\n";
        print_container(cnt);
     
        auto erased = std::erase(cnt, '3');
        std::cout << "Erase \'3\':\n";
        print_container(cnt);
     
        std::erase_if(cnt, [](char x) { return (x - '0') % 2 == 0; });
        std::cout << "Erase all even numbers:\n";
        print_container(cnt);
        std::cout << "In all " << erased << " even numbers were erased.\n";
    }

## ![20210228170421346.png][] ##

## emplace、emplace\_front、push\_back ##

*  emplace：直接于pos前插入元素到容器中
 *  emplace\_front、push\_front：插入新元素到容器起始
 *  [emplace\_back][emplace_back]、push\_back：插入新元素到容器末尾
 *  pop\_back：移除容器的末元素。在空容器上调用 `pop_back` 导致未定义行为。指向被擦除元素的迭代器和引用被非法化。

#include <algorithm>
    #include <iostream>
    #include <list>
    
    struct A{
        std::string s;
        A(std::string str) : s(std::move(str))  { std::cout << " constructed\n"; }
        A(const A& o) : s(o.s) { std::cout << " copy constructed\n"; }
        A(A&& o) : s(std::move(o.s)) { std::cout << " move constructed\n"; }
        A& operator=(const A& other) {
            s = other.s;
            std::cout << " copy assigned\n";
            return *this;
        }
        A& operator=(A&& other) {
            s = std::move(other.s);
            std::cout << " move assigned\n";
            return *this;
        }
    };
    
    int main()
    {
        std::list<A> container;
    
        std::cout << "construct 2 times A:\n";
        A two { "two" };
        A three { "three" };
    
        std::cout << "emplace:\n";
        container.emplace(container.end(), "one");
    
        std::cout << "emplace with A&:\n";
        container.emplace(container.end(), two);
    
        std::cout << "emplace with A&&:\n";
        container.emplace(container.end(), std::move(three));
    
        std::cout << "content:\n";
        for (const auto& obj : container)
            std::cout << ' ' << obj.s;
        std::cout << '\n';
    }

![20210228151921373.png][]

#include <list>
    #include <iostream>
     
    template<class T>
    void print(T const & xs)
    {
        std::cout << "[ ";
        for(auto && x : xs) {
            std::cout << x << ' ';
        }
        std::cout << "]\n";
    }
     
    int main()
    {
        std::list<int> numbers;
     
        print(numbers); 
     
        numbers.push_back(5);
        numbers.push_back(3);
        numbers.push_back(4);
     
        print(numbers); 
     
        numbers.pop_back();
     
        print(numbers); 
    }

![20210228155028574.png][]

## merge ##

*  merge：归并两排序链表为一个

#include <iostream>
    #include <list>
     
    std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
    {
        for (auto &i : list) {
            ostr << " " << i;
        }
        return ostr;
    }
     
    int main()
    {
        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 << "\n";
        std::cout << "list2:  " << list2 << "\n";
        list1.merge(list2);
        std::cout << "merged: " << list1 << "\n";
    }

![2021022816393910.png][]

## splice ##

*  splice：从一个list转移元素给另一个。不复制或者移动元素，仅重指向链表节点的内部指针

#include <list>
    #include <iostream>
    
    std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
    {
        for (auto &i : list) {
            ostr << " " << i;
        }
        return ostr;
    }
    
    int main()
    {
        std::list<int> list1 = { 1, 2, 3, 4, 5 };
        std::list<int> list2 = { 10, 20, 30, 40, 50 };
    
        auto it = list1.begin();
        std::advance(it, 2);
    
        list1.splice(it, list2);
    
        std::cout << "list1: " << list1 << "\n";
        std::cout << "list2: " << list2 << "\n";
    
        list2.splice(list2.begin(), list1, it, list1.end());
    
        std::cout << "list1: " << list1 << "\n";
        std::cout << "list2: " << list2 << "\n";
    }

![20210228164406874.png][]

## remove, remove\_if ##

#include <list>
    #include <iostream>
     
    int main()
    {
        std::list<int> l = { 1,100,2,3,10,1,11,-1,12 };
     
        l.remove(1); // 移除两个等于 1 的元素
        l.remove_if([](int n){ return n > 10; }); // 移除全部大于 10 的元素
     
        for (int n : l) {
            std::cout << n << ' '; 
        }
        std::cout << '\n';
    }

## reverse ##

*  作用：逆转容器中的元素顺序。不非法化任何引用或迭代器。

#include <iostream>
    #include <list>
     
    std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
    {
        for (auto &i : list) {
            ostr << " " << i;
        }
        return ostr;
    }
     
    int main()
    {
        std::list<int> list = { 8,7,5,9,0,1,3,2,6,4 };
     
        std::cout << "before:     " << list << "\n";
        list.sort();
        std::cout << "ascending:  " << list << "\n";
        list.reverse();
        std::cout << "descending: " << list << "\n";
    }

![20210228165304779.png][]

## unique ##

*  从容器移除所有*相继*的重复元素。只留下相等元素组中的第一个元素。

#include <iostream>
    #include <list>
     
    int main()
    {
      std::list<int> x = {1, 2, 2, 3, 3, 2, 1, 1, 2};
     
      std::cout << "contents before:";
      for (auto val : x)
        std::cout << ' ' << val;
      std::cout << '\n';
     
      x.unique();
      std::cout << "contents after unique():";
      for (auto val : x)
        std::cout << ' ' << val;
      std::cout << '\n';
     
      return 0;
    }

![20210228165604669.png][]

## 比较 ##

#include <iostream>
    #include <list>
     
    int main()
    {
        std::list<int> alice{1, 2, 3};
        std::list<int> bob{7, 8, 9, 10};
        std::list<int> eve{1, 2, 3};
     
        std::cout << std::boolalpha;
     
        // 比较不相等的容器
        std::cout << "alice == bob returns " << (alice == bob) << '\n';
        std::cout << "alice != bob returns " << (alice != bob) << '\n';
        std::cout << "alice <  bob returns " << (alice < bob) << '\n';
        std::cout << "alice <= bob returns " << (alice <= bob) << '\n';
        std::cout << "alice >  bob returns " << (alice > bob) << '\n';
        std::cout << "alice >= bob returns " << (alice >= bob) << '\n';
     
        std::cout << '\n';
     
        // 比较相等的容器
        std::cout << "alice == eve returns " << (alice == eve) << '\n';
        std::cout << "alice != eve returns " << (alice != eve) << '\n';
        std::cout << "alice <  eve returns " << (alice < eve) << '\n';
        std::cout << "alice <= eve returns " << (alice <= eve) << '\n';
        std::cout << "alice >  eve returns " << (alice > eve) << '\n';
        std::cout << "alice >= eve returns " << (alice >= eve) << '\n';
    }

![20210228165747675.png][]

[std_forward_list]: https://zh.cppreference.com/w/cpp/container/forward_list
[20210228142836337.png]: /images/20220517/16175825a84942bab69371290cab1624.png
[20210228143357202.png]: /images/20220517/6ce31853bddf404fb07fc3c8a7c4a2cf.png
[20210228143806664.png]: /images/20220517/bb47afb4d3f840a8b69926ee1fae5a83.png
[20210228144332140.png]: /images/20220517/d283f974259b414c94ac78c2f7554dd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20220517/8933663e6d3f4ccda029245ff4d623e9.png
[std_distance]: http://zh.cppreference.com/w/cpp/iterator/distance
[20210228145216985.png]: /images/20220517/ca14573bee964957867f660059fc9159.png
[20210228145730922.png]: /images/20220517/492403e3b17842e7b3feb0d577176e73.png
[2021022816092045.png]: /images/20220517/d9adfde71ad54740accb1bfaa1b29025.png
[20210228170105529.png]: /images/20220517/4a0d5b84892649dd800b583579070666.png
[size]: https://zh.cppreference.com/w/cpp/container/list/size
[20210228150311326.png]: /images/20220517/d3708c7398b84a94aea40d9e1d65bc34.png
[20210228150704644.png]: /images/20220517/1627ede3a7ed4c8baa2db8181451ed5b.png
[20210228170421346.png]: /images/20220517/a352658297f24cb8b1523dc494e58446.png
[emplace_back]: https://zh.cppreference.com/w/cpp/container/list/emplace_back
[20210228151921373.png]: /images/20220517/a9448d7ba6a3430086b4881ae6a64f24.png
[20210228155028574.png]: /images/20220517/47290dd6ec364421a387c7b2f23ff4ab.png
[2021022816393910.png]: /images/20220517/3dc4a7de927447259b366ff6c708a430.png
[20210228164406874.png]: /images/20220517/feeb6d2f86554c9d99201741cdeb6df4.png
[20210228165304779.png]: /images/20220517/96552938ca81480c94a67ab61540bebc.png
[20210228165604669.png]: /images/20220517/bc07a28cf1d94d77b25cdb82923b3c11.png
[20210228165747675.png]: /images/20220517/4f4ad18d618e4e50ab708757ffb25dfd.png