Home | Projects | Notes > C++ Programming > Sequence Container - std::list, std::forward_list

Sequence Container - std::list, std::forward_list

The STL Lists

• Sequence containers.

• Non-contiguous in memory.

• No direct access to elements using [] or at().

• Very efficient for inserting and deleting elements once an element is found.

std::list

• Declared in the <list> header file.

• Dynamic size

  • Doubly-linked lists of elements.

  • Supports bi-directional traverse.

• Direct element access is NOT provided.

• Rapid insertion and deletion of elements anywhere in the container - Constant time: O(1)

  • If you need a container where you'll have lots of insertions and deletions from the container and you don't need direct access to the elements, then the list is a good choice.

• All iterators are available but may become invalid when the corresponding element is deleted.

Initialization and Assignment

x
1
// Initialization
2
std::list<int> l1{1, 2, 3, 4, 5};
3
std::list<int> l2(10, 100); // ten 100s - overloaded constructor
4

5
// Initialization
6
std::list<std::string> l3{
7
    std::string{"Kyungjae"},
8
    "Sunny",    // C-style string will be converted to a std::string.
9
    std::string{"Yena"}
10
};
11

12
// Assignment via initializer list
13
l1 = {2, 4, 6, 8, 10};

Common Methods

For more information, see cppreference.com.

34
1
std::list<int> l1{1, 2, 3, 4, 5};
2
std::list<int> l2{10, 20, 30, 40, 50};
3

4
std::cout << l1.size();     // 5
5
std::cout << l1.max_size(); // A very large number
6
std::cout << l1.front();    // 1 (Returns reference to the first element)
7
std::cout << l1.back();     // 5 (Returns reference to the last element)
8
std::cout << l1.empty();    // 0 (false)
9

10
// The following won't work since std::sort() requires random access
11
// iterators, and std::list provides only bidirectional iterators.
12
//std::sort(l1.begin(), l1.end());
13

14
l1.sort();
15

16
auto it = std::find(l1.begin(), l1.end(), 3);
17
l1.insert(it, 10);  // 1, 2, 10, 3, 4, 5
18
l1.erase(it);       // erase 3. now 1, 2, 10, 4, 5 ('it' becomes invalid)       
19

20
it = std::find(l1.begin(), l1.end(), 4);
21
l1.insert(it, l2.begin(), l2.end());
22
    // 1, 2, 10, 10, 20, 30, 40, 50, 4, 5
23

24
// Lists are bi-directional, so iterators can iterate in both directions.
25
std::cout << *it;   // 4
26
it++;
27
std::cout << *it;   // 5
28
it--;
29
std::cout << *it;   // 4
30

31
l1.resize(2);       // 1, 2
32
l1.resize(5);       // 1, 2, 0, 0, 0
33

34
l1.swap(l2);                // Swaps the two deques

L17: The list will insert an element very efficiently before 3 and the it will still reference 3.

The std::list allows for efficiently inserting and deleting elements at the front and back:

9
1
person p{"Kyungjae", 30};
2
std::list<person> d;
3

4
l.push_back(p);                 // Add p to the back (copy is made)
5
l.pop_back();                   // Remove the last element (p in this case)
6
l.push_front(person{"Sunny", 20});
7
l.pop_front();                  // Remove element from the front
8
l.emplace_front("Yena", 5);     // Construct the object in-place. Very efficient!
9
l.emplace_back("Sunny", 20);    // Construct the object in-place. Very efficient!

std::forward_list (C++11)

• Declared in the <forward_list> header file. Introduced in C++11.

• Dynamic size

  • Singly-linked lists of elements.

  • Supports uni-directional traverse only. (Does not have the concept of "back".)

  • Less overhead than a std::list.

• Direct element access is NOT provided.

• Rapid insertion and deletion of elements anywhere in the container - Constant time: O(1)

  • If you need a container where you'll have lots of insertions and deletions from the container and you don't need direct access to the elements, then the list is a good choice.

• Reverse iterators are not available.

• Iterators may become invalid when the corresponding element is deleted.

Initialization and Assignment

13
1
// Initialization
2
std::deque<int> d1{1, 2, 3, 4, 5};
3
std::deque<int> d2(10, 100);    // ten 100s
4

5
// Initialization
6
std::deque<std::string> d3{
7
    std::string{"Kyungjae"},
8
    "Sunny",    // C-style string will be converted to a std::string.
9
    std::string{"Yena"}
10
};
11

12
// Assignment via initializer list
13
d1 = {2, 4, 6, 8, 10};

Common Methods

For more information, see cppreference.com.

34
1
std::list<int> l1{1, 2, 3, 4, 5};
2
std::list<int> l2{10, 20, 30, 40, 50};
3

4
//std::cout << l1.size();       // size() not supported
5
std::cout << l1.max_size(); // A very large number
6
std::cout << l1.front();    // 1 (Returns reference to the first element)
7
//std::cout << l1.back();       // back() not supported
8
std::cout << l1.empty();    // 0 (false)
9

10
// The following won't work since std::sort() requires random access
11
// iterators, and std::list provides only bidirectional iterators.
12
//std::sort(l1.begin(), l1.end());
13

14
l1.sort();
15

16
auto it = std::find(l1.begin(), l1.end(), 3);
17
l1.insert(it, 10);  // 1, 2, 10, 3, 4, 5
18
l1.erase(it);       // erase 3. now 1, 2, 10, 4, 5 ('it' becomes invalid)       
19

20
it = std::find(l1.begin(), l1.end(), 4);
21
l1.insert_after(it, 10);    // 1, 2, 3, 10, 4, 10, 5
22
l1.emplace_after(it, 100);  // 1, 2, 3, 10, 4, 100, 10, 5
23
l1.erase_after(it);         // Erase the 100. 1, 2, 3, 10, 4, 10, 5
24

25
// Lists are bi-directional, so iterators can iterate in both directions.
26
std::cout << *it;   // 4
27
it++;
28
std::cout << *it;   // 5
29
//it--;             // Not supported
30

31
l1.resize(2);       // 1, 2
32
l1.resize(5);       // 1, 2, 0, 0, 0
33

34
l1.swap(l2);                // Swaps the two deques

max_size(): Returns the maximum number of elements a vector can theoretically hold on the current

system. This is typically a very large number and depends on system and implementation limits.

9
1
person p{"Kyungjae", 30};
2
std::deque<person> d;
3

4
//d.push_back(p);                   // Not supported
5
//d.pop_back();                     // Not supported
6
d.push_front(person{"Sunny", 20});
7
d.pop_front();                  // Remove element from the front
8
d.emplace_front("Yena", 5);     // Construct the object in-place. Very efficient!
9
//d.emplace_back("Sunny", 20);      // Not supported

L6: Creates a temporary (unnamed) person object and adds it to the forward list using move semantics.

L8: Constructs the person object directly in place using the constructor. Very efficient - no moves, no copies. It’s built exactly where it needs to be. Use this!

Project: Usage of std::list

Ensure that your custom classes provide the following three elements to work correctly with the STL:

• Overloaded default constructor

• Overloaded operator<

• Overloaded operator==

test3() in the following code demonstrates the importance of defining a default constructor for your custom class.

191
1
#include <iostream>
2
#include <list>
3
#include <algorithm>
4
#include <iterator> // std::advance()
5

6
class person
7
{
8
public:
9
    person() : name{"Unkown"}, age{0} {}    // will be useful when resizing happens
10
    person(std::string name, int age)
11
        : name{name}, age{age}
12
    {}
13
    bool operator<(const person &rhs) const
14
    {
15
        return this->age < rhs.age;
16
    }
17
    bool operator==(const person &rhs) const 
18
    {
19
        return (this->name == rhs.name && this->age == rhs.age);
20
    }
21
    
22
private:
23
    friend std::ostream& operator<<(std::ostream &os, const person &p);
24
    std::string name;
25
    int age;
26
};
27

28
// Overloading the insertion operator as a global function.
29
std::ostream& operator<<(std::ostream &os, const person &p)
30
{
31
    os << p.name << ":" << p.age;
32
    return os;
33
}
34

35
// Template function to print elements of any list.
36
template <typename T>
37
void print(const std::list<T> &l)
38
{
39
    std::cout << "[ ";
40
    for (const auto &elem : l)
41
    {
42
        std::cout << elem << " ";
43
    }
44
    std::cout << "]" << std::endl;
45
}
46

47
// push_front(), push_back()
48
void test1(void)
49
{
50
    std::cout << "\nTEST1" << std::endl;
51

52
    std::list<int> l1{1, 2, 3, 4, 5};
53
    print(l1);
54

55
    // Very efficient when inserting at both ends.
56
    std::list<std::string> l2;
57
    l2.push_back("Back");
58
    l2.push_front("Front");
59
    print(l2);
60

61
    std::list<int> l3;
62
    l3 = {1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10};
63
    print(l3);
64

65
    std::list<int> l4(10, 100); // ten 100s in the list (using constructor)
66
    print(l4);
67
}
68

69
// size(), front(), back(), clear()
70
void test2(void)
71
{
72
    std::cout << "\nTEST2" << std::endl;
73

74
    std::list<int> l{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
75
    print(l);
76

77
    std::cout << "Size: " << l.size() << std::endl;
78

79
    std::cout << "Front: " << l.front() << std::endl;
80
    std::cout << "Back: " << l.back() << std::endl;
81

82
    l.clear();
83
    print(l);
84
    std::cout << "Size: " << l.size() << std::endl;
85
}
86

87
void test3(void)
88
{
89
    std::cout << "\nTEST3" << std::endl;
90

91
    std::list<int> l1{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
92
    print(l1);
93

94
    l1.resize(5);
95
    print(l1);
96

97
    l1.resize(10);  
98
    print(l1);
99

100
    // This shows why it is important to define a overloaded default constructor
101
    // when using a custom class with the STL. (as well as 'operator<' and 
102
    // 'operator==')
103
    std::list<person> l2;
104
    l2.resize(5);   // uses the person's overloaded default constructor
105
    print(l2);
106
}
107

108
void test4(void)
109
{
110
    std::cout << "\nTEST4" << std::endl;
111

112
    std::list<int> l1{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
113
    print(l1);
114
    auto it = std::find(l1.begin(), l1.end(), 5);
115
    if (it != l1.end())
116
    {
117
        l1.insert(it, 100); // insert a 100 before the iterator
118
    }
119
    print(l1);
120

121
    std::list<int> l2{1000, 2000, 3000};
122
    l2.insert(it, l2.begin(), l2.end());    // 'it' still referencing 5 in l1
123
    print(l1);  // 1 2 3 4 100 1000 2000 3000 5 6 7 8 9 10
124

125
    std::advance(it, -4);   // point to the 100
126
    std::cout << *it << std::endl;
127

128
    l1.erase(it);   // remove the 100 - iterator becomes invalid
129
                    // to use iterator again you need to reset it!
130
    print(l1);
131
}
132

133
// emplace(), emplace_back(), find()
134
void test5(void)
135
{
136
    std::cout << "\nTEST5" << std::endl;
137

138
    std::list<person> l{
139
        {"Kyungjae", 30},
140
        {"Sunny", 20},
141
        {"Yena", 5}
142
    };
143

144
    print(l);
145
    std::string name;
146
    int age{};
147
    std::cout << "\nEnter the name of the next person: ";
148
    getline(std::cin, name);
149
    std::cout << "Enter their age: ";
150
    std::cin >> age;
151

152
    // I'm not creating an object to add to the list. The list will create an
153
    // object for me based on the passed values.
154
    l.emplace_back(name, age);
155
    print(l);
156

157
    // Insert Nina before Yena
158
    auto it = std::find(l.begin(), l.end(), person{"Yena", 5});
159
    if (it != l.end())
160
    {
161
        l.emplace(it, "Nina", 1);
162
    }
163
    print(l);
164
}
165

166
// sort()
167
void test6(void)
168
{
169
    std::cout << "\nTEST6" << std::endl;
170

171
    std::list<person> l{
172
        {"Kyungjae", 30},
173
        {"Sunny", 20},
174
        {"Yena", 5}
175
    };
176

177
    print(l);
178
    l.sort();   // sort() will use the overloaded 'operator<' 
179
    print(l);
180
}
181

182
int main(int argc, char *argv[])
183
{
184
    test1();
185
    test2();
186
    test3();
187
    test4();
188
    test5();
189
    test6();
190
    return 0;
191
}

38
1
TEST1
2
[ 1 2 3 4 5 ]
3
[ Front Back ]
4
[ 1 2 3 4 5 5 6 7 8 9 10 ]
5
[ 100 100 100 100 100 100 100 100 100 100 ]
6

7
TEST2
8
[ 1 2 3 4 5 6 7 8 9 10 ]
9
Size: 10
10
Front: 1
11
Back: 10
12
[ ]
13
Size: 0
14

15
TEST3
16
[ 1 2 3 4 5 6 7 8 9 10 ]
17
[ 1 2 3 4 5 ]
18
[ 1 2 3 4 5 0 0 0 0 0 ]
19
[ Unkown:0 Unkown:0 Unkown:0 Unkown:0 Unkown:0 ]
20

21
TEST4
22
[ 1 2 3 4 5 6 7 8 9 10 ]
23
[ 1 2 3 4 100 5 6 7 8 9 10 ]
24
[ 1 2 3 4 100 1000 2000 3000 5 6 7 8 9 10 ]
25
100
26
[ 1 2 3 4 1000 2000 3000 5 6 7 8 9 10 ]
27

28
TEST5
29
[ Kyungjae:30 Sunny:20 Yena:5 ]
30

31
Enter the name of the next person: Miyoung
32
Enter their age: 50
33
[ Kyungjae:30 Sunny:20 Yena:5 Miyoung:50 ]
34
[ Kyungjae:30 Sunny:20 Nina:1 Yena:5 Miyoung:50 ]
35

36
TEST6
37
[ Kyungjae:30 Sunny:20 Yena:5 ]
38
[ Yena:5 Sunny:20 Kyungjae:30 ]