前向列表是序列容器,允许在序列中的任何位置进行恒定时间的插入和擦除操作。
前向列表被实现为单链表;单链表可以将它们所包含的每个元素存储在不同且不相关的存储位置。通过与序列中下一个元素的链接的每个元素的关联来保持排序。
forward_list容器和list容器之间的主要设计区别在于,前者在内部只保留一个到下一个元素的链接,而后者为每个元素保留两个链接:一个指向下一个元件,一个指向前一个元件。这允许在两个方向上进行高效迭代,但每个元件消耗额外的存储空间,插入和删除元件的时间开销略高。因此,forward_list对象比list对象更有效率,尽管它们只能向前迭代。
与其他基本标准序列容器(array、vector和deque)相比,forward_list在插入、提取和移动容器内任何位置的元素方面通常表现得更好,因此在密集使用这些元素的算法(如排序算法)中也表现得更好。
与这些其他序列容器相比,forward_list和list的主要缺点是它们缺乏通过位置对元素的直接访问;例如,要访问forward_list中的第六个元素,必须从开始迭代到该位置,这需要在这些元素之间的距离上花费线性时间。它们还消耗一些额外的内存来保持与每个元素相关联的链接信息(这可能是小型元素的大列表的重要因素)。
forward_list类模板的设计考虑到了效率:在设计中,它的效率与简单的手写C风格单链表一样高,事实上,它是唯一一个出于效率考虑故意缺少大小成员函数的标准容器:由于其作为链表的性质,拥有一个需要恒定时间的大小成员需要为其大小保留一个内部计数器(就像列表一样)。这将消耗一些额外的存储空间,并使插入和删除操作的效率略低。要获得forward_list对象的大小,可以使用距离算法及其开始和结束,这是一种需要线性时间的操作。
其类图如下:
void ForwardListSuite::push_front()
{
std::forward_list<std::string> names;
std::string name("james");
names.push_front(name);
TEST_ASSERT_EQUALS("james", names.front())
names.push_front(std::string("tom"));
TEST_ASSERT_EQUALS("tom", names.front())
}
void ForwardListSuite::pop_front()
{
std::forward_list<int> a = { 1, 2, 3, 4, 5 };
TEST_ASSERT_EQUALS(1, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(2, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(3, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(4, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(5, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(true, a.empty())
}
void ForwardListSuite::construct()
{
std::forward_list<int> a;
std::forward_list<int> b(5, 100);
std::forward_list<int> c(b.begin(), b.end());
std::forward_list<int> d(c);
std::forward_list<int> e(std::move(d));
std::forward_list<int> f = { 1, 2, 3, 4, 5 , 6 };
TEST_ASSERT_EQUALS(true, a.empty())
TEST_ASSERT_EQUALS(false, b.empty())
TEST_ASSERT_EQUALS(false, c.empty())
TEST_ASSERT_EQUALS(true, d.empty())
TEST_ASSERT_EQUALS(false, e.empty())
TEST_ASSERT_EQUALS(false, f.empty())
}
void ForwardListSuite::assigns()
{
std::forward_list<int> a;
std::forward_list<int> b;
std::forward_list<int> c;
a = { 1, 2, 3, 4, 5 };
b = a;
c = std::move(b);
TEST_ASSERT_EQUALS(false, a.empty())
TEST_ASSERT_EQUALS(true, b.empty())
TEST_ASSERT_EQUALS(false, c.empty())
}
#define ARRAY_SIZE(array) sizeof(array) / sizeof(array[0])
void ForwardListSuite::iterators()
{
int array[] = { 1, 2, 3, 4, 5 };
std::forward_list<int> a(array, array + ARRAY_SIZE(array));
int index = 0;
for(auto it = a.begin(); it != a.end(); ++it)
{
TEST_ASSERT_EQUALS(array[index++], *it)
}
index = 0;
for(auto it = a.cbegin(); it != a.cend(); ++it)
{
TEST_ASSERT_EQUALS(array[index++], *it)
}
}
说明:
void ForwardListSuite::capacity()
{
std::forward_list<int> a;
std::forward_list<int> b = { 1, 2, 3, 4, 5 };
TEST_ASSERT_EQUALS(true, a.empty())
TEST_ASSERT_EQUALS(false, b.empty())
TEST_ASSERT_EQUALS(a.max_size(), b.max_size())
}
说明:
void ForwardListSuite::access()
{
std::forward_list<int> a = { 1, 2, 3, 4, 5 };
TEST_ASSERT_EQUALS(1, a.front())//size of a must more than 0
}
void ForwardListSuite::assign()
{
std::forward_list<int> a;
std::forward_list<int> b;
std::forward_list<int> c;
a.assign({ 1, 2, 3, 4, 5 });
b.assign(a.begin(), a.end());
c.assign(4, 5);
TEST_ASSERT_EQUALS(1, a.front())
TEST_ASSERT_EQUALS(1, b.front())
TEST_ASSERT_EQUALS(5, c.front())
}
void ForwardListSuite::emplace_front()
{
std::forward_list<std::string> names;
names.emplace_front("james");
TEST_ASSERT_EQUALS("james", names.front())
names.emplace_front("tom");
TEST_ASSERT_EQUALS("tom", names.front())
}
void ForwardListSuite::push_front()
{
std::forward_list<std::string> names;
std::string name("james");
names.push_front(name);
TEST_ASSERT_EQUALS("james", names.front())
names.push_front(std::string("tom"));
TEST_ASSERT_EQUALS("tom", names.front())
}
void ForwardListSuite::pop_front()
{
std::forward_list<int> a = { 1, 2, 3, 4, 5 };
TEST_ASSERT_EQUALS(1, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(2, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(3, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(4, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(5, a.front())
a.pop_front();
TEST_ASSERT_EQUALS(true, a.empty())
}
void ForwardListSuite::emplace_after()
{
std::forward_list<std::string> names;
auto it = names.before_begin();
it = names.emplace_after(it, "james");
TEST_ASSERT_EQUALS("james", *it)
it = names.emplace_after(it, "jim");
TEST_ASSERT_EQUALS("jim", *it)
}
说明:
void ForwardListSuite::insert_after()
{
std::forward_list<std::string> names;
std::string name("James");
auto it = names.insert_after(names.before_begin(), name);//James
TEST_ASSERT_EQUALS(name, *it)
it = names.insert_after(it, 2, "Tom"); //James Tom Tom
TEST_ASSERT_EQUALS("Tom", *it)
it = names.insert_after(it, "Peter"); //James Tom Tom Peter
TEST_ASSERT_EQUALS("Peter", *it)
it = names.insert_after(it, {"Jim", "Rose", }); //James Tom Tom Peter Jim Rose
TEST_ASSERT_EQUALS("Rose", *it) //??
}
说明:
void ForwardListSuite::erase_after()
{
std::forward_list<int> a({1, 2, 3, 4, 5});
auto it = a.erase_after(a.begin());// 1 3 4 5
TEST_ASSERT_EQUALS(3, *it)
it = a.erase_after(it);// 1 3 5
TEST_ASSERT_EQUALS(5, *it)
}
void ForwardListSuite::swap()
{
std::forward_list<int> a({1, 2, 3, 4, 5});
std::forward_list<int> b;
TEST_ASSERT_EQUALS(false, a.empty())
TEST_ASSERT_EQUALS(true, b.empty())
a.swap(b);
TEST_ASSERT_EQUALS(true, a.empty())
TEST_ASSERT_EQUALS(false, b.empty())
}
void ForwardListSuite::resize()
{
std::forward_list<int> a;
a.resize(5, 10); //10 10 10 10 10
for(auto it = a.begin(); it != a.end(); ++it)
TEST_ASSERT_EQUALS(10, *it);
a.resize(8); //10 10 10 10 10 0 0 0
auto end = a.begin();
std::advance(end, 5);
for(auto it = a.begin(); it != end; ++it)
TEST_ASSERT_EQUALS(10, *it);
for(auto it = end; it != a.end(); ++it)
TEST_ASSERT_EQUALS(0, *it);
a.resize(10, 20); //10 10 10 10 10 0 0 0 20 20
auto begin = a.begin();
std::advance(begin, 10);
for(auto it = begin; it != a.end(); ++it)
TEST_ASSERT_EQUALS(20, *it);
}
void ForwardListSuite::clear()
{
std::forward_list<int> a({1, 2, 3, 4, 5});
TEST_ASSERT_EQUALS(false, a.empty())
a.clear();
TEST_ASSERT_EQUALS(true, a.empty())
}
void ForwardListSuite::splice_after()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::forward_list<int> a({1, 2, 3, 4, 5});
std::forward_list<int> b({6, 7, 8, 9, 10});
b.splice_after(b.before_begin(), a);//1 2 3 4 5 6 7 8 9 10
int index = 0;
for(auto i : b)
TEST_ASSERT_EQUALS(array[index++], i)
TEST_ASSERT_EQUALS(true, a.empty())
a.splice_after(a.before_begin(), b, b.begin());
TEST_ASSERT_EQUALS(2, a.front()) // 2
TEST_ASSERT_EQUALS(1, b.front()) // 1 3 4 5 6 7 8 9 10
auto it = b.begin();
std::advance(it, 3);
a.splice_after(a.begin(), b, it, b.end());// 2 6 7 8 9 10
int a_array[] = { 2, 6, 7, 8, 9, 10 };
int b_array[] = { 1, 3, 4, 5 };
index = 0;
for(auto i : a)
TEST_ASSERT_EQUALS(a_array[index++], i)
index = 0;
for(auto i : b)
TEST_ASSERT_EQUALS(b_array[index++], i)
}
说明:
void ForwardListSuite::remove()
{
std::forward_list<int> a({1, 2, 3, 3, 4, 5});
a.remove(3);
bool isFound = false;
for(auto i : a)
if(i == 3)
isFound = true;
TEST_ASSERT_EQUALS(false, isFound)
}
struct is_odd
{
bool operator()(const int& value) { return value % 2 == 1; }
};
void ForwardListSuite::remove_if()
{
std::forward_list<int> a({15, 36, 7, 17, 20, 39, 4, 1});
a.remove_if(is_odd());
bool isFound = false;
is_odd odd;
for(auto i : a)
if(odd(i)) isFound = true;
TEST_ASSERT_EQUALS(false, isFound)
}
void ForwardListSuite::unique()
{
std::forward_list<int> a({ 1, 2, 3, 3, 4, 3, 5, 6 , 6});
a.unique();//1 2 3 4 3 5 6
int count = 0;
for(auto i : a)
if(i == 3) count++;
TEST_ASSERT_EQUALS(2, count)
a.sort();
a.unique();//1 2 3 4 5 6
count = 0;
for(auto i : a)
if(i == 3) count++;
TEST_ASSERT_EQUALS(1, count)
std::forward_list<float > b{ 1.2, 1.5, 2.2, 2.3, 3.2, 3.3 };
b.unique([](const float& l, const float& r) { return int(l) == int(r); }); // 1.2 2.2 3.2
count = 0;
for(auto f : b)
if(f == 1.5 || f == 2.3 || f == 3.3 ) count++;
TEST_ASSERT_EQUALS(0, count)
}
说明:
void ForwardListSuite::merge()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int rarray[] = { 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
std::forward_list<int> a{ 1, 2, 3, 4, 5 };
std::forward_list<int> b{ 6, 7, 8, 9, 10 };
std::forward_list<int> c{ 11, 12, 13, 14, 15 };
a.sort();
b.sort();
a.merge(b);
int index = 0;
for(auto i : a)
TEST_ASSERT_EQUALS(array[index++], i)
TEST_ASSERT_EQUALS(false, a.empty())
TEST_ASSERT_EQUALS(true, b.empty())
a.sort(std::greater<int>());
c.sort(std::greater<int>());
a.merge(c, std::greater<int>());
TEST_ASSERT_EQUALS(true, c.empty())
index = 0;
for(auto i : a)
TEST_ASSERT_EQUALS(rarray[index++], i)
}
说明:
void ForwardListSuite::sort()
{
int array[] = { 1, 5, 6, 7, 8, 15, 32 };
int rarray[] = { 32, 15, 8, 7, 6, 5, 1 };
std::list<int> a{5, 1, 7, 8, 6, 15, 32};
a.sort();
int index = 0;
for(auto it = a.begin(); it != a.end(); ++it)
TEST_ASSERT_EQUALS(array[index++], *it)
a.sort([](int const&l, int const&r ){ return l > r; });
index = 0;
for(auto it = a.begin(); it != a.end(); ++it)
TEST_ASSERT_EQUALS(rarray[index++], *it)
}
说明:
void ForwardListSuite::reverse()
{
int array[] = { 1, 2, 3, 4, 5 };
std::forward_list<int> a = { 5, 4, 3, 2, 1};
a.reverse();
int index = 0;
for(auto it = a.begin(); it != a.end(); ++it)
TEST_ASSERT_EQUALS(array[index++], *it)
}
void ForwardListSuite::get_allocator()
{
std::forward_list<int> a;
auto allocator = a.get_allocator();
int* p = allocator.allocate(5);
allocator.deallocate(p, 5);
try
{
p = allocator.allocate(allocator.max_size() + 1);
}
catch(...)
{
p = nullptr;
}
TEST_ASSERT_EQUALS(true, p == nullptr)
}