Loading...
墨滴

lyf

2021/04/10  阅读:28  主题:雁栖湖

STL容器—list使用技巧

1. std::list

Lists are sequence containers that allow non-contiguous memory allocation. As compared to vector, list has slow traversal, but once a position has been found, insertion and deletion are quick. Normally, when we say a List, we talk about doubly linked list. For implementing a singly linked list, we use forward list.

std::list中元素的存储不是连续的(双向链表),因此和std::vector相比,无法通过O(1)的时间复杂度去访问元素,但是一旦某个元素找到后,添加和删除元素是非常快捷的,这也是链表的优点。

stl_list
stl_list

上图大致描述了,标准库中std::list在内存中的结构。

2. 时间复杂度

Header
#include <list>
Constructors
list<T> l; Make an empty list. O(1)
list<T> l(begin, end); Make a list and copy the values from begin to end. O(n)
Accessors
l.size(); Return current number of elements. O(1)
l.empty(); Return true if list is empty. O(1)
l.begin(); Return bidirectional iterator to start. O(1)
l.end(); Return bidirectional iterator to end. O(1)
l.front(); Return the first element. O(1)
l.back(); Return the last element. O(1)
Modifiers
l.push_front(value); Add value to front. O(1)
l.push_back(value); Add value to end. O(1)
l.emplace_back(args...) Add value to end. O(1)
l.insert(iterator, value); Insert value after position indexed by iterator. O(1)
l.pop_front(); Remove value from front. O(1)
l.pop_back(); Remove value from end. O(1)
l.erase(iterator); Erase value indexed by iterator. O(1)
l.erase(begin, end); Erase the elements from begin to end. O(1)
l.remove(value); Remove all occurrences of value. O(n)
l.remove_if(test); Remove all element that satisfy test. O(n)
l.reverse(); Reverse the list. O(n)
l.clear(); Clear the list O(n)
l.sort(); Sort the list. O(n log n)
l.sort(comparison); Sort with comparison function. O(n logn)
l.merge(l2); Merge sorted lists. O(n)

从上表可以看出,凡是涉及在list中查找的操作都比较耗时(O(n)),但是一旦找到iterator后的一些操作都是O(1)。

3. code

借用前面std::vector的测试代码,可以验证std::list内存分配,

#include <cstdlib>
#include <vector>
#include <chrono>
#include <iostream>
#include <list>

int main()
{
    auto roll = []() {
        return (std::rand() % 10) + 1;
    };
    //std::vector<int> container;
    std::list<int> container;

    container.push_back(roll());
    const int* pAddressOrignItemZero = &(*container.begin());
    std::chrono::duration<doubledurInsertTime(0);

    for (int i = 0; i < 5; i++)
    {
        const int* pAddressItemZero = &(*container.begin());
        std::cout << "contains " << container.size() << " elements, took " <<
            std::chrono::duration_cast<std::chrono::microseconds>(durInsertTime).count() << " us" << std::endl;
        for (const auto& i : container) {
            const int* pAddressItemX = &i;
            int pItemOffset = pAddressItemX - pAddressItemZero;
            int pItemOffsetOrigin = pAddressItemX - pAddressOrignItemZero;
            std::cout << "offset from origin: " << pItemOffsetOrigin << " offset from zero: " << pItemOffset
                << " Content: " << i << std::endl;
        }

        auto tm1 = std::chrono::high_resolution_clock::now();
        container.push_back(roll());
        auto tm2 = std::chrono::high_resolution_clock::now();
        durInsertTime = tm2 - tm1;
    }

    return 0;
}

执行结果如下,可以看出来,std::list内存不连续,在添加元素的过程中不会像std::vector有内存重新分配拷贝的过程,执行时间都是类似的。

contains 1 elements, took 0 us
offset from origin: 0 offset from zero: 0 Content: 2
contains 2 elements, took 7 us
offset from origin: 0 offset from zero: 0 Content: 2
offset from origin: 432 offset from zero: 432 Content: 8
contains 3 elements, took 6 us
offset from origin: 0 offset from zero: 0 Content: 2
offset from origin: 432 offset from zero: 432 Content: 8
offset from origin: -312 offset from zero: -312 Content: 5
contains 4 elements, took 6 us
offset from origin: 0 offset from zero: 0 Content: 2
offset from origin: 432 offset from zero: 432 Content: 8
offset from origin: -312 offset from zero: -312 Content: 5
offset from origin: 408 offset from zero: 408 Content: 1
contains 5 elements, took 6 us
offset from origin: 0 offset from zero: 0 Content: 2
offset from origin: 432 offset from zero: 432 Content: 8
offset from origin: -312 offset from zero: -312 Content: 5
offset from origin: 408 offset from zero: 408 Content: 1
offset from origin: 24 offset from zero: 24 Content: 10

4. list的清理

调用std::listclear或者erase接口,c++标准不保证立即进行内存的释放。目前在STL中,只有含 reserve()/capacity() 成员函数的容器才可以用类似std::vector中的swap函数来立即释放空间,但是只有std::vectorstd::string支持。

下面的代码来自[chrome] Contents of /trunk/src/base/stl_util.h (chromium.org),用于对STL容器内部的存储进行清理,可以看到只包含了vectorstring的头文件。

// Copyright (c) 2011 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Derived from google3/util/gtl/stl_util.h6 
#ifndef BASE_STL_UTIL_H_
#define BASE_STL_UTIL_H_

#include <algorithm>
#include <functional>
#include <iterator>
#include <string>
#include <vector>

#include "base/logging.h"

// Clears internal memory of an STL object.
// STL clear()/reserve(0) does not always free internal memory allocated
// This function uses swap/destructor to ensure the internal memory is freed.
template<class T>
void STLClearObject(T* obj) {
T tmp;
tmp.swap(*obj);
// Sometimes "T tmp" allocates objects with memory (arena implementation?).
// Hence using additional reserve(0) even if it doesn't always work.
obj->reserve(0);
}

5. 哪里可以用std::list

通过上面的分析,在考虑效率的前提下,std::list基本可以抛弃不用了。但是它真的一无是处吗?下面是列举的一些可能有用的场所:

  1. 维护老旧代码。你已经有了很多std::list,想把他们连接或者分开,这时候再使用std::list将他们连接或者分开;
  2. 如果你频繁的要在一个容器A中查找某个元素,并把它删除,这时候用std::list是比较合适的(因为每次都必须得迭代整个容器)。

lyf

2021/04/10  阅读:28  主题:雁栖湖

作者介绍

lyf

自动驾驶系统、算法