序列式容器和关联式容器

在C++中容器被分为序列式容器和关联式容器两大类，它们的核心区别在于元素的组织方式和访问方式

特性	序列式容器	关联式容器
元素顺序	由插入顺序决定	由容器内部排列规则决定
访问方式	通过（索引/迭代器）访问	通过键（key）访问
是否有序	保持插入顺序	按键值自动排序（默认升序）
是否允许重复	允许	ser/multiset允许重复键值对
查找效率	O(N)线性查找	O(logN)红黑树实现
典型容器	vector、list、deque	set、map、multiset、multimap

序列式容器

• 元素按插入顺序排列。

• 支持随机访问（如 vector）或顺序访问（如 list）。

• 没有键值概念，元素就是值本身。

关联式容器

• 元素按键值自动排序（默认升序）。

• 查找、插入、删除效率为 O(log n)。

• 不允许重复键（set, map），或允许重复（multiset, multimap）。

set的使用

set的插入insert

#include<set>

int main()
{
	set<int> s;
	s.insert(9);
	s.insert(6);
	s.insert(5);
	s.insert(1);
	s.insert(7);

	/*set<int>::iterator it1 = s.begin();

	while (it1 != s.end())
	{
		cout << *it1 <<" ";
		++it1;
	}*/

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

• 返回 pair<iterator,bool>

  • second == true 表示确实发生了插入；

  • first 始终指向拥有等价键（即 value_type）的那个元素。

• 返回 iterator

  • 如果插入成功，指向新元素；

  • 如果等价键已存在，指向已存在的那个元素。
    注意：不会告诉你“到底有没有插入”，需要后续手动比较 size 或 count。

• 无返回值，批量插入

#include <set>
#include <iostream>
using namespace std;

int main(){
    set<int> s {4, 2, 6};

    // 1. 普通插入
    auto [it1, ok1] = s.insert(5);
    cout << *it1 << (ok1?" 插入成功":" 已存在") << '\n';

    // 2. 重复键
    auto [it2, ok2] = s.insert(4);
    cout << *it2 << (ok2?" 插入成功":" 已存在") << '\n';

    // 3. 带提示插入
    auto hint = s.find(6);
    auto it3  = s.insert(hint, 7);   // hint 给在 6 之后，插入 7 正好紧邻
    cout << *it3 << '\n';

    // 4. 范围插入
    vector<int> v {9, 1, 3};
    s.insert(v.begin(), v.end());

    // 5. 初始化列表
    s.insert({10, 8});

    // 遍历
    for(int x:s) cout << x << ' ';   // 1 2 3 4 5 6 7 8 9 10
}

1. 与顺序容器 insert 的区别小结

---

• set::insert 永远自动排序，不会 push_back/push_front。

• 若键已存在，不会覆盖旧值，也不会报错，只是告诉你“没插进去”。

set的删除erase

#include<set>
int main()
{
	set<int> s;
	s.insert(9);
	s.insert(6);
	s.insert(5);
	s.insert(1);
	s.insert(7);

	s.erase(s.begin());
	int x;
	cin >> x;
	/*int num = s.erase(x);
	if (num == 0)
	{
		cout << x << "不存在" << endl;
	}*/

	auto pos = s.find(x);
	if (pos != s.end())
	{
		s.erase(pos);
	}
	else
	{
		cout << x << "不存在" << endl;
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

erase 三种玩法：

• 传迭代器 → 删指定位置，返回下一位置；

• 传键值 → 删等价元素，返回 0/1；

• 传区间 → 批量删除，返回下一位置。

#include <set>
#include <iostream>
int main(){
    std::set<int> s{7,3,5,9,3};

    // 1. 按键删
    if (s.erase(5))              // 返回 1 表示删掉了
        std::cout << "5 已删除\n";
    std::cout << "erase(4) 返回值 = " << s.erase(4) << '\n'; // 0

    // 2. 按迭代器删
    auto it = s.find(7);
    if (it != s.end())
        it = s.erase(it);        // 删 7，it 指向 9
    std::cout << "下一个元素是 " << *it << '\n';

    // 3. 区间删
    auto first = s.find(3);
    auto last  = s.find(9);
    s.erase(first, last);        // 删 [3,9) 即仅 3

    for (int x:s) std::cout << x << ' ';  // 9
}

set中的count

count只给个数不给位置，但是find只给位置但不告诉有无

#include <set>
#include <iostream>
int main(){
    std::set<int> s{3, 1, 4, 1, 5};
    int x = 4;
    if (s.count(x))
        std::cout << x << " 存在\n";
    else
        std::cout << x << " 不存在\n";

    std::cout << "s 里有 " << s.count(1) << " 个 1\n";   // 1
    std::cout << "s 里有 " << s.count(9) << " 个 9\n";   // 0
}

int main()
{
	std::set<int> myset;

	std::set<int>::iterator itlow, itup;
	for (int i = 1; i < 10; i++)
	{
		myset.insert(i * 10);
	}

	itlow = myset.lower_bound(30);//>=30
	itup = myset.upper_bound(60);//>60

	myset.erase(itlow, itup);

	for (std::set<int>::iterator it = myset.begin(); it != myset.end(); it++)
	{
		std::cout << ' ' << *it;
		std::cout << '\n';
	}
	return 0;
}

multiset的使用

multiset和set的使用完全类似，只不过multiset支持数据冗余

int main()
{
	multiset<int> s;
	s.insert(9);
	s.insert(1);
	s.insert(3);
	s.insert(6);
	s.insert(4);
	s.insert(6);
	s.insert(4);
	s.insert(7);
	s.insert(9);

	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	int x;
	cin >> x;
	auto pos = s.find(x);
	if (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

	cout << s.count(x) << endl;
	s.erase(x);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

其中如果find相同的值就会返回二叉搜索树第一个插入的值

map的使用

pair类型

std::pair<T1,T2> 就是 两个公共成员变量 first / second 的轻量级组合，配合 make_pair、结构化绑定，用来“一次搬两个值”最顺手。

// 1. 构造函数
pair<int, double> p1(42, 3.14);

// 2. 工厂函数 make_pair（自动推导类型）
auto p2 = std::make_pair(1, "abc");   // pair<int, const char*>

// 3. C++17 起 类模板参数推导 (CTAD)
std::pair p3(5, 6.6);                 // pair<int,double>

// 4. 列表初始化（C++11）
pair<char,float> p4{'A', 2.0f};

#include<map>
#include<iostream>
#include<string>
using namespace std;
//int main()
//{
//	map<string, string> dict;
//
//	pair<string, string> kv1("left", "左边");
//	dict.insert(kv1);
//
//	dict.insert(make_pair("insert", "插入"));
//
//	dict.insert({ "right","右边" });
//
//	/*map<string, string>::iterator it = dict.begin();
//	while(it != dict.end())
//	{
//		cout << it->first << ";" << it->second << endl;
//
//		++it;
//	}
//	cout << endl;
//
//	for (auto e : dict)
//	{
//		cout << e.first << ":" << e.second <<" ";
//	}
//	cout << endl;*/
//
//	string str;
//	while (cin >> str)
//	{
//		auto ret = dict.find(str);;
//		if (ret != dict.end())
//		{
//			cout << ret->second << endl;
//		}
//		else
//		{
//			cout << "无此单词" << endl;
//		}
//	}
//
//	return 0;
//}

int main()
{
	string arr[] = { "苹果","香蕉","苹果","西瓜","西瓜","苹果","香蕉","苹果" };
	map<string, int> countTree;
	for (const auto& str : arr)
	{
		auto ret = countTree.find(str);

		if (ret == countTree.end())
		{
			countTree.insert({ str,1 });
		}
		else
		{
			ret->second++;
		}
	}

	for (const auto& e : countTree)
	{
		cout << e.first << ":" << e.second << endl;

	}
	cout << endl;
	return 0;
}