Для начала стоит отметить, что проекты я выбирал на си-подобных языках: в первую очередь С++, Java и прочие. Стратегией поиска были: форк репозитория, клонирование его на виртуальную машину под OC linux и поиск по содержимому файлов с помощью команды
grep --include=\*.{cpp,hpp} -rnw '/path/to/somewhere/' -e "pattern"
Где в фигурных скобках указываются типы файлов, которые нужно проверять, в одинарных кавычках - путь, в двойных - то, что нужно искать в этих файлах.
К примеру, в проекте Aleth (C++ Etherium client):
Результат поиска по запросу list
mocurin@mocurin-VirtualBox:~$ grep --include=\*.{cpp,hpp} -rnw 'aleth' -e "list"
aleth/libweb3jsonrpc/Eth.cpp:144: //Return list of transaction that being sent by local accounts
aleth/libdevcrypto/LibSnark.cpp:133: // Input: list of pairs of G1 and G2 points
aleth/libevm/VMFactory.cpp:54:/// We don't use a map to avoid complex dynamic initialization. This list will never be long,
aleth/libevm/VMFactory.cpp:115:/// The list of EVMC options stored as pairs of (name, value).
aleth/rlp/main.cpp:205: else if (arg == "list")
aleth/rlp/main.cpp:220: << " list [ <file> | -- ] List the items in the RLP list by hash and size." << endl
aleth/rlp/main.cpp:221: << " extract [ <file> | -- ] Extract all items in the RLP list, named by hash." << endl
aleth/rlp/main.cpp:335: cerr << "Error: Invalid format; RLP data is not a list." << endl;
aleth/rlp/main.cpp:343: cerr << "Error: Invalid format; RLP list item is not data." << endl;
aleth/rlp/main.cpp:355: cerr << "Error: Invalid format; RLP data is not a list." << endl;
aleth/rlp/main.cpp:363: cerr << "Error: Invalid format; RLP list item is not data." << endl;
aleth/libethereum/EthereumCapability.cpp:449: // Build list of peers to send transactions to
aleth/libethereum/BlockQueue.cpp:318: list<h256> badQueue(1, _bad);
aleth/libethereum/BlockQueue.cpp:476: list<h256> goodQueue(1, _good);
aleth/libethereum/BlockChainSync.cpp:928: // Can't check invariants here since the peers is already removed from the list and the state is not updated yet.
aleth/libethcore/BlockHeader.cpp:160: BOOST_THROW_EXCEPTION(InvalidBlockFormat() << errinfo_comment("Block must be a list") << BadFieldError(0, _block.toString()));
aleth/libethcore/BlockHeader.cpp:163: BOOST_THROW_EXCEPTION(InvalidBlockFormat() << errinfo_comment("Block header must be a list") << BadFieldError(0, header.data().toString()));
aleth/libethcore/BlockHeader.cpp:165: BOOST_THROW_EXCEPTION(InvalidBlockFormat() << errinfo_comment("Block transactions must be a list") << BadFieldError(1, root[1].data().toString()));
aleth/libethcore/BlockHeader.cpp:167: BOOST_THROW_EXCEPTION(InvalidBlockFormat() << errinfo_comment("Block uncles must be a list") << BadFieldError(2, root[2].data().toString()));
aleth/libethcore/TransactionBase.cpp:53: BOOST_THROW_EXCEPTION(InvalidTransactionFormat() << errinfo_comment("transaction RLP must be a list"));
aleth/libp2p/NodeTable.cpp:157:list<NodeID> NodeTable::nodes() const
aleth/libp2p/NodeTable.cpp:159: list<NodeID> nodes;
aleth/libp2p/NodeTable.cpp:168:list<NodeEntry> NodeTable::snapshot() const
aleth/libp2p/NodeTable.cpp:170: list<NodeEntry> ret;
aleth/libp2p/NodeTable.cpp:377: // (i.e. to the end of the list)
aleth/libp2p/Host.cpp:764: list<shared_ptr<Peer>> toConnect;
aleth/libp2p/Host.cpp:920: list<NodeEntry> nodeTableEntries;
aleth/libp2p/Host.cpp:1014: // node was saved from the connected peer list
aleth/test/tools/fuzzTesting/fuzzHelper.cpp:129: //make header as list
aleth/test/tools/fuzzTesting/fuzzHelper.cpp:200: //list 0-55 [0xc0, 0xf7] + data
aleth/test/tools/fuzzTesting/fuzzHelper.cpp:209: //list more 55 [0xf8, 0xff] + length + data
aleth/test/tools/fuzzTesting/fuzzHelper.cpp:430: randomAddressProbability(3), //probability of generating a random address instead of defined from list
aleth/test/tools/fuzzTesting/fuzzHelper.cpp:575: // Return address of the sender (sender is a part of state acount list)
aleth/test/tools/jsontests/BlockChainTests.cpp:489: // if exception is thrown, RLP is invalid and no blockHeader, Transaction list, or Uncle list should be given
aleth/test/tools/jsontests/BlockChainTests.cpp:865: cnote << "uncle list mismatch\n" << RLP(_a.bytes())[2].data() << "\n" << RLP(_b.bytes())[2].data();
aleth/test/tools/jsontests/BlockChainTests.cpp:941: // if exception is thrown, RLP is invalid and no blockHeader, Transaction list, or Uncle list should be given
aleth/test/tools/jsontests/BlockChainTests.cpp:974: BOOST_CHECK_MESSAGE(txsFromRlp.size() == txsFromField.size(), _testname + "transaction list size does not match");
aleth/test/tools/libtesteth/TestSuite.cpp:43: list<string> removeList;
aleth/test/tools/libtesteth/Options.cpp:76: cout << setw(30) << "--help" << setw(25) << "Display list of command arguments\n";
aleth/test/unittests/libethereum/TransactionQueue.cpp:272: //future list size is now 3 + 1 imported transaction
aleth/test/unittests/libp2p/peer.cpp:150: list<Host*> hosts;
aleth/test/unittests/libp2p/net.cpp:617: list<NodeEntry> const allNodeEntries = nodeTable->snapshot();
aleth/test/unittests/libdevcore/RLP.cpp:79: // non-list RLP data
aleth/aleth/AccountManager.cpp:33: _out << " account list List all keys available in wallet\n"
aleth/aleth/AccountManager.cpp:80: if (argc < 3 || string(argv[2]) == "list")
aleth/aleth/main.cpp:285: peersetDescriptionStream << "Comma delimited list of peers; element format: type:enode://publickey@ipAddress[:port[?discport=port]]\n"
aleth/aleth/main.cpp:295: addNetworkingOption("peerset", po::value<string>()->value_name("<list>"), peersetDescription.c_str());
aleth/libdevcore/RLP.cpp:251: size_t s = m_out.size() - p; // list size
aleth/libdevcore/RLP.cpp:270: _itemCount = 1; // for all following iterations, we've effectively appended a single item only since we completed a list.
aleth/libdevcore/DBFactory.cpp:47:/// We don't use a map to avoid complex dynamic initialization. This list will never be long,
aleth/libdevcore/LoggingProgramOptions.cpp:33: "Space-separated list of the log channels to show (default: show all channels)." +
aleth/libdevcore/LoggingProgramOptions.cpp:44: "Space-separated list of the log channels to hide.\n");
aleth/evmc/include/evmc/evmc.hpp:83: /// with provided list of options.aleth/libethereum/BlockQueue.cpp:318: list<h256> badQueue(1, _bad);
aleth/libethereum/BlockQueue.cpp:476: list<h256> goodQueue(1, _good);Код метода выглядит так:
void BlockQueue::noteReady_WITH_LOCK(h256 const& _good)
{
DEV_INVARIANT_CHECK;
list<h256> goodQueue(1, _good); // 1
bool notify = false;
while (!goodQueue.empty())
{
h256 const parent = goodQueue.front(); // 2
vector<pair<h256, bytes>> const removed = m_unknown.removeByKeyEqual(parent);
goodQueue.pop_front(); // 3
for (auto& newReady: removed)
{
DEV_GUARDED(m_verification)
m_unverified.enqueue(UnverifiedBlock { newReady.first, parent, move(newReady.second) });
m_unknownSet.erase(newReady.first);
m_readySet.insert(newReady.first);
goodQueue.push_back(newReady.first); // 4
notify = true;
}
}
if (notify)
m_moreToVerify.notify_all();
}Я отметил в коде 4 места:
- Строка 476: создание "очереди", которая по факту очередью не является. Здесь используется STL-ный двунаправленный список "std::list", но используется он лишь в рамках функционала очереди.
- Строка 480: доступ к первому элементу. Здесь вызывается метод list::front(), позволяющий "взглянуть" на первый элемент.
- Строка 482: удаление первого элемента из очереди. Метод list::pop_front() удаляет "голову" списка, то есть первый элемент.
- Строка 489: добавление элемента в очередь. Метод list::push_back(Elem elem) добавляет elem в конец списка.
Касаемо очистки списка - тут она происходит в деструкторе std::list, который вызывается в конце блока, куда помещен этот список,- память выделенная под каждый элемент освобождается и список таким образом очищается.
Таким образом, std::list здесь используется как очередь: элементы забираются из начала, добавляются лишь в конец. Реализуется FIFO (first in first out). В STL есть достаточно удобный для этого контейнер std::queue, но, возможно, в силу его реализации, разработчики этого проекта предпочли двунаправленный список.
В проекте Aleth достаточно трудно найти место, где на списке что-то по-настоящему базируется. В основном там используются хэш-таблицы. Поэтому я выбрал другой проект - Thor-os:
Код там написан достаточно просто и, что самое главное, там есть юнит-тесты, где большая часть методов успешно вызывается.
Файл thor-os/tstl/test_suite/vector.cpp
- Строка 30: Создание вектора. Как действие над atd мы это не обозначали, но отметить это место как важное считаю нужным
void test_erase(){
std::vector<int> a{1, 0, 0, 2, 3, 4};
...- Строка 32: Удаление элемента. Здесь происходит удаление по индексу, т.е удаляется третий по счету элемент.
...
a.erase(2);
...- Строка 34: Получение размера списка.
...
check(a.size() == 5, "Invalid vector:size");
...- Строка 35: Получение i-го элемента, т.е. получение элемента по индексу (
std::vector::operator[](size_t index))
...
check(a[0] == 1, "Invalid vector:[]");
...- Строка 176: Очистка списка.
...
std::vector<kiss> vec;
...
vec.clear();
...- Строки 198 и 202: Вставка элементов. В то время как push_back является частным случаем вставки, который для std::vector имеет амортизированную сложность O(1), метод push_front для вектора несильно отличается от std::vector::insert(Elem elem), поэтому приведу я только их
...
for(size_t i = 0; i < 1000; ++i){
vec.push_back(i);
}
for(size_t i = 10000; i < 11000; ++i){
vec.push_front(i);
}
...- Строка 121: Получение следующего элемента. Здесь это действие реализовано через инкремент итератора. С помощью декремента, аналогичной операции, можно получить предыдущий элемент
...
auto it = a.begin();
...
++it;
...Эти методы используются и в других местах, но как правило, использованы через итераторы, а не через индексы, а потому менее явны.
В ранее рассмотренном проекте Aleth так же есть структура trie, которая является деревом. В основном ее разные формы(например с хэшированием или без), реализуется в файле aleth/libdevcore/TrieDB.h
- Строки 785, 786, файла aleth/libethereum/State.cpp. Получение корня
SecureTrieDB<h256, DB> storageDB(_state.db(), i.second.baseRoot())
...
assert(storageDB.root());
s.append(storageDB.root());
...Здесь корень сначала проверяется на отсутствие нуля, а затем помещается в поток s.
Так же, в проекте есть RangeMask - структура, которая, насколько я понимаю, нужна для хранения и слияния ренджей итераторов, внутри которого используется std::map, являющаяся деревом.
Далее операции будут производиться над полем m_ranges
std::map<unsigned, unsigned> m_ranges;
- Строка 69, файла aleth/libdevcore/RangeMask.h. Получение самого левого сына
...
for (auto i = m_ranges.begin(); i != m_ranges.end() && _items; ++i)
...Зная строение std::map можно без труда определить, что получение начального итератора и будет реализовывать это действие.
- Строка 84, того же файла. Получение элемента
...
for (auto i: m_ranges)
...
if (i.first != last)
ret.m_ranges[last] = i.first;
last = i.second;
....first и .last - получение значений пары, содержащейся в каждом ноде дерева. Строки вытащены из метода RangeMask inverted() const, согласно комментарию возвращет дополнение входящих ренджей
- Строка 141, того же файла. Обнуление дерева
void clear()
{
m_ranges.clear();
}Используется для очистки содержимого управляющей структуры.
- Слияние и получение правого брата Конкретно в этом проекте мне не удалось найти каких-то операций ни одного, ни другого в явном типе. Слияние реализуется последовательной вставкой одного контейнера в другой, "быстрое" слияние не используется, либо просто не реализуется.
Так же в Aleth есть достаточно много примеров использования std::unordered_set как примера типичного множества:
- Строка 330, файл aleth/libdevcore/CommonData.h. Проверка принадлежности элемента множеству
template <class V>
bool contains(std::unordered_set<V> const& _set, V const& _v)
{
return _set.find(_v) != _set.end();
}Применяется, например в файле aleth/libdevcore/Log.cpp:
...
contains(_options.includeChannels, messageChannel)) &&
!contains(_options.excludeChannels, messageChannel);
...includeChannels и excludeChannels являются std::unordered_set для определенного в проекте класса channel.
- Строка 273, файл aleth/libdevcore/CommonData.h. Математические операции с множествами, добавление элемента в множество и слияние множеств
template <class T, class U>
std::unordered_set<T>& operator+=(std::unordered_set<T>& _a, U const& _b)
{
_a.insert(std::begin(_b), std::end(_b));
return _a;
}Приведу определение, но не использование функции, т.к. функция - оператор, которые куда труднее искать в проекте чем обычные функции. Так же этот оператор объявлен для большинства других контейнеров в проекте. Внутри функции присутствует вставка - метод std::unordered_set::insert(It start, it end)
Слияние так же реализуется это операцией. Как правило, множества сливаются в одно существующее или последовательно в созданное заранее.
- Строка 70, файла aleth/libethereum/EthereumPeer.h. Обнуление множества.
void clearKnownBlocks() { m_knownBlocks.clear(); }Поле m_knownBlocks объявлено как h256Hash m_knownBlocks , а h256Hash, в свою очередь using h256Hash = std::unordered_set<h256>. Таким образом это все то же множество.
clearKnownBlocks() используется в одном файле проекта (aleth/libethereum/EthereumCapability.cpp) для очистки множества.
- Строка 273, файла aleth/libethereum/ClientBase.cpp. Удаление элемента из множества
...
auto fit = m_filters.find(id);
...
m_filters.erase(fit);
...Здесь fit итератор std::unordered_map - т.е словаря m_filters. Происходит удаление по итератору.
- Касаемо нахождения минимального элемента - конкретно в этом проекте это не используется. Как правило, этот АТД используется с такими типами в качестве элементов, что в этой операции нет необходимости
В общем и целом - эти типы данных принимают самые разные формы, адаптируясь под цели проекта. Они могут как реализовывать функции своего типа, так и пропускать некоторые за ненадобностью. Даже если все методы реализуются, они могут быть не доступны пользователю Так же, как мне кажется, границы между ними порой очень размываются и определить что где и как используется достаточно трудно
Таким образом, АТД используются повсеместно, но чтобы такое использование приносило только пользу необходимо правильно их подбирать