[“Set”]

less than 1 minute read

Published:

C++

std::set in <set>

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>,
> class set;
  • Container that contains a sorted set of unique objects of type Key. Sorting is done using Compare.

  • Internally red-black trees are used. Search, removal, Insertion has logarithmic complexity.

  • capacity: size(), empty()
  • modify: clear(), insert()
  • lookup: find(), contains(), count(),

Java

Set is an interface implemented by: AbstractSet, ConcurrentSkipListSet, EnumSet, HashSet, LinkedHashSet, TreeSet

Set<E> set = new HashSet<E>();
  • capacity: size(), isEmpty()
  • modify: add(E e), addAll(Collection<? extends E> e)
  • lookup: contains(E e)

Leave a Comment

You May Also Enjoy

Algorithms Index

less than 1 minute read

Published:

This is the central index for the C++ algorithms series.

Segment Tree and Fenwick Tree

4 minute read

Published:

Fenwick Tree (Binary Indexed Tree)

Fenwick tree supports point updates and prefix/range sums efficiently. Core idea: each index stores partial sum of a power-of-two range. How it works: move index with idx += idx & -idx for update and reverse for query.

String Algorithms

4 minute read

Published:

KMP Prefix Function

Prefix function (pi) stores longest proper prefix that is also suffix for each prefix. Core idea: reuse previous match length instead of restarting from zero. How it works: on mismatch, jump using pi[j-1]; on match, increase j.

Dynamic Programming

2 minute read

Published:

1D DP: Fibonacci

DP stores answers to subproblems so each state is solved once. Core idea: define state and transition. How it works: dp[i] = dp[i-1] + dp[i-2].